Open AccessApproximation of Nash equilibria and the network community structure detection problem
Author(s) -
Mihai Alexandru Suciu,
Noémi Gaskó,
Rodica Ioana Lung
Publication year - 2017
Publication title -
plos one
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.99
H-Index - 332
ISSN - 1932-6203
DOI - 10.1371/journal.pone.0174963
Subject(s) - nash equilibrium , computer science , game theory , mathematical optimization , community structure , stochastic game , optimization problem , best response , function (biology) , mathematical economics , mathematics , combinatorics , evolutionary biology , biology
Game theory based methods designed to solve the problem of community structure detection in complex networks have emerged in recent years as an alternative to classical and optimization based approaches. The Mixed Nash Extremal Optimization uses a generative relation for the characterization of Nash equilibria to identify the community structure of a network by converting the problem into a non-cooperative game. This paper proposes a method to enhance this algorithm by reducing the number of payoff function evaluations. Numerical experiments performed on synthetic and real-world networks show that this approach is efficient, with results better or just as good as other state-of-the-art methods.