Cooperative Game Theory Approaches for Network Partitioning

Abstract

The paper is devoted to game-theoretic methods for community detection in networks. The traditional methods for detecting community structure are based on selecting denser subgraphs inside the network. Here we propose to use the methods of cooperative game theory that highlight not only the link density but also the mechanisms of cluster formation. Specifically, we suggest two approaches from cooperative game theory: the first approach is based on the Myerson value, whereas the second approach is based on hedonic games. Both approaches allow to detect clusters with various resolution. However, the tuning of the resolution parameter in the hedonic games approach is particularly intuitive. Furthermore, the modularity based approach and its generalizations can be viewed as particular cases of the hedonic games.

References in corpus (6)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Near linear time algorithm to detect community structures in large-scale networks
• Resolution limit in community detection
• Statistical Mechanics of Community Detection

Cited by in corpus (211)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Near linear time algorithm to detect community structures in large-scale networks
• Stochastic blockmodels and community structure in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in networks: A user guide
• An information-theoretic framework for resolving community structure in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Line Graphs, Link Partitions and Overlapping Communities
• Mixture models and exploratory analysis in networks
• Analysis of the structure of complex networks at different resolution levels
• Defining and identifying Sleeping Beauties in science
• Phase transition in the detection of modules in sparse networks
• Detecting network communities by propagating labels under constraints
• Robustness of community structure in networks
• Modularity-Maximizing Network Communities via Mathematical Programming
• Size reduction of complex networks preserving modularity
• Community Detection in Complex Networks Using Genetic Algorithms
• Modularity clustering is force-directed layout
• Community detection in networks: Structural communities versus ground truth
• The entropy of randomized network ensembles
• Nestedness in complex networks: Observation, emergence, and implications
• Community Detection as an Inference Problem
• Crawling Facebook for Social Network Analysis Purposes
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Robust network community detection using balanced propagation
• Kernel Granger causality and the analysis of dynamical networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• Clique Graphs and Overlapping Communities
• Structural Inference of Hierarchies in Networks
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• On network bipartivity
• Motif-based communities in complex networks
• When are networks truly modular?
• Social significance of community structure: Statistical view
• Predicting percolation thresholds in networks
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Spectral methods for the detection of network community structure: a comparative analysis
• Unifying Graph Convolutional Neural Networks and Label Propagation
• Prisoners' dilemma in real-world acquaintance networks: Spikes and quasi-equilibria induced by the interplay between structure and dynamics
• Information filtering in complex weighted networks
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Efficient method for estimating the number of communities in a network
• Median evidential c-means algorithm and its application to community detection
• Network Community Detection: A Review and Visual Survey
• EoN (Epidemics on Networks): a fast, flexible Python package for simulation, analytic approximation, and analysis of epidemics on networks
• Data-driven Computational Social Science: A Survey
• Communicability Graph and Community Structures in Complex Networks
• Dynamic message-passing equations for models with unidirectional dynamics
• Note on the equivalence of the label propagation method of community detection and a Potts model approach
• Identification of network modules by optimization of ratio association
• Topological implications of negative curvature for biological and social networks
• Community Structure Detection in Complex Networks with Partial Background Information
• Measuring robustness of community structure in complex networks
• People are Strange when you're a Stranger: Impact and Influence of Bots on Social Networks
• DDGK: Learning Graph Representations for Deep Divergence Graph Kernels
• Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
• Interacting discovery processes on complex networks
• Phase transitions in semisupervised clustering of sparse networks
• Covariance, correlation matrix and the multi-scale community structure of networks
• Markov random walk under constraint for discovering overlapping communities in complex networks
• Unveiling community structures in weighted networks
• Detecting communities of triangles in complex networks using spectral optimization
• Detecting Communities in Networks by Merging Cliques
• Opinion Maximization in Social Networks
• Multilayer Network Science: from Cells to Societies
• Fast and accurate determination of modularity and its effect size
• Finding network communities using modularity density
• Discrete-time quantum walk on complex networks for community detection
• Optimizing an Organized Modularity Measure for Topographic Graph Clustering: a Deterministic Annealing Approach
• Genetic Algorithm with Ensemble Learning for Detecting Community Structure in Complex Networks
• Genetic Algorithm with a Local Search Strategy for Discovering Communities in Complex Networks
• Hierarchical benchmark graphs for testing community detection algorithms
• Reinforced communication and social navigation generate groups in model networks
• Exploiting the Structure of Bipartite Graphs for Algebraic and Spectral Graph Theory Applications
• Community detection and Social Network analysis based on the Italian wars of the 15th century
• The Interplay Between Dynamics and Networks: Centrality, Communities, and Cheeger Inequality
• DMCS : Density Modularity based Community Search
• Identifying overlapping communities in social networks using multi-scale local information expansion
• Gain and loss of esteem, direct reciprocity and Heider balance
• What do we see when we look at networks
• Graph Comparison via the Non-backtracking Spectrum
• A Generalized and Adaptive Method for Community Detection
• Modeling and verifying a broad array of network properties
• Effect of size heterogeneity on community identification in complex networks
• Network Weirdness: Exploring the Origins of Network Paradoxes
• Quantum walks on complex networks with connection instabilities and community structure
• Ant Colony Optimization with a New Random Walk Model for Community Detection in Complex Networks
• Social Network Analysis Taxonomy Based on Graph Representation
• Community detection using preference networks
• Discovering link communities in complex networks by exploiting link dynamics
• The characteristics of cycle-nodes-ratio and its application to network classification
• Network clustering and community detection using modulus of families of loops
• Multi-resolution community detection in massive networks
• Community detection by label propagation with compression of flow
• Inferring the strength of social ties: a community-driven approach
• Node Dependent Local Smoothing for Scalable Graph Learning
• Embedding Node Structural Role Identity into Hyperbolic Space
• Methods for approximating stochastic evolutionary dynamics on graphs
• Clustering and Community Detection with Imbalanced Clusters
• ExplaiNE: An Approach for Explaining Network Embedding-based Link Predictions
• Understanding graph embedding methods and their applications
• Approximating quasi-stationary behaviour in network-based SIS dynamics
• A Method for Group Extraction and Analysis in Multilayer Social Networks
• Community structure revealed by phase locking
• Spectral estimation of the percolation transition in clustered networks
• Multi-scale Dynamics in a Massive Online Social Network
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Exploring the "Middle Earth" of Network Spectra via a Gaussian Matrix Function
• Fast Complex Network Clustering Algorithm Using Agents
• Detecting groups of similar components in complex networks
• ImGAGN:Imbalanced Network Embedding via Generative Adversarial Graph Networks
• Consistent Community Identification in Complex Networks
• Community Detection in Complex Networks Using Agents
• Locally computable approximations for spectral clustering and absorption times of random walks
• Optimal exploration of random walks with local bias on networks
• Evidential Communities for Complex Networks
• Consensus and Information Cascades in Game-Theoretic Imitation Dynamics with Static and Dynamic Network Topologies
• Identification of Overlapping Communities by Locally Calculating Community-Changing Resolution Levels
• Weighted H-index for identifying influential spreaders
• Fast Community Identification by Hierarchical Growth
• Model-based clustering in networks with Stochastic Community Finding
• Understanding Information Centrality Metric: A Simulation Approach
• The Landscape of Complex Networks
• Explainable, Stable, and Scalable Graph Convolutional Networks for Learning Graph Representation
• Entrograms and coarse graining of dynamics on complex networks
• Community structure in real-world networks from a non-parametrical synchronization-based dynamical approach
• Ranking the Importance of Nodes of Complex Networks by the Equivalence Classes Approach
• Null-eigenvalue localization of quantum walks on real-world complex networks
• Benchmarking community detection methods on social media data
• On Comparing and Enhancing Common Approaches to Network Community Detection
• Generating Post-hoc Explanations for Skip-gram-based Node Embeddings by Identifying Important Nodes with Bridgeness
• On weakly optimal partitions in modular networks
• Geometric properties of graph layouts optimized for greedy navigation
• Leiden-Fusion Partitioning Method for Effective Distributed Training of Graph Embeddings
• Active Learning for Hidden Attributes in Networks
• Angular separability of data clusters or network communities in geometrical space and its relevance to hyperbolic embedding
• Finding the proper node ranking method for complex networks
• Percolation transitions with nonlocal constraint
• A fast multilevel algorithm for graph clustering and community detection
• A new edge betweenness measure using a game theoretical approach: an application to hierarchical community detection
• Opinion Dynamics Optimization Through Noncooperative Differential Games
• Efficient network navigation with partial information
• A multilevel clustering technique for community detection
• Stochastic graph Voronoi tessellation reveals community structure
• Combinations of Affinity Functions for Different Community Detection Algorithms in Social Networks
• Smoothness Sensor: Adaptive Smoothness-Transition Graph Convolutions for Attributed Graph Clustering
• Systematic comparison of graph embedding methods in practical tasks
• Distortion estimates for approximate Bayesian inference
• Dual regularized Laplacian spectral clustering methods on community detection
• Community Detection Algorithm Combining Stochastic Block Model and Attribute Data Clustering
• Maximizing spreading in complex networks with risk in node activation
• Analyzing Large and Sparse Tensor Data using Spectral Low-Rank Approximation
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• Analyzing the Performance of Graph Neural Networks with Pipe Parallelism
• Clustering evolving data using kernel-based methods
• A Visual Analytics Framework for Contrastive Network Analysis
• Ensemble Node Embeddings using Tensor Decomposition: A Case-Study on DeepWalk
• Lowest Degree Decomposition of Complex Networks
• Scalable Community Detection via Parallel Correlation Clustering
• Overcoming Bias in Community Detection Evaluation
• Weighted Label Propagation Algorithm based on Local Edge Betweenness
• QWalkVec: Node Embedding by Quantum Walk
• Evolutionary Multi Objective Optimization Algorithm for Community Detection in Complex Social Networks
• Spectral Graph Analysis: A Unified Explanation and Modern Perspectives
• Multilateration of Random Networks with Community Structure
• Fair treatment allocations in social networks
• Community Detection by Principal Components Clustering Methods
• An improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel
• The vulnerability of communities in complex network: An entropy approach
• Hate: no choice. Agent simulations
• Trophic groups and modules: two levels of group detection in food webs
• Symmetrical SyncMap for Imbalanced General Chunking Problems
• Using Spectral Radius Ratio for Node Degree to Analyze the Evolution of Scale Free Networks and Small World Networks
• Competitive Dynamics on Complex Networks
• On the notion of balance in social network analysis
• Dominating sets and ego-centered decompositions in social networks
• Spaceland Embedding of Sparse Stochastic Graphs
• Correlation-Based Community Detection
• Temporal similarity metrics for latent network reconstruction: The role of time-lag decay
• Error-Correcting Decoders for Communities in Networks
• Synergistic Effects in Networked Epidemic Spreading Dynamics
• Improved mixing time for k-subgraph sampling
• A Game-Theoretic Algorithm for Link Prediction
• Tutorial on NLP-Inspired Network Embedding
• Impact of independence on polarization of opinions
• Estimating Network Processes via Blind Identification of Multiple Graph Filters
• Spectral clustering of annotated graphs using a factor graph representation
• Generalized Centrality Aggregation and Exclusive Centrality
• Community Detection by a Riemannian Projected Proximal Gradient Method
• On the use of local structural properties for improving the efficiency of hierarchical community detection methods
• A Consistent Diffusion-Based Algorithm for Semi-Supervised Classification on Graphs
• Cultural fragmentation and innovation diffusion in a dynamic scenario
• Statistical properties of telephone communication network
• Inferring Network Structure From Data
• A systematic association of subgraph counts over a network
• A novel method based on node correlation to evaluate the important nodes in complex networks
• Dynamic Virtual Graph Significance Networks for Predicting Influenza
• A Neighborhood-preserving Graph Summarization
• Understanding in Artificial Intelligence
• Mixed-SCORE+ for mixed membership community detection
• Interpreting Graph Drawing with Multi-Agent Reinforcement Learning
• Exact statistical mechanics of the Ising model on networks
• Evaluating Effects of Background Stories on Graph Perception
• SNAC: An Unbiased Metric Evaluating Topology Recognize Ability of Network Alignment
• Diseases on complex networks. Modeling from a database and a protection strategy proposal
• God ($\equiv Elohim$), the first small world network
• Classification of vertices on social networks by multiple approaches
• A Consistent Diffusion-Based Algorithm for Semi-Supervised Graph Learning