Defining and identifying communities in networks

@misc{citeulike:341233, abstract = {The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic, cellular or protein networks) or technological problems (optimization of large infrastructures). Several types of algorithm exist for revealing the community structure in networks, but a general and quantitative definition of community is still lacking, leading to an intrinsic difficulty in the interpretation of the results of the algorithms without any additional non-topological information. In this paper we face this problem by introducing two quantitative definitions of community and by showing how they are implemented in practice in the existing algorithms. In this way the algorithms for the identification of the community structure become fully self-contained. Furthermore, we propose a new local algorithm to detect communities which outperforms the existing algorithms with respect to the computational cost, keeping the same level of reliability. The new algorithm is tested on artificial and real-world graphs. In particular we show the application of the new algorithm to a network of scientific collaborations, which, for its size, can not be attacked with the usual methods. This new class of local algorithms could open the way to applications to large-scale technological and biological applications.}, author = {Radicchi, Filippo and Castellano, Claudio and Cecconi, Federico and Loreto, Vittorio and Parisi, Domenico }, citeulike-article-id = {341233}, comment = {provides mathematical measures of communities within networks. Important to refer to this when discussing communities of practice, knowledge building, etc.}, eprint = {cond-mat/0309488}, keywords = {algorithms, analysis, collaboation, communities, cscl, eni, fundamental, gmr, graphs, mathematical, measure, networks, social, webreports}, month = {Feb}, posted-at = {2005-11-17 11:26:44}, priority = {4}, title = {Defining and identifying communities in networks}, url = {http://arxiv.org/abs/cond-mat/0309488}, year = {2004} }

TY - ELEC ID - citeulike:341233 L3 - citeulike-article-id:341233 TI - Defining and identifying communities in networks N2 - The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic, cellular or protein networks) or technological problems (optimization of large infrastructures). Several types of algorithm exist for revealing the community structure in networks, but a general and quantitative definition of community is still lacking, leading to an intrinsic difficulty in the interpretation of the results of the algorithms without any additional non-topological information. In this paper we face this problem by introducing two quantitative definitions of community and by showing how they are implemented in practice in the existing algorithms. In this way the algorithms for the identification of the community structure become fully self-contained. Furthermore, we propose a new local algorithm to detect communities which outperforms the existing algorithms with respect to the computational cost, keeping the same level of reliability. The new algorithm is tested on artificial and real-world graphs. In particular we show the application of the new algorithm to a network of scientific collaborations, which, for its size, can not be attacked with the usual methods. This new class of local algorithms could open the way to applications to large-scale technological and biological applications. KW - algorithms KW - analysis KW - collaboation KW - communities KW - cscl KW - eni KW - fundamental KW - gmr KW - graphs KW - mathematical KW - measure KW - networks KW - social KW - webreports N1 - provides mathematical measures of communities within networks. Important to refer to this when discussing communities of practice, knowledge building, etc. AU - Radicchi, Filippo AU - Castellano, Claudio AU - Cecconi, Federico AU - Loreto, Vittorio AU - Parisi, Domenico PY - 2004/Feb/27/ UR - http://arxiv.org/abs/cond-mat/0309488 ER -