Multiscale community detection using markov dynamics

M.S. University of Hawaii at Manoa 2014.Includes bibliographical references.Complex networks is an interdisciplinary research area getting attention from a variety of disciplines including sociology, biology, and computer science. It studies the properties of complex systems that may have many functional or structural subunits. Community detection algorithms are one of the major approaches to analyse complex networks by finding these intermediate-level subunits called modules or communities. Furthermore, some networks may have multilevel or overlapping community structures. InfoMap is one of the best performing algorithms that finds the communities of a network by compressing the flow of information [25, 17]. In this work, we introduced Markov Dynamics to the InfoMap in order to detect communities at multiscales. Although Markov Dynamics have been applied to the InfoMap for undirected networks before [28], this was the first application of Markov Dynamics to the InfoMap for directed networks. Additionally, we added a feature to detect overlapping nodes using the compression of flow on the boundary nodes, similar to the approach described in [9] before. These two features were combined into the InfoMap for directed networks. We evaluated these two features on synthetic networks and benchmark graphs. We have comparable results with the Hierarchical InfoMap [26] for multilevel community detection, but improvement in runtime is needed. We evaluated the overlapping feature by its own ability, and found that it can detect overlapping nodes for networks with sparse overlaps