Medida de los clusters de calidad en un gráfico

Question

Supongamos que tenemos un gráfico de $G=(V,E)$ $n$ no se solapan los subdiagramas, los clústeres $C_1, C_2, \dots, C_n$ que cubre el gráfico de $C_1 \cup \dots \cup C_n = G$.

Estoy buscando una buena métrica para medir la calidad de estos grupos.

Vamos a llamar a $m(C)$. Quisiera $m(C)$

• alta cuando la mayoría de los vecinos de los nodos dentro de $C$ también están en $C$
• el más alto al $C$ es un grafo completo sin los enlaces fuera de $C$
• cuando baja a la mayoría de los vecinos de los nodos dentro de $C$ están en otros grupos
• el menor al $C$ no tiene borde y cada uno de los nodos en $C$ está vinculado a todos los nodos en $G$ y fuera de $C$
• y null cuando hay exactamente el mismo número de vecinos dentro y fuera de $C$.

(Todo esto teniendo en cuenta que dos nodos vecinos, $C$ no debería contar dos veces).

Hace una métrica existen? ¿Cuál es su nombre? Gracias.

Answer 1

La medida de la modularidad propuesto por M. Girvan y M. E. J. Newman[1]. se define como: \begin{eqnarray} Q & = & (\mbox{fraction of edges within communities}) \\ & & - (\mbox{expected fraction of such edges}) \\ & = & \frac{1}{2m} \sum_{i,j} \left[ A_{ij} - \frac{k_i k_j}{2m} \ \right] \delta(c_i, c_j) \end{eqnarray} Donde $m=\frac{1}{2} \sum_{ij} A_{ij}$, $k_i = \sum_j A_{ij}$ y $A_{ij}$ es el peso entre el borde de conectar $i$$j$.
$\delta(c_i, c_j)$ es el Kroneker Delta, que es 1, sólo si el la comunidad de asignación de $c_i$ es igual a la de la comunidad de asignación de $c_j$.

Esta medida es positiva cuando la fracción de los bordes en el interior de las comunidades es mayor que la cantidad esperada de los bordes en el interior de las comunidades si los bordes se distribuyeron al azar. Cumple sus primeros 4 puntos.

[1] M. Girvan y M. E. J. Newman. Estructura de la comunidad en social y las redes biológicas. Procedimientos de la National La academia de las Ciencias de la, 99(12):7821-7826, 2002.