ommunity detection and analysis is an important methodology for
understanding the organization of various real-world networks and has
applications in problems as diverse as consensus formation in social
communities or the identification of functional modules in biochemical
networks. Currently used algorithms that identify the community structures in
large-scale real-world networks require a priori information such as the number
and sizes of communities or are computationally expensive. In this paper we
investigate a simple label propagation algorithm that uses the network
structure alone as its guide and requires neither optimization of a pre-defined
objective function nor prior information about the communities. In our
algorithm every node is initialized with a unique label and at every step each
node adopts the label that most of its neighbors currently have. In this
iterative process densely connected groups of nodes form a consensus on a
unique label to form communities. We validate the algorithm by applying it to
networks whose community structures are known. We also demonstrate that the
algorithm takes an almost linear time and hence it is computationally less
expensive than what was possible so far.
%0 Generic
%1 Raghavan2007Near
%A Raghavan, Usha N.
%A Albert, Reka
%A Kumara, Soundar
%D 2007
%K community graph
%T Near linear time algorithm to detect community structures in large-scale networks
%U http://arxiv.org/abs/0709.2938
%X ommunity detection and analysis is an important methodology for
understanding the organization of various real-world networks and has
applications in problems as diverse as consensus formation in social
communities or the identification of functional modules in biochemical
networks. Currently used algorithms that identify the community structures in
large-scale real-world networks require a priori information such as the number
and sizes of communities or are computationally expensive. In this paper we
investigate a simple label propagation algorithm that uses the network
structure alone as its guide and requires neither optimization of a pre-defined
objective function nor prior information about the communities. In our
algorithm every node is initialized with a unique label and at every step each
node adopts the label that most of its neighbors currently have. In this
iterative process densely connected groups of nodes form a consensus on a
unique label to form communities. We validate the algorithm by applying it to
networks whose community structures are known. We also demonstrate that the
algorithm takes an almost linear time and hence it is computationally less
expensive than what was possible so far.
@misc{Raghavan2007Near,
abstract = {ommunity detection and analysis is an important methodology for
understanding the organization of various real-world networks and has
applications in problems as diverse as consensus formation in social
communities or the identification of functional modules in biochemical
networks. Currently used algorithms that identify the community structures in
large-scale real-world networks require a priori information such as the number
and sizes of communities or are computationally expensive. In this paper we
investigate a simple label propagation algorithm that uses the network
structure alone as its guide and requires neither optimization of a pre-defined
objective function nor prior information about the communities. In our
algorithm every node is initialized with a unique label and at every step each
node adopts the label that most of its neighbors currently have. In this
iterative process densely connected groups of nodes form a consensus on a
unique label to form communities. We validate the algorithm by applying it to
networks whose community structures are known. We also demonstrate that the
algorithm takes an almost linear time and hence it is computationally less
expensive than what was possible so far.},
added-at = {2012-12-15T01:08:53.000+0100},
archiveprefix = {arXiv},
author = {Raghavan, Usha N. and Albert, Reka and Kumara, Soundar},
biburl = {https://www.bibsonomy.org/bibtex/20734aca3f3ab7d285662398d24627044/kibanov},
citeulike-article-id = {1688934},
citeulike-linkout-0 = {http://arxiv.org/abs/0709.2938},
citeulike-linkout-1 = {http://arxiv.org/pdf/0709.2938},
eprint = {0709.2938},
interhash = {195683f4eff68a82d2c8f83a37a0fb78},
intrahash = {0734aca3f3ab7d285662398d24627044},
keywords = {community graph},
month = sep,
posted-at = {2007-09-25 16:04:07},
priority = {2},
timestamp = {2012-12-15T01:08:53.000+0100},
title = {Near linear time algorithm to detect community structures in large-scale networks},
url = {http://arxiv.org/abs/0709.2938},
year = 2007
}