User Tools

Site Tools


hierarchical_graph_clustering

Visual Analytics Course

Graph clustering

Louvain fast community unfolding (hierarchical clustering) algorithm

The main reference for this algorithm is a paper by 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 equipped with a clustering .

(Mancoridis modularity)

where denotes the number of edges connecting clusters and .

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. thus varies in the [-1, 1] interval, with when all clusters all (unconnected) cliques, while when cliques are fully connected and edgeless. When considering clustering with no isolated nodes (clusters of size 1), can be shown to have mean value 0 and be estimated by a gaussian distribution.

(Newman's modularity)

Observe that is the fraction of edges that are internal to clusters, while is the fraction of edges that connect to cluster . The rationale behind is quite clear: it measures just how 'far' is from begin random (edges being dispatched randomly between clusters). Indeed, write the adjacency matrix of the graph as . The probability that nodes and are connected in , respecting node degrees, is . Hence, may alternatively be defined as:

The algorithm runs in two phases. Phase 1 seeks at optimizing modularity using a greedy approach:

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

Now, the critical step in the algorithm is to decide whether to change a node from a community to a community 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 and then into community . The corresponding computation can be easily tracked by observing that merging an isolated node into a community induces a gain:

where denotes how many neighbors has in . Note also that all these identities hold if we consider edge weights, replacing standard node degree by their weighted degree, and with the sum of all weights of edges .

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. 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, , their Jaccard similarities is:

Observe that this ratio can be evaluated using scalar products. Assume both sets are subsets of a universal set , . We may then write sets as bit vectors and (where or 1 depending on whether or ). The numerator then equals . A similar expression can be derived for the denominator . Observe that so the ratio may be simply written as:

  • The cosinus similarity (of two sets or vectors) follows a similar line and is defined as:
  • Edge strength

 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 to each possible threshold value , obtained from by filtering out edges having a value below . 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