15 Jun 2005 | Gergely Palla†‡, Imre Derényi‡, Illés Farkas†, and Tamás Vicsek†‡
The paper by Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek introduces a method to analyze the overlapping community structure in complex networks, which is crucial for understanding the structural and functional properties of networks. Traditional methods for large networks often fail to capture the overlapping and nested nature of real-world networks, where nodes often belong to multiple communities. The authors define a *k-clique-community* as a union of all *k-cliques* (fully connected subgraphs) that can be reached from each other through adjacent $k$-cliques. They develop an efficient algorithm to identify these communities and explore their statistical properties, including the size, degree, overlap, and membership number of communities. The study demonstrates that the distributions of these quantities reveal universal features of networks, such as power-law distributions for community size and degree, and non-trivial correlations and scaling properties of the web of communities. The method is applied to social networks, word association networks, and protein interaction networks, showing its effectiveness in uncovering the modular structure of complex systems. The authors also highlight the importance of overlaps between communities and the hierarchical nature of these networks, providing a tool to predict the impact of removing a unit on the network's modular structure.The paper by Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek introduces a method to analyze the overlapping community structure in complex networks, which is crucial for understanding the structural and functional properties of networks. Traditional methods for large networks often fail to capture the overlapping and nested nature of real-world networks, where nodes often belong to multiple communities. The authors define a *k-clique-community* as a union of all *k-cliques* (fully connected subgraphs) that can be reached from each other through adjacent $k$-cliques. They develop an efficient algorithm to identify these communities and explore their statistical properties, including the size, degree, overlap, and membership number of communities. The study demonstrates that the distributions of these quantities reveal universal features of networks, such as power-law distributions for community size and degree, and non-trivial correlations and scaling properties of the web of communities. The method is applied to social networks, word association networks, and protein interaction networks, showing its effectiveness in uncovering the modular structure of complex systems. The authors also highlight the importance of overlaps between communities and the hierarchical nature of these networks, providing a tool to predict the impact of removing a unit on the network's modular structure.