Network partitioning algorithms as cooperative games

A Four-Stage Algorithm for Community Detection Based on Label Propagation and Game Theory in Social Networks

Over the years, detecting stable communities in a complex network has been a major challenge in network science. The global and local structures help to detect communities from different perspectives. However, previous methods based on them suffer from high complexity and fall into local optimum, respectively. The Four-Stage Algorithm (FSA) is proposed to reduce these issues and to allocate nodes to stable communities. Balancing global and local information, as well as accuracy and time complexity, while ensuring the allocation of nodes to stable communities, are the fundamental goals of this research. The Four-Stage Algorithm (FSA) is described and demonstrated using four real-world data with ground truth and three real networks without ground truth. In addition, it is evaluated with the results of seven community detection methods: Three-stage algorithm (TS), Louvain, Infomap, Fastgreedy, Walktrap, Eigenvector, and Label propagation (LPA). Experimental results on seven real network data sets show the effectiveness of our proposed approach and confirm that it is sufficiently capable of identifying those communities that are more desirable. The experimental results confirm that the proposed method can detect more stable and assured communities. For future work, deep learning methods can also be used to extract semantic content features that are more beneficial to investigating networks.

A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection

In this paper we formally define the hierarchical clustering network problem (HCNP) as the problem to find a good hierarchical partition of a network. This new problem focuses on the dynamic process of the clustering rather than on the final picture of the clustering process. To address it, we introduce a new hierarchical clustering algorithm in networks, based on a new shortest path betweenness measure. To calculate it, the communication between each pair of nodes is weighed by the importance of the nodes that establish this communication. The weights or importance associated to each pair of nodes are calculated as the Shapley value of a game, named as the linear modularity game. This new measure, (the node-game shortest path betweenness measure), is used to obtain a hierarchical partition of the network by eliminating the link with the highest value. To evaluate the performance of our algorithm, we introduce several criteria that allow us to compare different dendrograms of a network from two point of view: modularity and homogeneity. Finally, we propose a faster algorithm based on a simplification of the node-game shortest path betweenness measure, whose order is quadratic on sparse networks. This fast version is competitive from a computational point of view with other hierarchical fast algorithms, and, in general, it provides better results.