Abstract

The network community detection problem consists in identifying groups of nodes that are more densely connected to each other than to the rest of the network. The lack of a formal definition for the notion of community led to the design of various solution concepts and computational approaches to this problem, among which those based on optimization and, more recently, on game theory, received a special attention from the heuristic community. The former ones define the community structure as an optimum value of a fitness function, while the latter as a game equilibrium. Both are appealing as they allowed the design and use of various heuristics. This paper analyses the behavior of such a heuristic that is based on extremal optimization, when used either as an optimizer or within a game theoretic setting. Numerical results, while significantly better than those provided by other state-of-art methods, for some networks show that differences between tested scenarios do not indicate any superior behavior when using game theoretic concepts; moreover, those obtained without using any selection for survival suggest that the search is actually guided by the inner mechanism of the extremal optimization method and by the fitness function used to evaluate and compare components within an individual.

Game theory

A recent approach to the problem of detecting the community structure uses game theoretic concepts to define and detect communities as game equilibria by converting it into a mathematical game in which nodes (as players) choose a community (strategy) trying to maximize a certain payoff function.

Nash equilibrium

In game theory, the Nash equilibrium (NE) is a solution concept of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his or her own strategy.
The Nash equilibrium is one of the foundational concepts in game theory.

Extremal optimization for Community detection

Extremal optimization is a powerful local search tool that has recently been adapted in various forms. To perform comparisons, the NoisyEO algorithm is used as underlying method, with parameters indicated by the authors

About CSC

The Centre for the Study of Complexity is a multidisciplinary research unit of Babes-Bolyai University, Cluj-Napoca aiming to explore the frontiers of complexity and build a network of powerful emerging ideas. Complex real-world problems require novel approaches able to tackle subtle aspects of emergence, auto-organization and evolution. The fundamental principles in complex physical, computational, biological, economical and social systems are intensively studied by bringing together expertise from various fields. We are a research team working on new natural computing models in the study of complexity.

People

Mihai Suciu
Mihai Suciu
evolutionary optimization, game theory, web services composition
Rodica Ioana Lung
Rodica Ioana Lung
game theory, evolutionary optimization, complex networks
Noémi Gaskó
Noémi Gaskó
game theory, evolutionary algorithms

Results

Our results - in progress

Platform developer
Florentin Bota

Latest simulations

  • Aug, 6
    SIMULATION – 709

    SIMULATION – 709

    by

    Simulation Files defaultNetwork709       Date: 06.08.2018 defaultCommunity709       Date: 06.08.2018

    Read more SIMULATION – 709
    Mar, 28
    SIMULATION – 703

    SIMULATION – 703

    by

    The config file was created successfully. Results Reading parameter file: configFile_703.txt Writing result #0: 0,30,13650,45,1,0.0210308,-3.70499e+11,0.0195343,-3.95295e+11,15.4 Writing result #1: 1,30,13650,45,1,0.256444,-1.83719e+12,0.00743998,-5.61236e+11,79.69 File location: http://www.csc-net.ro/neo/wp-content/uploads/rezExpGECCO2016_defaultNetwork703.txt_28_3_19_1_51.csv Simulation Files defaultNetwork703       Date: 28.03.2017 defaultCommunity703       Date: 28.03.2017 configFile_703       Date: 28.03.2017

    Read more SIMULATION – 703
  • Mar, 28
    SIMULATION – 699

    SIMULATION – 699

    by

    Simulation Files defaultNetwork699       Date: 28.03.2017 defaultCommunity699       Date: 28.03.2017

    Read more SIMULATION – 699
    Mar, 23
    SIMULATION – 693

    SIMULATION – 693

    by

    The config file was created successfully. Results Reading parameter file: configFile_693.txt Writing result #0: 0,30,13650,45,1,0.130683,-1.04875e+10,0.000759449,-1.93036e+12,15.75 Writing result #1: 1,30,13650,45,1,0.0352879,-2.35111e+11,0.0226066,-2.3511e+11,107.99 File location: http://www.csc-net.ro/neo/wp-content/uploads/rezExpGECCO2016_defaultNetwork693.txt_23_3_12_27_45.csv Simulation Files defaultNetwork693       Date: 23.03.2017 defaultCommunity693       Date: 23.03.2017 configFile_693       Date: 23.03.2017

    Read more SIMULATION – 693
  • Mar, 15
    SIMULATION – 687

    SIMULATION – 687

    by

    The config file was created successfully. Results Reading parameter file: configFile_687.txt Writing result #0: 0,30,13650,45,1,0.196838,-2.43653e+11,0.00709778,-3.67675e+11,15.83 Writing result #1: 1,30,13650,45,1,0.0294292,-5.8635e+11,0.0260038,-6.06735e+11,83.41 File location: http://www.csc-net.ro/neo/wp-content/uploads/rezExpGECCO2016_defaultNetwork687.txt_15_3_11_51_54.csv Simulation Files defaultNetwork687       Date: 15.03.2017 defaultCommunity687       Date: 15.03.2017 configFile_687       Date: 15.03.2017

    Read more SIMULATION – 687
    Mar, 11
    SIMULATION – 681

    SIMULATION – 681

    by

    The config file was created successfully. Results Reading parameter file: configFile_681.txt Writing result #0: 0,30,13650,45,1,0.0520271,-6.50388e+11,0.0226062,-6.86311e+11,15.63 Writing result #1: 1,30,13650,45,1,0.215783,-7.4703e+11,0.0171246,-5.92822e+11,89.72 Writing result #2: 2,30,13650,45,1,0.285867,-9.54504e+11,0.00276313,-2.87338e+11,13.6 Writing result #3: 3,30,13650,45,1,0.293632,-8.31676e+11,0.00742203,-3.39736e+11,11.75 Writing result #4: 0,30,13650,45,1,0.260902,-8.61938e+11,0.0396527,-1.11252e+12,15.31 File location: http://www.csc-net.ro/neo/wp-content/uploads/rezExpGECCO2016_defaultNetwork681.txt_11_3_7_17_46.csv Simulation Files defaultNetwork681       Date: 11.03.2017 defaultCommunity681       Date: 11.03.2017 configFile_681       Date: 11.03.2017

    Read more SIMULATION – 681
  • Mar, 11
    SIMULATION – 675

    SIMULATION – 675

    by

    The config file was created successfully. Results Reading parameter file: configFile_675.txt Writing result #0: 0,30,13650,45,1,0.0210308,-3.74566e+11,0.0210308,-3.74566e+11,15.69 Writing result #1: 1,30,13650,45,1,0.256231,-1.72364e+12,0.00376113,-3.89648e+11,89.14 File location: http://www.csc-net.ro/neo/wp-content/uploads/rezExpGECCO2016_defaultNetwork675.txt_11_3_7_13_13.csv Simulation Files defaultNetwork675       Date: 11.03.2017 defaultCommunity675       Date: 11.03.2017 configFile_675       Date: 11.03.2017

    Read more SIMULATION – 675
    Mar, 11
    SIMULATION – 669

    SIMULATION – 669

    by

    The config file was created successfully. Result: Data Reading parameter file: configFile_669.txt Writing result #0: 0,30,1650,5,1,0.0240666,-4.35473e+11,0.0210308,-3.88571e+11,4.07 Writing result #1: 1,30,1650,5,1,0.439011,-1.79354e+12,0.00331573,-1.35758e+11,10.14 File location: http://www.csc-net.ro/neo/wp-content/uploads/rezExpGECCO2016_defaultNetwork669.txt_11_3_7_7_25.csv Simulation Files defaultNetwork669       Date: 11.03.2017 defaultCommunity669       Date: 11.03.2017 configFile_669       Date: 11.03.2017

    Read more SIMULATION – 669
  • Mar, 11
    SIMULATION – 657

    SIMULATION – 657

    by

    The config file was created successfully. Result: Reading parameter file: wp-content/uploads/configFile_657.txt Writing result #: 0 0,30,13650,45,1,0.12082,-4.33984e+10,0.0210308,-9.55872e+10,15.79 Writing result #: 1 1,30,13650,45,1,0.176894,-5.39964e+10,0.0243419,-9.63827e+10,72.37 File location: /var/www/html/neo/wp-content/uploads/rezExpGECCO2016_defaultNetwork657.txt_11_3_6_35_24.csv Simulation Files defaultNetwork657       Date: 11.03.2017 defaultCommunity657       Date: 11.03.2017 configFile_657       Date: 11.03.2017

    Read more SIMULATION – 657
    Mar, 8
    SIMULATION – 647

    SIMULATION – 647

    by

    The config file was created successfully. Result: Reading parameter file: wp-content/uploads/configFile_647.txt Writing result #: 0 0,30,13650,45,1,0.114216,-3.68343e+11,0.0022557,-6.54679e+11,15.36 Writing result #: 1 1,30,13650,45,1,0.288074,-1.18123e+12,0.00145888,-1.06169e+12,64.69 File location: /var/www/html/neo/wp-content/uploads/rezExpGECCO2016_defaultNetwork647.txt_8_3_8_53_54.csv Simulation Files defaultNetwork647       Date: 08.03.2017 defaultCommunity647       Date: 08.03.2017 configFile_647       Date: 08.03.2017

    Read more SIMULATION – 647