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.
"In general algorithms define communities operationally as what the they finds. A dendrogram, i. e. a community
structure, is always produced by the algorithms down to the level of single nodes, independently from the type
of graph analyzed. This is due to the lack of explicit prescriptions to discriminate between networks that
are actually endowed with a community structure and those that are not. As a consequence, in practical
applications one needs additional, non topological, information on the nature of the network to understand
which of the branches of the tree have a real significance. Without such information it is not clear at all whether
the identification of a community is reliable or not."
---
Domain: scientific collaborations
Task: calculate a dendrogram (the community graph)
Method: effucuebt GN (Girvan & Newman( algorithm based on edge betweenness. Their algorithm allows to be fine-tuned beween acting local or global. To be more efficient they replace the "edge betweenness" by "edge clustering coefficient" which is based on the number of triangles the edge is contained in VS the degree of the incident nodes.
Motto: Älgorithm must include the quantitative community definition"
%0 Generic
%1 citeulike:341233
%A Radicchi, Filippo
%A Castellano, Claudio
%A Cecconi, Federico
%A Loreto, Vittorio
%A Parisi, Domenico
%D 2004
%K folksonomy collaborative communities community identifying
%T Defining and identifying communities in networks
%U http://arxiv.org/abs/cond-mat/0309488
%X 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.
@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.},
added-at = {2007-01-23T16:49:08.000+0100},
author = {Radicchi, Filippo and Castellano, Claudio and Cecconi, Federico and Loreto, Vittorio and Parisi, Domenico},
biburl = {https://www.bibsonomy.org/bibtex/28634d935e0bf4d74a870d5c805612665/domenico79},
citeulike-article-id = {341233},
comment = {"In general algorithms define communities operationally as what the they finds. A dendrogram, i. e. a community
structure, is always produced by the algorithms down to the level of single nodes, independently from the type
of graph analyzed. This is due to the lack of explicit prescriptions to discriminate between networks that
are actually endowed with a community structure and those that are not. As a consequence, in practical
applications one needs additional, non topological, information on the nature of the network to understand
which of the branches of the tree have a real significance. Without such information it is not clear at all whether
the identification of a community is reliable or not."
---
Domain: scientific collaborations
Task: calculate a dendrogram (the community graph)
Method: effucuebt GN (Girvan \& Newman( algorithm based on edge betweenness. Their algorithm allows to be fine-tuned beween acting local or global. To be more efficient they replace the "edge betweenness" by "edge clustering coefficient" which is based on the number of triangles the edge is contained in VS the degree of the incident nodes.
Motto: "Algorithm must include the quantitative community definition"},
eprint = {cond-mat/0309488},
interhash = {6ec9b00862909de405c08db1c9b43d63},
intrahash = {8634d935e0bf4d74a870d5c805612665},
keywords = {folksonomy collaborative communities community identifying},
month = Feb,
priority = {0},
timestamp = {2007-01-23T16:49:08.000+0100},
title = {Defining and identifying communities in networks},
url = {http://arxiv.org/abs/cond-mat/0309488},
year = 2004
}