Game Theoretic Clustering for Finding Strong Communities

Area of Science:

• Network Science
• Game Theory
• Data Mining

Background:

• Existing community detection methods often lack unique solutions and are sensitive to initial conditions.
• Identifying meaningful and stable communities in complex networks remains a significant challenge.

Purpose of the Study:

• To propose a novel model for community detection that guarantees unique and meaningful solutions.
• To develop a computationally efficient framework for identifying hierarchical community structures.

Main Methods:

• Utilizing convex game theory and a measure of community strength.
• Employing submodular function minimization for polynomial-time computation.
• Extending the framework to hypergraphs and polymatroids.

Main Results:

• The proposed model identifies strong communities with a hierarchical structure, visualized as a dendrogram.
• The framework provides unique solutions with clear operational meaning.
• A more efficient algorithm based on max-flow min-cut is feasible for graphical models.

Conclusions:

• The convex game theory approach offers a robust analytical framework for community detection.
• The method yields unique, hierarchical, and interpretable community structures.
• Future research can focus on developing near-linear time complexity algorithms for practical applications.