Shifting niches for community structure detection

Corrado Grappiolo, Julian Togelius, Georgios N. Yannakakis

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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 languageEnglish (US)
    Title of host publication2013 IEEE Congress on Evolutionary Computation, CEC 2013
    Number of pages8
    StatePublished - 2013
    Event2013 IEEE Congress on Evolutionary Computation, CEC 2013 - Cancun, Mexico
    Duration: Jun 20 2013Jun 23 2013

    Publication series

    Name2013 IEEE Congress on Evolutionary Computation, CEC 2013


    Other2013 IEEE Congress on Evolutionary Computation, CEC 2013


    • Community Structures
    • Complete Weighted Networks
    • Evolutionary Computation
    • Niching
    • Sparse Graphs

    ASJC Scopus subject areas

    • Computational Theory and Mathematics
    • Theoretical Computer Science


    Dive into the research topics of 'Shifting niches for community structure detection'. Together they form a unique fingerprint.

    Cite this