Optimisation dans la détection de communautés recouvrantes et équilibre de Nash

Abstract

Community detection in graphs has been the subject of many algorithms. Recent methods want to optimize a modularity function which shows a maximum of relationships within communities and found a minimum of inter-community relations. these algorithms are applied to unipartite, multipartite and directed graphs. However, given the NP-completeness of the problem, these algorithms are heuristics that do not guarantee an optimum. In this paper we introduce an algorithm which, based on an approximate solution obtained through a efficient detection algorithm, modifie it to achieve a local optimum based on a function. this reassignment function is a potential function and therefore the computed optimum is a Nash equilibrium. We supplement our method with an overlap function that allows to have simultaneously the two detection modes. Several experiments show the interest of our approach.

References in corpus (10)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Detecting the overlapping and hierarchical community structure of complex networks
• Community structure in directed networks
• Modularity and community detection in bipartite networks
• Line Graphs, Link Partitions and Overlapping Communities
• Detecting network communities by propagating labels under constraints
• Partitioning and modularity of graphs with arbitrary degree distribution