Doubly-stochastic scaling of adjacency matrices for community detection (Workshop on Graphs, Networks, and their Applications, Moscou, 2019)
Résumé
Community detection in networks consists in finding groups of individuals such that a same group contains ele-ments that are similar (behave similarly, share common features, ...), whereas elements of two different groups aredifferent (have different features, ...). Various modularity measures have been designed to evaluate the correctnessof a community structure for a given network. Graphs and their adjacency matrices are a key tool in the context ofcommunity detection: if a newtork has a community structure, we should be able to symmetrically permute rows andcolumns of the adjacency matrix to observe dense blocks along its diagonal.Finding a doubly-stochastic scaling on a positive matrixM∈Rn×nmeans findingE,F∈Rn×ntwo diagonalmatrices so that all the row and the column sums ofEMFare equal to one. This scaling has properties that mayhighlight the community structure of a network:•It leverages small and big communities by giving to the first higher edge weights. This is an interesting propertybecause small communities are generally more difficult to detect.•If a network has a flow—i.e.an imbalance between edges that enter and leave a community—the doubly-stochastic scaling erases the imbalance and highlights the community.•The scaled graph is 1-regular—all its node degrees are 1. This is interesting as some modularity measures areidentical when applied onk-regular graphs [CC].In our study, we hence use a doubly-stochastic scaling of the adjacency matrix as a preprocessing for the Louvain’salgorithm [louvain]. This algorithm is a heuristic to maximise Newman and Girvan’s modularity [NGmodu], and ithas been proved to be one of the best community detection algorithms in the recent study [zhang2016]. We usethe generic version proposed in [generalLouvain] that allows the user to maximise some other modularities. Toshow the added value of the doubly-stochastic scaling, we compare the results of the algorithm on the raw and thescaled graph by applying it on some well-known benchmark test cases [LFRBenchmark,LFBenchmark]. Forfurther comparisons we also use it with different modularity measures to provide some qualitative remarks about theefficiency of these measures.