User Tools

Site Tools


hierarchical_graph_clustering

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

hierarchical_graph_clustering [2012/11/22 15:38] (current)
melancon created
Line 1: Line 1:
 +===== Visual Analytics Course =====
  
 +==== Graph clustering ====
 +
 +=== Louvain fast community unfolding (hierarchical clustering) algorithm ===
 +
 +The main reference for this algorithm is a paper by {{:​blondel_2008.pdf|Blondel et al. 2008}}. The method relies on a measure evaluating the //​modularity//​ of a clustering: just how well groups are defined. The modularity seeks at maximizing inner connectivity while minimizing outer connectivity. There are several measures that may be considered when running the Louvain algorithm. COnsider a grpah $G = (V, E)$ equipped with a clustering ${\bf C} = (C_1, \ldots, C_k)$.
 +
 +(Mancoridis modularity)
 +
 +$$
 +MQ(G; {\bf C}) = \frac{1}{k} \sum_i \frac{E(C_i,​ C_i)}{{|C_i|} \choose 2} - \frac{1}{{k (k-1)} \choose 2} \sum_{i < j} \frac{E(C_i,​ C_j)}{|C_i| \cdot |C_j|}
 +$$
 +
 +where $E(C_i, C_j)$ denotes the number of edges connecting clusters $C_i$ and $C_j$.
 +
 +$MQ$ thus computes a positive contribution in terms of inner connectivity,​ comparing each cluster to a clique of the same size. Outer connectivity brings in a negative contribution,​ comparing outer edges to a complete bipartite graph of the same size. $MQ$ thus varies in the [-1, 1] interval, with $MQ = 1$ when all clusters all (unconnected) cliques, while $MQ = -1$ when cliques are fully connected and edgeless. When considering clustering with no isolated nodes (clusters of size 1), $MQ$ can be shown to have mean value 0 and be estimated by a gaussian distribution.
 +
 +(Newman'​s modularity)
 +
 +$$
 +Q(G; {\bf C}) = \frac{1}{|E|} \big( \sum_i \big[ E(C_i, C_i) - \big( \sum_j \frac{1}{|E|} E(C_i, C_j) \big)  \big]^2 \big)
 +$$
 +
 +Observe that $\frac{1}{|E|} \sum_i E(C_i, C_i)$ is the fraction of edges that are internal to clusters, while $\sum_j \frac{1}{|E|} E(C_i, C_j)$ is the fraction of edges that connect to cluster $C_i$. The rationale behind $Q$ is quite clear: it measures just how '​far'​ $\bf C$ is from begin random (edges being dispatched randomly between clusters). Indeed, write the adjacency matrix of the graph as ${\bf A} = (a_{u v})_{u, v \in V}$. The probability that nodes $u$ and $v$ are connected in $G$, respecting node degrees, is $\frac{\deg_G(u) \deg_G(v)}{2|A}$. Hence, $Q$ may alternatively be defined as:
 +
 +$$
 +Q(G; {\bf C}) = \frac{1}{2 |E|} \sum_i \sum_{u, v, \in C_i} \big( a_{u v} - \frac{\deg_G(u) \deg_G(v)}{2|E|} \big).
 +$$
 +
 +The algorithm runs in two phases. Phase 1 seeks at optimizing modularity using a greedy approach:
 +
 +<​code>​
 +Louvain algorithm
 +
 +First consider a trivial partition where clusters correspond to singletons.
 +
 +The cluster containing a node is called its community.
 +
 +Iterate until the overall modularity no more improves
 +  Iterate over all nodes u
 +     ​consider moving towards each of it's neighbors community,
 +     move it towards the community bringing the largest positive increase in modularity
 +</​code>​
 +
 +Now, the critical step in the algorithm is to decide whether to change a node from a community $C$ to a community $C'$ according to the gain in modularity we may expect from such a move. Now, the move may be simulated by first taking the node //out// of community $C$ and then //into// community $C'$. The corresponding computation can be easily tracked by observing that merging an isolated node $u$ into a community $C$ induces a gain:
 +
 +$$
 +\frac{1}{|E|} \big( \deg_C(u) - \deg_G(u) \sum_{v \in C} \frac{\deg_G(v)}{|E|} ​ \big)
 +$$
 +
 +where $deg_C(u) = N_G(u) \cap C$ denotes how many neighbors $u$ has in $C$. Note also that all these identities hold if we consider edge weights, replacing standard node degree by their weighted degree, and $|A|$ with the sum of all weights of edges $\sum_{e \in E} \omega(e)$.
 +
 +
 +=== Newman and Girvan & Chiricota et al. algorithm, modularity measure (Q, MQ), betweenness centrality ===
 +
 +Another popular approach is to use statistics on edges or nodes in the grpah in order to identify edges acting as //bridges// between communities. We may expect that by removing these bridges, the graph will split up into separate communities. Different statistics may be used to perform the search. [[network_data|The section concerned with node and edge metrics]] gives a long list of possible statistics.
 +
 +  * The //Jaccard index//. This index was originally designed to evaluate set similarities. Given any two set s$A$, $B$, their Jaccard similarities is:
 +
 +$$
 +J(A, b) = \frac{|A \cap B|}{|A \cup B|}
 +$$
 +
 +Observe that this ratio can be evaluated using scalar products. Assume both sets are subsets of a universal set $U$, $A, B \subset U$. We may then write sets as bit vectors ${\bf a} = (a_u)_{u \in U}$ and ${\bf b} = (b_u)_{u \in U}$ (where $a_x, b_y = 0$ or 1 depending on whether $u \in A$ or $u \in B$). The numerator then equals $|A \cap B| = \langle {\bf a}, {\bf b} \rangle$. A similar expression can be derived for the denominator $|A \cup B| = \langle {\bf a}, {\bf a} \rangle + \langle {\bf b}, {\bf b} \rangle - \langle {\bf a}, {\bf b} \rangle$. Observe that $\|{\bf a}\|^2 = \langle {\bf a}, {\bf a} \rangle$ so the ratio may be simply written as:
 +
 +$$
 +J(A, b) = \frac{\langle {\bf a}, {\bf b} \rangle}{\|{\bf a}\|^2 + \|{\bf b}\|^2 - \langle {\bf a}, {\bf b} \rangle}
 +$$
 +
 +  * The //cosinus similarity//​ (of two sets or vectors) follows a similar line and is defined as:
 +
 +$$
 +cos(A, B) = \frac{\langle {\bf a}, {\bf b} \rangle}{\|{\bf a}\|^2 \cdot \|{\bf b}\|^2}
 +$$
 +
 +  * //Edge strength//
 +
 +{{ :​histo-imdb-1000stepnoaglo.dat.jpg?​nolink&​300| }} Now, these statistics may all be used as an indicator of how much cohesion an edge brings into its neighborhood. Edges with values are expected to sit in densely connected neighborhood,​ while edges with low values maybe suspected to act bridges. A simple idea then consists in //filtering out edges with low values// and take as communities the remaining connected components.
 +
 +Thus, there is an application associating a graph clustering ${\bf C}_\tau = (C_1, \ldots, C_k)$ to each possible threshold value $\tau \in [0, a]$, obtained from $G$ by filtering out edges having a value below $\tau$. If in turn we compute the modularity of the resulting clustering, we then get a curve allowing us to select the best possible threshold, and hence a best candidate clustering. ​
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/hierarchical_graph_clustering.txt · Last modified: 2012/11/22 15:38 by melancon