Overlapping communities detection through weighted graph community games.

Area of Science:

• Network science
• Game theory
• Operations research

Background:

• Community detection is crucial for understanding network structures.
• Existing methods often struggle with overlapping communities or large-scale networks.
• Cooperative game theory offers a framework for modeling group interactions.

Purpose of the Study:

• To develop a new model for detecting overlapping communities in networks.
• To leverage cooperative games and mathematical programming for community identification.
• To provide a robust method for analyzing complex network structures.

Main Methods:

• Defining communities as stable coalitions within a weighted graph community game.
• Formulating community detection as a mixed-integer linear programming (MILP) problem.
• Developing a heuristic algorithm to address scalability for large networks.

Main Results:

• The proposed model accurately identifies overlapping communities.
• Exact solutions for small to medium networks reveal valuable structural insights.
• The heuristic algorithm effectively handles large instances and allows objective function comparison.

Conclusions:

• The cooperative game and mathematical programming model offers a powerful approach to overlapping community detection.
• The method enhances understanding of network topology and group dynamics.
• The developed heuristic ensures applicability to real-world, large-scale network analysis.