Mostrando entradas con la etiqueta componentes conectados. Mostrar todas las entradas
Mostrando entradas con la etiqueta componentes conectados. Mostrar todas las entradas

lunes, 3 de octubre de 2016

ARS 101: Bi-componentes conectados o vértices de corte

Bicomponentes conectados o vértice de corte
Wikipedia


Un grafo de ejemplo con el vértice de corte marcado. Cada color corresponde a un vértice de corte. vértices multicolores se cortan vértices, y por lo tanto pertenecen a varios vértice de corte.

En la teoría de grafos, un vértice de corte (también conocido como un bloque o componente 2-conectado) es un subgrafo máximo biconexas. Cualquier grafo conexo se descompone en un árbol del vértice de corte llamado el árbol de corte de bloque del grafo. Los bloques están unidos entre sí en los vértices compartidos llamados vértices de corte o puntos de articulación. Específicamente, un vértice de corte es cualquier vértice cuya eliminación aumenta el número de componentes conectados.


Algoritmos

El tiempo lineal profundidad primera búsqueda

El algoritmo secuencial clásica para el cálculo de vértice de corte en un grafo no dirigido conectada se debe a John Hopcroft y Robert Tarjan (1973). [1] Se ejecuta en tiempo lineal, y se basa en la búsqueda en profundidad. Este algoritmo también se perfila como un Problem 22-2 de su Introduction to Algorithms (tanto 2ª y 3ª ediciones).

La idea es ejecutar una búsqueda en profundidad mientras se mantiene la siguiente información:
  • la profundidad de cada vértice en el árbol de profundidad-primero-búsqueda (una vez que se visitó), y
  • para cada vértice v, la profundidad más baja de los vecinos de todos los descendientes de v en el árbol de profundidad primera búsqueda, llamado el punto más bajo.

La profundidad es estándar para mantener durante una búsqueda en profundidad. El punto más bajo de v puede calcularse después de visitar todos los descendientes de v (es decir, justo antes de v se apareció de la pila profundidad-primero-búsqueda) como el mínimo de la profundidad de v, la profundidad de todos los vecinos de v (aparte de la padre de v en el árbol de la profundidad de primera búsqueda) y el punto más bajo de todos los hijos de v en el árbol de la profundidad de primera búsqueda.

La clave es que un vértice no raíz v es un vértice de corte (o punto de articulación) que separa dos vértice de corte si y sólo si hay un niño y de v tal que si profundidad  ≥ punto más bajo (y) (v). Esta propiedad puede ser probado una vez que la búsqueda en profundidad regresó de cada hijo de v (es decir, justo antes de v se hizo estallar de la pila de profundidad primera búsqueda), y si es verdad, v separa el grafo en diferentes vértice de corte. Esto se puede representar mediante el cálculo de un vértice de corte de cada uno de estos y (un componente que contiene y contendrá el subárbol de y, además v) y, a continuación, borrar el subárbol de y del árbol.

El vértice de la raíz debe ser manejado por separado: es un vértice de corte si y sólo si tiene al menos dos hijos. Por lo tanto, basta con simplemente construir un componente de cada subárbol hijo de la raíz (incluyendo la raíz).

Pseudocódigo

GetArticulationPoints(i, d)
    visited[i] = true
    depth[i] = d
    low[i] = d
    childCount = 0
    isArticulation = false
    for each ni in adj[i]
        if not visited[ni]
            parent[ni] = i
            GetArticulationPoints(ni, d + 1)
            childCount = childCount + 1
            if low[ni] >= depth[i]
                isArticulation = true
            low[i] = Min(low[i], low[ni])
        else if ni <> parent[i]
            low[i] = Min(low[i], depth[ni])
    if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
        Output i as articulation point

Otros algoritmos

Una alternativa simple al algoritmo anterior utiliza descomposiciones de la cadena, que son descomposiciones especiales para los oídos en función de árboles DFS. [2] Las descomposiciones de cadena se pueden calcular en tiempo lineal por esta regla de desplazamiento. Sea C una descomposición de la cadena de G. Entonces se conecta-2-vértice G si y sólo si G tiene grado mínimo 2 y C1 es el único ciclo en C. Esto da inmediatamente una prueba de 2-conectividad en tiempo lineal y se puede ampliar listar todos los vértices de corte de G en el tiempo lineal utilizando la siguiente instrucción: un vértice v en un grafo conexo G (con grado mínimo 2) es un vértice de corte si y sólo si v es incidente a un puente o v es el primer vértice de un ciclo en C - C1. La lista de los vértices de corte se puede utilizar para crear el árbol de bloque de corte de G en el tiempo lineal.

En la versión en línea del problema, se añaden vértices y aristas (pero no eliminado) de forma dinámica, y una estructura de datos deben mantener las vértice de corte. Jeffery Westbrook y Robert Tarjan (1992) [3] desarrollaron una estructura de datos eficiente para este problema sobre la base de estructuras de datos disjuntos-set. En concreto, se procesa n vértices adiciones y adiciones m de borde en O (m α (m, n)) tiempo total, donde α es la función inversa Ackermann. Esta vez unida se demostró ser óptima.

Uzi Vishkin y Robert Tarjan (1985) [4] diseñaron un algoritmo paralelo en CRCW PRAM que se ejecuta en O (log n) tiempo con n + m procesadores. Guojing Cong y David A. Bader (2005) [5] desarrollaron un algoritmo que logra una aceleración de 5 con 12 procesadores en SMP. Aceleraciones superiores a 30 basado en el algoritmo original Tarjan-Vishkin fueron reportados por James A. Edwards y Uzi Vishkin (2012). [6]

Estructuras relacionadas

Relación de equivalencia

Uno puede definir una relación binaria en los bordes de un grafo no dirigido arbitraria, según la cual dos bordes E y F están relacionadas si y sólo si, ya sea e = f o el grafo contiene un ciclo simple tanto a través de e y f. Cada borde está relacionada a sí mismo, y un borde e está relacionado con otro borde f si y sólo si f está relacionado de la misma manera a E, menos evidente, esta es una relación transitiva: si existe un ciclo simple que contiene bordes e y f, y otro ciclo simple que contiene bordes F y g, entonces se pueden combinar estos dos ciclos de encontrar un ciclo simple a través de e y g. Por lo tanto, esta es una relación de equivalencia, y que puede ser utilizado para dividir los bordes en clases de equivalencia, los subconjuntos de los bordes con la propiedad de que dos bordes están relacionados entre sí, si y sólo si pertenecen a la misma clase de equivalencia. Los subgraphs formados por los bordes de cada clase de equivalencia son los vértice de corte de la grafo dada. Por lo tanto, los vértice de corte partición de los bordes de la grafo; sin embargo, pueden compartir vértices entre sí. [7]

Grafo de bloque 

El grafo de bloques de un grafo dado G es el grafo intersección de sus bloques. Por lo tanto, tiene un vértice para cada bloque de G, y un borde entre dos vértices siempre que las correspondientes dos bloques comparten un vértice. Un grafo H es el grafo de bloques de otro grafo G exactamente cuando todos los bloques de H son subgrafos completos. Los grafo H con esta propiedad son conocidos como los grafos de bloque. [8]

Árbol de bloque de corte

Un punto de un grafo de G punto de corte, el vértice de corte, o la articulación es un vértice que es compartida por dos o más bloques. La estructura de los bloques y los puntos de corte de un grafo conectado puede ser descrita por un árbol llamado el árbol de bloque de corte o árbol de BC. Este árbol tiene un vértice para cada bloque y para cada punto del grafo dada la articulación. Hay una ventaja en el árbol de bloque de corte para cada par de un bloque y un punto de articulación que pertenece a ese bloque. [9]


Notas

  1. Hopcroft, J.; Tarjan, R. (1973). "Algorithm 447: efficient algorithms for graph manipulation". Communications of the ACM. 16 (6): 372–378. doi:10.1145/362248.362272.
  2. Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters, 113 (7): 241–244, doi:10.1016/j.ipl.2013.01.016.
  3. Westbrook, J.; Tarjan, R. E. (1992). "Maintaining bridge-connected and biconnected components on-line". Algorithmica. 7: 433–464. doi:10.1007/BF01758773.
  4. Tarjan, R.; Vishkin, U. (1985). "An Efficient Parallel Biconnectivity Algorithm". SIAM J. Comput. 14 (4): 862–874. doi:10.1137/0214061.
  5. Guojing Cong and David A. Bader, (2005). "An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs)". Proceedings of the 19th IEEE International Conference on Parallel and Distributed Processing Symposium. pp. 45b. doi:10.1109/IPDPS.2005.100.
  6. Edwards, J. A.; Vishkin, U. (2012). "Better speedups using simpler parallel programming for graph connectivity and biconnectivity". Proceedings of the 2012 International Workshop on Programming Models and Applications for Multicores and Manycores - PMAM '12. p. 103. doi:10.1145/2141702.2141714. ISBN 9781450312110.
  7. Tarjan & Vishkin (1985) credit the definition of this equivalence relation to Harary (1969); however, Harary does not appear to describe it in explicit terms.
  8. Harary, Frank (1969), Graph Theory, Addison-Wesley, p. 29.
  9. Harary (1969), p. 36.

sábado, 25 de octubre de 2014

Centralidad de cercanía en componentes desconectados

Centralidad de cercanía en redes con componentes desconectados

Una medida centralidad de nodo clave en las redes es proximidad central (Freeman, 1978;. Opsahl et al, 2010; Wasserman y Faust, 1994). Se define como la inversa de la lejanía, que a su vez, es la suma de las distancias a todos los demás nodos. Como la distancia entre los nodos en los componentes desconectados de una red es infinito, esta medida no se puede aplicar a redes con componentes desconectados (Opsahl et al, 2010;. Wasserman y Faust, 1994). Este anuncio pone de relieve una posible solución temporal, lo que permite que la medida se aplique a estas redes y al mismo tiempo mantener la idea original detrás de la medida.

Esta red da un ejemplo concreto de la medida de la cercanía. La distancia entre el nodo G y el nodo H es infinita dado que no existe un camino directo o indirecto entre ellos (es decir, que pertenecen componentes separados). Mientras al menos un nodo es inalcanzable por los otros, la suma de las distancias a todos los otros nodos es infinito. Como consecuencia, los investigadores han limitado la cercanía a medida el componente más grande de nodos (es decir, medido intra-componente). La matriz de distancia para los nodos de la red de la muestra es:
NodosTodos incluidosIntra-componente
ABCDEFGHIJKLejaníaCercaníaLejaníaCercanía
A112233InfInfInfInfInf0120.08
B112123InfInfInfInfInf0100.10
C111222InfInfInfInfInf090.11
D221211InfInfInfInfInf090.11
E212213InfInfInfInfInf0110.09
F322112InfInfInfInfInf0110.09
G332132InfInfInfInfInf0140.07
HInfInfInfInfInfInfInf12InfInf030.33
IInfInfInfInfInfInfInf11InfInf020.50
JInfInfInfInfInfInfInf21InfInf030.33
KInfInfInfInfInfInfInfInfInfInfInf00Inf

Aunque las puntuaciones de proximidad dentro de los componentes no son infinitos para todos los nodos de la red, sería inexacto utilizarlos como medida cercanía. Esto es debido al hecho de que la suma de las distancias contendría un número diferente de trayectorias (por ejemplo, hay dos distancia desde el nodo H a otros nodos en su componente, mientras que hay seis distancias desde el nodo G a otros nodos de su componente). De hecho, los nodos en componentes más pequeños por lo general se considera que estar más cerca de los demás que los nodos de los componentes más grandes. Por lo tanto, los investigadores se ha centrado exclusivamente en el componente más grande. Sin embargo, esto conduce a una serie de cuestiones metodológicas, incluyendo la selección de la muestra.
Para desarrollar esta medida, me fui de nuevo a la ecuación original:
\mbox{closeness}(i) = \sum_j \left[ d_{ij} \right]^{-1} = \frac{1}{\sum_j d_{ij}}
donde i es el nodo focal, j es otro nodo en la red, y d_{ij} es la distancia mas corta entre estos dos nodos. En esta ecuación, las distancias están invertidas después de que se han sumado, y cuando la suma de un número infinito, el resultado es infinito. Para superar este problema durante su estancia en consonancia con la medida existente de cercanía, me aproveché del hecho de que el límite de un número dividido por infinito es cero. A pesar de que el infinito no es un número exacto, el inverso de un número muy alto es muy cercano a 0. De hecho, se devuelve 0 si introduce 1 / Inf en el programa estadístico R. Al tomar ventaja de esta característica, es posible reescribir la ecuación cercanía como la suma de las distancias La Inversa a todos los demás nodos en lugar de la inversa de la suma de las distancias a todos los demás nodos. La ecuación sería entonces:
\mbox{closeness}(i) = \sum_j \frac{1}{d_{ij}}
Para ejemplificar este cambio, para el ejemplo de la red anterior, las distancias inversas y las puntuaciones de proximidad son:
NodesCloseness
ABCDEFGHIJKSumNormalized
A1.001.000.500.500.330.3300003.670.37
B1.001.000.501.000.500.3300004.330.43
C1.001.001.000.500.500.5000004.500.45
D0.500.501.000.501.001.0000004.500.45
E0.501.000.500.501.000.3300003.830.38
F0.330.500.501.001.000.5000003.830.38
G0.330.330.501.000.330.5000003.000.30
H00000001.000.5001.500.15
I00000001.001.00020.20
J00000000.501.0001.500.15
K000000000000

Como puede verse en esta tabla, una puntuación cercanía se alcanza para todos los nodos, teniendo en cuenta un número igual de distancias para cada nodo, independientemente del tamaño del componente de los nodos. Por otra parte, los nodos que pertenecen a un mayor componente generalmente alcanza una puntuación más alta. Esto es deliberado, ya que estos nodos pueden llegar a un mayor número de personas distintas de los nodos en componentes más pequeños. Las puntuaciones normalizadas están unidos entre 0 y 1. Es 0 si un nodo es un aislado, y 1 si un nodo está conectado directamente todos los demás.
Esta medida se puede extender fácilmente a las redes ponderados mediante la introducción (1959) el algoritmo de Dijkstra tal como se propone en la distancia más corta media en redes ponderados.
Referencias
Dijkstra, E. W., 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271.
Freeman, L. C., 1978. Centrality in social networks: Conceptual clarification. Social Networks 1, 215-239.
Opsahl, T., Agneessens, F., Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks 32, 245-251.
Wasserman, S., Faust, K., 1994. Social Network Analysis: Methods and Applications. Cambridge University Press, New York, NY.

Tore Opsahl

martes, 23 de septiembre de 2014

Conectividad y descentralización en componentes

Sistemas descentralizados y el estado invisible: Cohesión multiconectada de baja densidad en Redes Sociales de gran escala en Tlaxcala, México

Douglas R. White, Michael Schnegg, y Lilyan A. Brudner 1999
Este material está basado en trabajo apoyado por la National Science Foundation con la subvención No. 9978282.



Tabla 2:

Nivel de conectividad (generando subgrupos limitados)
Conceptos de Cohesión
1-Componente Conectado (1-)
2-Conectado (bicomponente)
3-Conectado (tricomponente)
...
k-Conectado (k-componente)

Escala de Cohesión:
Vulnerable a desconexión

Potencialmente gran escala, Baja densidad

Agrupados dentro de bicomponentes
...
Jerárquicamente agrupado




Definición 1: A un (1) componente de una red (o grafo) es un conjunto máximo de nodos y arcos tales que cada par de nodos está conectado tres componentes (desconectado).
Definición 2: Una de dos componentes de una red (o grafo) es un conjunto máximo de nodos y arcos tales que cada par de nodos está conectado por dos o más caminos independientes (tres subgrafos gris claro).
Definición 3: Una de tres componentes de una red (o grafo) es un conjunto máximo de nodos y arcos tales que cada par de nodos está conectado por tres o más caminos independientes (subgrafo gris).
Definición General 4: Un k-componente de una red (o grafo) es un conjunto máximo de nodos y arcos de tal manera que cada par de nodos está conectado por k o más caminos independientes (no hay ejemplos anteriores para k> 2).

Las hipótesis generales:
(a) Biconectividad es una fuente de emergente, potencialmente descentralizada de cohesión social que puede ocurrir (con efectos observables) a baja densidad en (los bicomponentes de) las redes sociales relativamente estable.

(b) Esto es especialmente cierto para las relaciones que tienen muy alta "moneda" o de soporte vital relevancia, como las relaciones de poder político, la transmisión de la propiedad, o el parentesco y conexiones matrimoniales.

(c) Por lo tanto, la clase social, las élites, y los sistemas de matrimonio riqueza transmisión están especialmente bien adaptados para el análisis.


  • Una red descentralizada con biconectividad puede tener efectos más cohesionadas que una red centralizada o una mayor escala de cohesión de grupos localmente más cohesivos.
  • El mecanismo es el potencial para los circuitos de retroalimentación positiva auto-amplificación o.
  • Además, cuanto mayor es la conectividad ("redundancia"), menos vulnerabilidad a la desconexión. Máxima conectividad = minimo punto de corte (eliminación mínima de nodo para la desconexión): el teorema de Menger.
  • Por lo tanto, la energía, la información o los recursos pueden circular o redistribuidos en mayores k-componentes con mayor eficacia.
  • Bicomponentes son fáciles de identificar en gráficos grandes en o tiempo lineal (max (V, E)), V = vértices, E = bordes.
  • Bicomponentes no son "cerrados", pero irradian lazos hacia el exterior en los patrones conectivo con forma de árbol, posiblemente 1-conectados a otros bicomponentes. Los nodos en su perímetro pueden incluso ser más central en la gráfica general (nodo 9, en el ejemplo, se conecta dos bicomponentes).
  • En una red grande con suficiente (pero a menudo bajo) densidad, un gigante de dos componentes puede ser la fuente de la participación fuertemente cohesionada en ámbitos institucionales principales del grupo (aunque no todo el mundo biconexas por relaciones de alto divisas tendrá alta cohesión). Otros pueden ser 1-conectado al componente gigante. Esto da lugar a una estructura de tres partes:
    • el núcleo biconexas gigante 
    • su periferia, 1 conectado con el núcleo gigante  
    • los márgenes, en separadas 1-componentes
  • Conexiones dentro de una de dos componentes no necesitan ser homogénea: las interacciones locales o k-componentes de orden superior dentro bicomponentes pueden dar lugar a otras propiedades globales o subgrupo emergentes.
  • k-componentes de orden superior también son fácilmente computable: tricomponents en o tiempo lineal (V + E) [Hopcroft y Tarjan 1973], y todos los k-componentes en baja polinomio tiempo o (. V ** 5 ** E 2) [Aun y Tarjan 1975] o en tiempo casi lineal en computación paralela.
(d) la evolución dinámica de 1-conectividad y biconectivitdad (y conectividades de orden superior que tienen ambos efectos globales "gigante" de componentes y efectos de interacción localizadas) puede dar lugar a transiciones de fase en las configuraciones de red (un posible ejemplo: la co-evolución de los estados y mercados en la Florencia renacentista).


Fuente

domingo, 10 de noviembre de 2013

ARS 101: Centralidad, componentes y otros temas de redes

Lada Adamic nos comenta sobre centralidad y componentes conectados

Lada Adamic, ganadora en 2012 del afamado premio Henry Russell, es una científica social experta en redes sociales de la Universidad de Michigan. En esta exposición introductoria comenta sobre centralidad y componentes conectados. Los subtítulos en español y sus errores son responsabilidad mía.


martes, 27 de noviembre de 2012

Efecto de red a través de componentes gigantes

"Giant Components" Implies WInner-Takes-All in the Social Network Race

In graph theoretic social networking analysis, there's a concept known as "Giant Components". As the name implies, in any given human social network, there exists one main, extremely large, set of connected "nodes" (people) surrounded by significantly smaller, disconnected from the giant component, peripheral clusters of social networks.

This is illustrated qualitatively in "Networks, Crowds, and Markets" (free version here) by given the example: consider your current friend group, and who they're connected to, and so on. Ultimately, you'll find you're indirected connected to people from other countries. Another way to put it, if everyone has 100 (unique) friends, you very quickly get to large numbers of connected nodes (100 of your friends x (have) 100 friends x (who have) 100 friends x (who have) 100 friends x (who have) 100 friends = 10B people. However, there will be people, isolated on an island somewhere, that is not connected to the giant component.

Random Example (from here). You can see that a high proportion of nodes below to one connected cluster.
If any one person, in any one of the smaller clusters, becomes connected to the "Giant Component", the entire cluster is then considered part of the "Giant Component". So, it's reasonable to assume that, at some point, the desert island person will eventually meet one person in the giant component. It seems, in this connected world, we're almost fatalistically destined to be part of the giant component.

It is inevitable then, that we become part of the Facebook giant component, right? They're nearing 600 millions users, and check out this giant component.


In reality, things aren't as inevitable. It's not obvious initially, but a few things to consider:
  • The definition of the edges (connections between people) are a little more nuanced than simply "knowing" someone. What if you, instead of drawing a social graph based on Facebook-stated friendships, you drew it based on spending greater than 10 hours a day together? The graph would become much more fragmented.
  • Graphs can be used to represent different classes of social graphs. For example, and Facebook even does this, my family, and my coworkers could be represented as separate graphs. In other words, people are capable of belonging to multiple networks.
Both of these facts create an opportunity for emerging or niche social networks to evolve and grow -- and not necessarily at the expense of Facebook either! In retrospect, Livemocha, an interest-based social network, benefited from this.

Another example (or maybe a 3rd bullet is required above stating "cultural norms") is Mixi, a Japanese social network. Recently featured in the NYTimes, Facebook has been relatively unsuccessful in Japan. Some speculate it is cultural in nature; that the Japanese are more private and that Facebook's religious-like fervor towards unfettered openness doesn't resonate there. Allegedly, on Mixi only 5% of users use their real picture as an avatar.

The "giant component" question seems to simply be one of definition. Existentially, or environmentally, aren't we all connected?

As an aside, I'm taking a Social Media Analysis reading course this semester (similar to this one at Carnegie Melon). I have a weekly blog-writing assignment - this is the first post of many. 

Social Graph Paper