ARS Avanzado: Complejo clique

Complejo clique
Wikipedia



El complejo clique de un grafo. Los grupos de tamaño uno se muestran como pequeños discos rojos; grupos de tamaño 2 se muestran como segmentos de líneas negras; grupos de tamaño 3 se muestran como triángulos de color azul claro; y grupos de tamaño 4 o tetraedros se muestran de color azul oscuro.


Los complejos cliques, complejos de bandera, e hipergrafos conformales son objetos matemáticos que están relacionados estrechamente con la teoría de grafos y la topología geométrica que cada uno describen camarillas (subgrafos completos) de un grafo no dirigido.

El complejo clique  X(G) de un grafo no dirigido G es un complejo simplicial abstracto (es decir, una familia de conjuntos finitos cerrados bajo la operación de toma de subconjuntos), formada por los conjuntos de vértices en las camarillas de G. Cualquier subconjunto de una camarilla es en sí misma una camarilla, por lo que esta familia de conjuntos cumple con el requisito de un complejo simplicial abstracto en el que cada subconjunto de un conjunto en la familia también debe estar en la familia. El complejo clique también puede ser visto como un espacio topológico en el que cada camarilla de k vértices está representado por un simplex de dimensión k - 1. El 1-esqueleto de X (G) (también conocido como el grafo subyacente del complejo) es un grafo no dirigido con un vértice por cada conjunto de 1 elemento en la familia y un enlace para cada conjunto de 2 elementos en la familia; es isomorfo a G. [1]

Los complejos clique son también conocidos como complejos de Whitney. Una triangulación Whitney o triangulación limpio de un colector (manifold) de dos dimensiones es una incrustación de un grafo de G en el colector de tal manera que cada cara es un triángulo y cada triángulo es una cara. Si un grafo G tiene una triangulación Whitney, debe formar un complejo de célula que es isomorfo al complejo Whitney de G. En este caso, el complejo (visto como un espacio topológico) es homeomorfo al colector subyacente. Un grafo G tiene un complejo clique de 2 colectores (manifold), y puede ser incrustado como una triangulación Whitney, si y sólo si G es localmente cíclico; esto significa que, para cada vértice v en el grafo, el subgrafo inducido formado por los vecinos de v forma un solo ciclo. [2]

Complejo de independencia

El complejo independencia I (G) de un grafo G se forma de la misma manera como el complejo camarilla de los conjuntos independientes de G. Es el complejo camarilla del grafo complemento de G.

Complejo de bandera

En un complejo simplicial abstracto, un conjunto S de vértices que no es en sí parte del complejo, pero de tal manera que cada par de vértices en S pertenece a algún simplex en el complejo, que se llama un simplex vacío. Mikhail Gromov define la condición de no-Δ ser la condición de que un complejo no tienen simplices vacías. Un complejo bandera es un complejo simplicial abstracto que no tiene simplices vacías; es decir, que es la condición no-Δ un complejo de Gromov satisfacer. Cualquier complejo bandera es el complejo de su camarilla 1-esqueleto. Por lo tanto, los complejos y los complejos bandera camarilla son esencialmente la misma cosa. Sin embargo, en muchos casos puede ser conveniente definir un complejo bandera directamente de algunos datos distintos de un grafo, en lugar de indirectamente como el complejo clique de un grafo derivado de los datos. [3]

Conforme de hipergrafo

El grafo primario G (H) de un hipergrafo es el grafo en el mismo conjunto de vértices que tiene como sus enlaces los pares de vértices que aparecen juntos en la misma hiperenlace. Un hipergrafo se dice que es conforme si cada camarilla máxima de su grafo es un hipernelace primitivo, o equivalentemente, si cada camarilla de su grafo primario está contenida en alguna hiperenlace. [4] Si se requiere el hipergrafo sea descendente cerrado (por lo que contiene todos los hiperenlaces que se contienen en algunos hiperenlaces) entonces el hipergrafo es conforme con precisión cuando se trata de un complejo de bandera. Esto se relaciona el lenguaje de hipergrafos al lenguaje del complejo simplicial.

Ejemplos y aplicaciones

La subdivisión baricéntrica de cualquier complejo C de células es un complejo de bandera que tiene un vértice por célula de C. Una colección de vértices de la subdivisión baricéntrica formar un simplex si y sólo si la colección correspondiente de células de C forman una bandera (una cadena en el inclusión de pedido de las células). [3] En particular, la subdivisión barycentric de un complejo celular en un 2-colector da lugar a una triangulación Whitney del colector.

El complejo orden de un conjunto parcialmente ordenado se compone de las cadenas (subconjuntos totalmente ordenado) del orden parcial. Si cada par de algún subconjunto es en sí mismo ordenó, entonces todo el subconjunto es una cadena, por lo que los complejos satisface la condición de la orden de no-Δ. Se puede interpretar como el complejo camarilla del grafo de la comparabilidad de la orden parcial. [3]

El complejo de empardamiento (matching complex) de un grafo consiste en los conjuntos de enlaces ninguno de cuyos pares comparten un punto final; de nuevo, esta familia de conjuntos satisface la condición de no-Δ. Puede ser visto como el complejo camarilla del grafo complemento del grafo de líneas del grafo dado. Cuando el complejo juego se denomina sin ninguna representación grafo concreta como contexto, significa el complejo juego de un grafo completo. El complejo juego de un grafo bipartito completo K_m,n es conocida como un complejo de tablero de ajedrez. Es el clique de del grafo complemento del grafo de una torre, [5] y cada uno de sus simplices representa una colocación de torres en un tablero de m × n de ajedrez de tal manera que no hay dos de las torres atacan entre sí. Cuando m = n ± 1, las formas complejas de tablero de ajedrez una pseudo-colector.

El complejo Vietoris-Rips de un conjunto de puntos en un espacio métrico es un caso especial de un complejo clique, formado a partir del grafo de disco unidad de los puntos; Sin embargo, cada complejo clique X(G) puede ser interpretada como el complejo Vietoris-Rips de la métrica camino más corto en el grafo subyacente G.

Hodkinson y Otto (2003) describen una aplicación de hipergrafos conformales en la lógica de las estructuras relacionales. En ese contexto, el grafo de Gaifman de una estructura relacional es el mismo que el grafo subyacente del hipergrafo que representa la estructura, y una estructura esté vigilado si corresponde a un hipergrafo conformal.

Gromov mostró que un complejo cúbico (es decir, una familia de hipercubos intersección cara a cara) forma un CAT (0) espacio si y sólo si el complejo está simplemente conectado y el enlace de cada vértice forma un complejo bandera. Una reunión compleja cúbica estas condiciones a veces se llama una cubicación o un espacio con paredes. [1] [6]

Referencias

1. Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J. E.; Pach, J.; Pollack, R., Surveys on Discrete and Computational Geometry: Twenty Years Later (PDF), Contemporary Mathematics, 453, Providence, RI: AMS, pp. 49–86.
2. Berge, C. (1989), Hypergraphs: Combinatorics of Finite Sets, North-Holland, ISBN 0-444-87489-5.
3. Chatterji, I.; Niblo, G. (2005), "From wall spaces to CAT(0) cube complexes", International Journal of Algebra and Computation, 15 (5–6): 875–885, arXiv:math.GT/0309036, doi:10.1142/S0218196705002669.
4. Davis, M. W. (2002), "Nonpositive curvature and reflection groups", in Daverman, R. J.; Sher, R. B., Handbook of Geometric Topology, Elsevier, pp. 373–422.
5. Dong, X.; Wachs, M. L. (2002), "Combinatorial Laplacian of the matching complex", Electronic Journal of Combinatorics, 9: R17.
6. Hartsfeld, N.; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica, 11 (2): 145–155, doi:10.1007/BF01206358.
7. Hodkinson, I.; Otto, M. (2003), "Finite conformal hypergraph covers and Gaifman cliques in finite structures", The Bulletin of Symbolic Logic, 9 (3): 387–405, doi:10.2178/bsl/1058448678.
8. Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics, 258: 123–135, doi:10.1016/S0012-365X(02)00266-2.
9. Malnič, A.; Mohar, B. (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B, 56 (2): 147–164, doi:10.1016/0095-8956(92)90015-P.

La reciprocidad de los enlaces de amistad es menor de lo que imaginamos

Investigación: Usted tiene menos amigos de lo que piensa
Alex "Sandy" Pentland | Harvard Business Review





La gente asume que cuando se consideran otra persona un "amigo", esa persona también piensa en ellos como un amigo. En otras palabras, la amistad es recíproca. Pero cuando analizamos las encuestas de relación de auto-reporte de varios experimentos en todo el mundo, nos encontramos que, si bien la mayoría de la gente asume que las amistades son de doble sentido, sólo la mitad de las amistades son, en efecto recíproco. Estos resultados indican una profunda incapacidad de las personas para saber quiénes son sus amigos, tal vez debido a la posibilidad de la amistad no recíproco desafía a la propia imagen de sí mismo. nos gustan, que tienen como nosotros.

En sí mismo esto puede parecer como un hallazgo interesante, pero de menor importancia, pero esta gran proporción de amistades asimétricas se traduce en un efecto importante sobre la capacidad de un individuo para persuadir a otros a cooperar o cambiar su comportamiento.

Eso es porque el éxito depende de la capacidad de reclutar amigos para ayudar en los momentos críticos. Los estudios han demostrado que la influencia social es un factor crítico en el cambio organizacional, y especialmente en la propagación de nuevos comportamientos, nuevas ideas y nuevos métodos en ambas organizaciones y la sociedad en general.

Por otra parte, en los últimos años programas de apoyo entre pares se han convertido en altamente eficaz y potenciar formas de aprovechar la influencia de grupo para apoyar el cambio de comportamiento de los empleados. Un tipo específico de programa de apoyo entre pares es el "sistema de amigos", en la que los individuos se emparejan con otro persona (es decir, un compañero) con la responsabilidad de apoyar su intento de cambiar su comportamiento, como la seguridad en los entornos de trabajo, dejar de fumar, y la condición física.

Sin embargo, nuestros hallazgos sugieren que esta percepción errónea de amistades limita de manera significativa los esfuerzos como sistemas de compañeros para promover un cambio de comportamiento Lo que es más, hemos encontrado que la direccionalidad de la amistad - amistad, que forma en que se percibe entre dos personas - es también un factor.

Por ejemplo, cuando se analizó la efectividad de un programa de acondicionamiento físico "sistema de compañeros", encontramos que cuando existe una amistad lazo de un solo sentido desde el compañero (la persona que solicita la presión de grupo) para el sujeto (la persona que recibe la presión), programas fueron más eficaces que cuando el lazo de amistad fue del sujeto al amigo. Aunque lo mejor es tener una amistad recíproca, que tiene un amigo que piensa de su objeto como un amigo es la siguiente mejor relación.

diseñadores de intervención, ya sea con programas de acondicionamiento físico o programas para dejar de fumar o cualquier otro, no puede depender de cómo el sujeto percibe la relación con el compañero para crear eficacia. Para superar esta limitación, hemos descubierto que dos conclusiones simples que se pueden aplicar a más efectivamente lograr un cambio de comportamiento.

La primera es que no debemos asumir las personas con un alto número de lazos sociales son "personas influyentes." Estas personas no son mejores y, a menudo son peores que el promedio de personas a ejercer influencia social. Nuestros resultados sugieren que esto se debe a que muchos de esos lazos o bien no son recíprocas o ir en la dirección equivocada, y por lo tanto no dará lugar a la persuasión efectiva. en lugar de buscar personas influyentes con un montón de amigos, buscar amigos que son compañeros, con aproximadamente el mismo número de amigos y muchos amigos en común .

En segundo lugar, si usted quiere ser un agente de cambio social, es posible que no desea iniciar centrándose en las personas que "saben todos" en la organización. Puede ser un error confiar en ellos para instituir el cambio que desea crear. Ellos simplemente tienen demasiadas cosas en que es fidedigna. en su lugar, comience por crear un consenso con sus compañeros que forman parte de sus redes de interacción. Después de hacer eso, los "influenciadores" empezarán a tomar el cambio propuesto en serio.

Al entender que la influencia social depende de la reciprocidad y la amistad dirección, puede ser más eficaz en la promoción del cambio de comportamiento, la difusión de las nuevas ideas, e incluso la promoción de productos.

ARS 101: Qué son las redes de coautoría

Redes de coautoría

Por Juan MC Larrosa


Una red social es un conjunto de personas o grupos, cada uno de los cuales tiene conexiones de algún tipo para todos o algunos de los otros. En el lenguaje del análisis de redes sociales, las personas o grupos se llaman actores y las conexiones, lazos o enlaces. Ambos actores y lazos se pueden definir de diferentes maneras dependiendo de las cuestiones de interés. Un actor puede ser una sola persona, un equipo o una empresa. Un enlace podría ser una amistad entre dos personas, una colaboración o miembros comunes entre dos equipos, o una relación de negocios entre empresas.
Aquí construimos redes de científicos en el que una relación entre dos científicos se establece por su coautoría de uno o varios artículos científicos. Estas redes son las redes de afiliación en la que los actores están unidos por su común pertenencia a grupos formados por los autores de un artículo. Son las redes sociales más verdaderamente que muchas redes de afiliación; es probable que sea justo decir que la mayoría de las personas que han escrito un documento conjunto están realmente familiarizados entre sí, de manera que, por ejemplo, actores de cine, que actuaron juntos en una película no puede ser. Hay excepciones-algunos muy grandes colaboraciones, por ejemplo en la física de alta energía, contendrá coautores que nunca han conocido-y discutimos éstos en su caso.
En general, sin embargo, la red refleja una verdadera interacción profesional entre los científicos, y puede ser la red social más grande jamás estudiado. Las redes de coautorazgo entonces son aquellas que identifican a los autores de un mismo trabajo literario o académico como unidos en una asociación por haber participado en el mismo.

Abajo se observan las típicas referencias de un trabajo académico.



¿Cómo ello se traduce a una red? Por ejemplo un trabajo coautorado entre dos actores puede tener las representación de una red no dirigida (simétrica) lineal, como se aprecia abajo:



Si el mismo autor (nodo rojo) realizara otra contribución con un tercer autor podría representarse como una extensión como se ve debajo:


A su vez, si los tres autores escribieran un trabajo con coautorándolo, quedaría representado por una red triangular como se representa debajo:


Y así sucesivamente para un paper con 4 coautores...

... 5 coautores...


... 6 coautores...



Y así. Ese puede ser un inicio para el estudio de redes más complicadas como la de abajo, donde un autor (nodo rojo) ha participado en diversos trabajos con variado número de coautores...

 



continuará