ﻻ يوجد ملخص باللغة العربية
Community structure is an important property of complex networks. An automatic discovery of such structure is a fundamental task in many disciplines, including sociology, biology, engineering, and computer science. Recently, several community discovery algorithms have been proposed based on the optimization of a quantity called modularity (Q). However, the problem of modularity optimization is NP-hard, and the existing approaches often suffer from prohibitively long running time or poor quality. Furthermore, it has been recently pointed out that algorithms based on optimizing Q will have a resolution limit, i.e., communities below a certain scale may not be detected. In this research, we first propose an efficient heuristic algorithm, Qcut, which combines spectral graph partitioning and local search to optimize Q. Using both synthetic and real networks, we show that Qcut can find higher modularities and is more scalable than the existing algorithms. Furthermore, using Qcut as an essential component, we propose a recursive algorithm, HQcut, to solve the resolution limit problem. We show that HQcut can successfully detect communities at a much finer scale and with a higher accuracy than the existing algorithms. Finally, we apply Qcut and HQcut to study a protein-protein interaction network, and show that the combination of the two algorithms can reveal interesting biological results that may be otherwise undetectable.
To understand the formation, evolution, and function of complex systems, it is crucial to understand the internal organization of their interaction networks. Partly due to the impossibility of visualizing large complex networks, resolving network str
The concept of community detection has long been used as a key device for handling the mesoscale structures in networks. Suitably conducted community detection reveals various embedded informative substructures of network topology. However, regarding
We investigate the impact of borders on the topology of spatially embedded networks. Indeed territorial subdivisions and geographical borders significantly hamper the geographical span of networks thus playing a key role in the formation of network c
The study of community structure has been a hot topic of research over the last years. But, while successfully applied in several areas, the concept lacks of a general and precise notion. Facts like the hierarchical structure and heterogeneity of com
Social impacts and degrees of organization inherent to opinion formation for interacting agents on networks present interesting questions of general interest from physics to sociology. We present a quantitative analysis of a case implying an evolving