Shifting niches for community structure detection

Corrado Grappiolo; Julian Togelius; Georgios N. Yannakakis

doi:10.1109/CEC.2013.6557560

Shifting niches for community structure detection

Corrado Grappiolo, Julian Togelius, Georgios N. Yannakakis

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present a new evolutionary algorithm for community structure detection in both undirected and unweighted (sparse) graphs and fully connected weighted digraphs (complete networks). Previous investigations have found that, although evolutionary computation can identify community structure in complete networks, this approach seems to scale badly due to solutions with the wrong number of communities dominating the population. The new algorithm is based on a niching model, where separate compartments of the population contain candidate solutions with different numbers of communities. We experimentally compare the new algorithm to the well-known algorithms of Pizzuti and Tasgin, and find that we outperform those algorithms for sparse graphs under some conditions, and drastically outperform them on complete networks under all tested conditions.

Original language	English (US)
Title of host publication	2013 IEEE Congress on Evolutionary Computation, CEC 2013
Pages	111-118
Number of pages	8
DOIs	https://doi.org/10.1109/CEC.2013.6557560
State	Published - 2013
Event	2013 IEEE Congress on Evolutionary Computation, CEC 2013 - Cancun, Mexico Duration: Jun 20 2013 → Jun 23 2013

Publication series

Name	2013 IEEE Congress on Evolutionary Computation, CEC 2013

Other

Other	2013 IEEE Congress on Evolutionary Computation, CEC 2013
Country/Territory	Mexico
City	Cancun
Period	6/20/13 → 6/23/13

Keywords

Community Structures
Complete Weighted Networks
Evolutionary Computation
Niching
Sparse Graphs

ASJC Scopus subject areas

Computational Theory and Mathematics
Theoretical Computer Science

Access to Document

10.1109/CEC.2013.6557560

Cite this

@inproceedings{97537f27001a428688fa8ab54ff18d27,

title = "Shifting niches for community structure detection",

abstract = "We present a new evolutionary algorithm for community structure detection in both undirected and unweighted (sparse) graphs and fully connected weighted digraphs (complete networks). Previous investigations have found that, although evolutionary computation can identify community structure in complete networks, this approach seems to scale badly due to solutions with the wrong number of communities dominating the population. The new algorithm is based on a niching model, where separate compartments of the population contain candidate solutions with different numbers of communities. We experimentally compare the new algorithm to the well-known algorithms of Pizzuti and Tasgin, and find that we outperform those algorithms for sparse graphs under some conditions, and drastically outperform them on complete networks under all tested conditions.",

keywords = "Community Structures, Complete Weighted Networks, Evolutionary Computation, Niching, Sparse Graphs",

author = "Corrado Grappiolo and Julian Togelius and Yannakakis, {Georgios N.}",

year = "2013",

doi = "10.1109/CEC.2013.6557560",

language = "English (US)",

isbn = "9781479904549",

series = "2013 IEEE Congress on Evolutionary Computation, CEC 2013",

pages = "111--118",

booktitle = "2013 IEEE Congress on Evolutionary Computation, CEC 2013",

}

TY - GEN

T1 - Shifting niches for community structure detection

AU - Grappiolo, Corrado

AU - Togelius, Julian

AU - Yannakakis, Georgios N.

PY - 2013

Y1 - 2013

N2 - We present a new evolutionary algorithm for community structure detection in both undirected and unweighted (sparse) graphs and fully connected weighted digraphs (complete networks). Previous investigations have found that, although evolutionary computation can identify community structure in complete networks, this approach seems to scale badly due to solutions with the wrong number of communities dominating the population. The new algorithm is based on a niching model, where separate compartments of the population contain candidate solutions with different numbers of communities. We experimentally compare the new algorithm to the well-known algorithms of Pizzuti and Tasgin, and find that we outperform those algorithms for sparse graphs under some conditions, and drastically outperform them on complete networks under all tested conditions.

AB - We present a new evolutionary algorithm for community structure detection in both undirected and unweighted (sparse) graphs and fully connected weighted digraphs (complete networks). Previous investigations have found that, although evolutionary computation can identify community structure in complete networks, this approach seems to scale badly due to solutions with the wrong number of communities dominating the population. The new algorithm is based on a niching model, where separate compartments of the population contain candidate solutions with different numbers of communities. We experimentally compare the new algorithm to the well-known algorithms of Pizzuti and Tasgin, and find that we outperform those algorithms for sparse graphs under some conditions, and drastically outperform them on complete networks under all tested conditions.

KW - Community Structures

KW - Complete Weighted Networks

KW - Evolutionary Computation

KW - Niching

KW - Sparse Graphs

UR - http://www.scopus.com/inward/record.url?scp=84881578305&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84881578305&partnerID=8YFLogxK

U2 - 10.1109/CEC.2013.6557560

DO - 10.1109/CEC.2013.6557560

M3 - Conference contribution

AN - SCOPUS:84881578305

SN - 9781479904549

T3 - 2013 IEEE Congress on Evolutionary Computation, CEC 2013

SP - 111

EP - 118

BT - 2013 IEEE Congress on Evolutionary Computation, CEC 2013

T2 - 2013 IEEE Congress on Evolutionary Computation, CEC 2013

Y2 - 20 June 2013 through 23 June 2013

ER -

Shifting niches for community structure detection

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this