11 Mar 2009 | Andrea Lancichinetti, Santo Fortunato, János Kertész
This paper presents a novel algorithm for detecting both overlapping and hierarchical community structures in complex networks. The method is based on the local optimization of a fitness function, which identifies natural communities by maximizing the fitness of nodes. The fitness function is defined as $ f_{\mathcal{G}} = \frac{k_{in}^{\mathcal{G}}}{(k_{in}^{\mathcal{G}} + k_{out}^{\mathcal{G}})^{\alpha}} $, where $ k_{in}^{\mathcal{G}} $ and $ k_{out}^{\mathcal{G}} $ are the internal and external degrees of the nodes in a module, and $ \alpha $ is a parameter that controls the size of the communities. The algorithm iteratively builds communities by adding nodes with the highest fitness until no further improvement is possible. The resolution parameter $ \alpha $ allows the method to explore different hierarchical levels of the network.
The algorithm is tested on both real and artificial networks, showing excellent results in identifying overlapping and hierarchical communities. It is particularly effective in detecting communities in networks with a hierarchical structure, where communities are nested within each other. The method also handles overlapping communities, where nodes can belong to multiple communities. The algorithm is computationally efficient and can be applied to large networks.
The paper also discusses the computational complexity of the algorithm, which depends on the size of the communities and their overlaps. The method is shown to have a worst-case computational complexity of $ n^2 \log n $, where $ n $ is the number of nodes in the network. However, for most practical applications, the complexity is much lower, especially when communities are small.
The algorithm is tested on several real-world networks, including social networks, biological networks, and sports networks. The results show that the method accurately identifies the community structure of these networks, even when communities overlap. The method is also compared with other community detection algorithms, such as the clique percolation method, and is shown to perform better in many cases.
The paper concludes that the proposed method provides a general framework for detecting both overlapping and hierarchical community structures in complex networks. The method is flexible and can be adapted to different types of networks, and it has the potential to be applied to a wide range of real-world problems. The algorithm is also capable of quantifying the participation of overlapping nodes in their communities, which is an important aspect of understanding the structure of complex networks.This paper presents a novel algorithm for detecting both overlapping and hierarchical community structures in complex networks. The method is based on the local optimization of a fitness function, which identifies natural communities by maximizing the fitness of nodes. The fitness function is defined as $ f_{\mathcal{G}} = \frac{k_{in}^{\mathcal{G}}}{(k_{in}^{\mathcal{G}} + k_{out}^{\mathcal{G}})^{\alpha}} $, where $ k_{in}^{\mathcal{G}} $ and $ k_{out}^{\mathcal{G}} $ are the internal and external degrees of the nodes in a module, and $ \alpha $ is a parameter that controls the size of the communities. The algorithm iteratively builds communities by adding nodes with the highest fitness until no further improvement is possible. The resolution parameter $ \alpha $ allows the method to explore different hierarchical levels of the network.
The algorithm is tested on both real and artificial networks, showing excellent results in identifying overlapping and hierarchical communities. It is particularly effective in detecting communities in networks with a hierarchical structure, where communities are nested within each other. The method also handles overlapping communities, where nodes can belong to multiple communities. The algorithm is computationally efficient and can be applied to large networks.
The paper also discusses the computational complexity of the algorithm, which depends on the size of the communities and their overlaps. The method is shown to have a worst-case computational complexity of $ n^2 \log n $, where $ n $ is the number of nodes in the network. However, for most practical applications, the complexity is much lower, especially when communities are small.
The algorithm is tested on several real-world networks, including social networks, biological networks, and sports networks. The results show that the method accurately identifies the community structure of these networks, even when communities overlap. The method is also compared with other community detection algorithms, such as the clique percolation method, and is shown to perform better in many cases.
The paper concludes that the proposed method provides a general framework for detecting both overlapping and hierarchical community structures in complex networks. The method is flexible and can be adapted to different types of networks, and it has the potential to be applied to a wide range of real-world problems. The algorithm is also capable of quantifying the participation of overlapping nodes in their communities, which is an important aspect of understanding the structure of complex networks.