baldassarri baronchelli barrat caglioti castellano cattuto complexity data_compression dattoli evolutionary_dynamics granular_media granular_media herrmann information_theory kreyon language_dynamics loreto mari mukherjee petri pietronero puglisi quantum_optics self_organization servedio statistical_physics techno_social_systems tria zapperi zippers
2004 |
Radicchi, Filippo; Castellano, Claudio; Cecconi, Federico; Loreto, Vittorio; Parisi, Domenico Defining and identifying communities in networks Journal Article PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 101 , pp. 2658–2663, 2004. Abstract | Links | BibTeX | Tag: castellano, cecconi, complex_networks, loreto, parisi, radicchi @article{b, title = {Defining and identifying communities in networks}, author = {Filippo Radicchi and Claudio Castellano and Federico Cecconi and Vittorio Loreto and Domenico Parisi}, url = {http://www.scopus.com/inward/record.url?eid=2-s2.0-1542357701&partnerID=65&md5=38349a61be5998bacd3283c61c6abce6 http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=000220065300004&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=0c7ff228ccbaaa74236f48834a34396a}, year = {2004}, date = {2004-01-01}, journal = {PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA}, volume = {101}, pages = {2658--2663}, publisher = {National Academy of Sciences:2101 Constitution Avenue Northwest:Washington, DC 20418:(877)314-2253, (615)377-3322, EMAIL: subspnas@nas.edu, INTERNET: http://www.pnas.org, Fax: (615)377-0525}, 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 and protein networks), or technological problems (optimization of large infrastructures). Several types of algorithms exist for revealing the community structure in networks, but a general and quantitative definition of community is not implemented in the algorithms, leading to an intrinsic difficulty in the interpretation of the results without any additional nontopological information. In this article we deal with this problem by showing how quantitative definitions of community 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 local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability. The algorithm is tested on artificial and real-world graphs. In particular, we show how the algorithm applies to a network of scientific collaborations, which, for its size, cannot be attacked with the usual methods. This type of local algorithm could open the way to applications to large-scale technological and biological systems.}, keywords = {castellano, cecconi, complex_networks, loreto, parisi, radicchi}, pubstate = {published}, tppubtype = {article} } 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 and protein networks), or technological problems (optimization of large infrastructures). Several types of algorithms exist for revealing the community structure in networks, but a general and quantitative definition of community is not implemented in the algorithms, leading to an intrinsic difficulty in the interpretation of the results without any additional nontopological information. In this article we deal with this problem by showing how quantitative definitions of community 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 local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability. The algorithm is tested on artificial and real-world graphs. In particular, we show how the algorithm applies to a network of scientific collaborations, which, for its size, cannot be attacked with the usual methods. This type of local algorithm could open the way to applications to large-scale technological and biological systems. |
Castellano, Claudio; Federico cecconi, ; Loreto, Vittorio; Parisi, Domenico; Radicchi, Filippo Self-contained algorithms to detect communities in networks Journal Article THE EUROPEAN PHYSICAL JOURNAL. B, CONDENSED MATTER PHYSICS, 38 , pp. 311–319, 2004. Links | BibTeX | Tag: castellano, cecconi, complex_networks, loreto, parisi, radicchi @article{b, title = {Self-contained algorithms to detect communities in networks}, author = {Claudio Castellano and Federico cecconi, and Vittorio Loreto and Domenico Parisi and Filippo Radicchi}, url = {http://www.scopus.com/inward/record.url?eid=2-s2.0-2942534881&partnerID=65&md5=95c1d25779e19f22e6eacd483a47ec2b http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=000221447300024&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=0c7ff228ccbaaa74236f48834a34396a}, year = {2004}, date = {2004-01-01}, journal = {THE EUROPEAN PHYSICAL JOURNAL. B, CONDENSED MATTER PHYSICS}, volume = {38}, pages = {311--319}, publisher = {EDP Sciences, Springer Verlag Germany}, keywords = {castellano, cecconi, complex_networks, loreto, parisi, radicchi}, pubstate = {published}, tppubtype = {article} } |
Other subjects
