Dynamic Cluster Formation Game for Attributed Graph Clustering.

Area of Science:

• Graph theory
• Network science
• Game theory

Background:

• Real-world networks often involve complex systems with diverse actors, best modeled as attributed graphs.
• Understanding how clusters form and evolve within these diverse attributed graphs is a significant challenge.
• Attributed graph clustering (AGC) aims to group nodes based on both connections and attributes.

Purpose of the Study:

• To develop a novel framework for attributed graph clustering (AGC).
• To model AGC as a dynamic cluster formation game (DCFG).
• To propose a self-learning algorithm for finding balanced AGC solutions.

Main Methods:

• Conceptualizing AGC as a dynamic cluster formation game (DCFG).
• Analyzing a special case: dynamic social games (DSG) and proving Nash equilibrium convergence.
• Developing a self-learning algorithm to solve coupled static Nash equilibrium problems.

Main Results:

• Demonstrated that balanced AGC solutions can be found by solving Nash equilibrium problems.
• Proposed a self-learning algorithm capable of achieving balanced solutions from arbitrary initial configurations.
• Validated the effectiveness and scalability of the approach through experiments on real-world social networks.

Conclusions:

• The proposed DCFG framework offers a robust method for tackling AGC.
• The self-learning algorithm effectively identifies satisfied cluster configurations in diverse networks.
• The approach shows promise for analyzing complex attributed graph structures in various domains.