Multi-scale Community Detection using Stability

Whether biological, social or technical, many real systems are represented as networks whose structure can be very informative regarding the original system’s organisation. In this respect the field of community detection has received a lot of attention in the past decade. Most of the approaches rely on the notion of modularity to assess the quality of a partition and use this measure as an optimisation criterion. Recently stability was introduced as

a new partition quality measure encompassing former partition quality measures such as modularity. The work presented here assesses stability as an optimisation criterion in a greedy approach similar to modularity optimisation techniques and enables multi-scale analysis using Markov time as resolution parameter. The method is validated and compared with other popular approaches against synthetic and various real data networks and the results show that the method enables accurate multi-scale network analysis. 1 INTRODUCTION In biology, sociology, engineering and beyond, many systems are represented and studied as graphs, or net- works (e.g. protein networks, social networks, web). In the past decade the field of community detection at- tracted a lot of interest considering community struc- tures as important features of real-world networks (Fortunato, 2010). Given a network of any kind, looking for communities refers to finding groups of nodes that are more densely connected internally than with the rest of the network. The concept considers the inhomogeneity within the connections between nodes to derive a partitioning of the network. As op- posed to clustering methods which commonly involve a given number of clusters, communities are usually unknown, can be of unequal size and density and of- ten have hierarchies (Fortunato, 2010). Finding such partitioning can provide information about the under- lying structure of a network and its functioning. It can also be used as a more compact representation of the network, for instance for visualisations. Detecting community structure in networks can be split into two subtasks: how to partition a graph, and how to measure the quality of a partition. The latter is commonly done using modularity (Newman and Girvan, 2004). Partitioning graphs is an NP- hard task (Fortunato, 2010) and heuristics based algorithms have thus been devised to reduce the complexity while still providing acceptable solutions. Considering the size of some real-world networks much effort is put into finding efficient algorithms able to deal with larger and larger networks such as modularity optimisation methods. However it has been shown that networks often have several levels of organisa- tion (Simon, 1962), leading to different partitions for each level which modularity optimisation alone can- not handle (Fortunato, 2010). Methods have been pro- vided to adapt modularity optimisation to multi-scale (multi-resolution) analysis using a tuning parameter (Reichardt and Bornholdt, 2006; Arenas et al., 2008). Yet the search for a partition quality function that acknowledges the multi-resolution nature...

Website: www.elemartelot.org | Filesize: -
No of Page(s): 10
Download Multi-scale Community Detection using Stability ... - Erwan Le Martelot.pdf