Detecting highly overlapping community structure by greedy clique
expansion
C. Lee, F. Reid, A. McDaid, и N. Hurley. Workshop on Social Network Mining and Analysis, (2010)cite arxiv:1002.1827
Comment: 10 pages, 7 Figures. Implementation source and binaries available at
http://sites.google.com/site/greedycliqueexpansion/.
Аннотация
In complex networks it is common for each node to belong to several
communities, implying a highly overlapping community structure. Recent advances
in benchmarking indicate that existing community assignment algorithms that are
capable of detecting overlapping communities perform well only when the extent
of community overlap is kept to modest levels. To overcome this limitation, we
introduce a new community assignment algorithm called Greedy Clique Expansion
(GCE). The algorithm identifies distinct cliques as seeds and expands these
seeds by greedily optimizing a local fitness function. We perform extensive
benchmarks on synthetic data to demonstrate that GCE's good performance is
robust across diverse graph topologies. Significantly, GCE is the only
algorithm to perform well on these synthetic graphs, in which every node
belongs to multiple communities. Furthermore, when put to the task of
identifying functional modules in protein interaction data, and college dorm
assignments in Facebook friendship data, we find that GCE performs
competitively.
Описание
[1002.1827] Detecting highly overlapping community structure by greedy clique expansion
%0 Conference Paper
%1 Lee2010
%A Lee, Conrad
%A Reid, Fergal
%A McDaid, Aaron
%A Hurley, Neil
%B Workshop on Social Network Mining and Analysis
%D 2010
%K 2010 cliques seminar sna
%T Detecting highly overlapping community structure by greedy clique
expansion
%U http://arxiv.org/abs/1002.1827
%X In complex networks it is common for each node to belong to several
communities, implying a highly overlapping community structure. Recent advances
in benchmarking indicate that existing community assignment algorithms that are
capable of detecting overlapping communities perform well only when the extent
of community overlap is kept to modest levels. To overcome this limitation, we
introduce a new community assignment algorithm called Greedy Clique Expansion
(GCE). The algorithm identifies distinct cliques as seeds and expands these
seeds by greedily optimizing a local fitness function. We perform extensive
benchmarks on synthetic data to demonstrate that GCE's good performance is
robust across diverse graph topologies. Significantly, GCE is the only
algorithm to perform well on these synthetic graphs, in which every node
belongs to multiple communities. Furthermore, when put to the task of
identifying functional modules in protein interaction data, and college dorm
assignments in Facebook friendship data, we find that GCE performs
competitively.
@inproceedings{Lee2010,
abstract = { In complex networks it is common for each node to belong to several
communities, implying a highly overlapping community structure. Recent advances
in benchmarking indicate that existing community assignment algorithms that are
capable of detecting overlapping communities perform well only when the extent
of community overlap is kept to modest levels. To overcome this limitation, we
introduce a new community assignment algorithm called Greedy Clique Expansion
(GCE). The algorithm identifies distinct cliques as seeds and expands these
seeds by greedily optimizing a local fitness function. We perform extensive
benchmarks on synthetic data to demonstrate that GCE's good performance is
robust across diverse graph topologies. Significantly, GCE is the only
algorithm to perform well on these synthetic graphs, in which every node
belongs to multiple communities. Furthermore, when put to the task of
identifying functional modules in protein interaction data, and college dorm
assignments in Facebook friendship data, we find that GCE performs
competitively.
},
added-at = {2010-09-20T10:26:10.000+0200},
author = {Lee, Conrad and Reid, Fergal and McDaid, Aaron and Hurley, Neil},
biburl = {https://www.bibsonomy.org/bibtex/2569cc01db5a01c1d8d480b9a3c52d910/beate},
booktitle = {Workshop on Social Network Mining and Analysis},
description = {[1002.1827] Detecting highly overlapping community structure by greedy clique expansion},
interhash = {c6547a1813b764cfd58fb4bcd53487d5},
intrahash = {569cc01db5a01c1d8d480b9a3c52d910},
keywords = {2010 cliques seminar sna},
note = {cite arxiv:1002.1827
Comment: 10 pages, 7 Figures. Implementation source and binaries available at
http://sites.google.com/site/greedycliqueexpansion/},
timestamp = {2010-09-20T10:26:10.000+0200},
title = {Detecting highly overlapping community structure by greedy clique
expansion},
url = {http://arxiv.org/abs/1002.1827},
year = 2010
}