Defining and identifying communities in networks

Defining and identifying communities in networks

27 Feb 2004 | Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, Domenico Parisi
This paper presents a new approach to identifying community structures in networks, addressing two key challenges: the lack of a quantitative definition of community in existing algorithms and the computational inefficiency of current methods. The authors propose a self-contained algorithm that uses a quantitative definition of community to determine whether subgraphs are actual communities. They also introduce a new local algorithm that is significantly faster than existing methods while maintaining similar accuracy. The paper discusses two definitions of community: a strong definition, where each node in a community has more connections within the community than outside, and a weak definition, where the sum of internal connections exceeds the sum of external connections. These definitions are used to evaluate the results of the GN algorithm, which is known for its accuracy but is computationally expensive. The authors propose a new divisive algorithm that uses local quantities, such as the edge clustering coefficient, to identify communities. This algorithm is much faster than the GN algorithm and performs well in both strong and weak definitions of community. It is tested on artificial and real-world networks, including a large network of scientific collaborations, where it successfully identifies communities. The new algorithm is compared to the GN algorithm on an artificial graph with four communities. It performs as well as the GN algorithm in the strong definition and is more accurate in the weak definition. The algorithm is also tested on a network of college football teams, where it produces results similar to the GN algorithm. The paper also discusses the computational efficiency of the new algorithm, showing that it is significantly faster than the GN algorithm. The algorithm is able to process large networks efficiently, making it suitable for applications in large-scale technological and biological systems. The authors conclude that the new algorithm provides a more efficient and accurate method for identifying community structures in networks. They emphasize the importance of a quantitative definition of community and the need for efficient algorithms to analyze large networks. The paper also highlights the potential applications of the new algorithm in various fields, including social, biological, and technological networks.This paper presents a new approach to identifying community structures in networks, addressing two key challenges: the lack of a quantitative definition of community in existing algorithms and the computational inefficiency of current methods. The authors propose a self-contained algorithm that uses a quantitative definition of community to determine whether subgraphs are actual communities. They also introduce a new local algorithm that is significantly faster than existing methods while maintaining similar accuracy. The paper discusses two definitions of community: a strong definition, where each node in a community has more connections within the community than outside, and a weak definition, where the sum of internal connections exceeds the sum of external connections. These definitions are used to evaluate the results of the GN algorithm, which is known for its accuracy but is computationally expensive. The authors propose a new divisive algorithm that uses local quantities, such as the edge clustering coefficient, to identify communities. This algorithm is much faster than the GN algorithm and performs well in both strong and weak definitions of community. It is tested on artificial and real-world networks, including a large network of scientific collaborations, where it successfully identifies communities. The new algorithm is compared to the GN algorithm on an artificial graph with four communities. It performs as well as the GN algorithm in the strong definition and is more accurate in the weak definition. The algorithm is also tested on a network of college football teams, where it produces results similar to the GN algorithm. The paper also discusses the computational efficiency of the new algorithm, showing that it is significantly faster than the GN algorithm. The algorithm is able to process large networks efficiently, making it suitable for applications in large-scale technological and biological systems. The authors conclude that the new algorithm provides a more efficient and accurate method for identifying community structures in networks. They emphasize the importance of a quantitative definition of community and the need for efficient algorithms to analyze large networks. The paper also highlights the potential applications of the new algorithm in various fields, including social, biological, and technological networks.
Reach us at info@study.space
Understanding Defining and identifying communities in networks.