Strong Nash Stability based Approach to Minimum Quasi Clique Partitioning

Srinka Basu, Debarka Sengupta, Ujjwal Maulik, Sanghamitra Bandyopadhyay, Communication Systems and Networks (COMSNETS), 2014 Sixth International Conference :1-6 (2014).


The problem of network partitioning into cohesive subgroups is of utmost interest in analysis of social networks. In this paper we use quasi clique based partitioning to study social cohesion. We propose a greedy algorithm based on the notion of strong Nash stability to determine the cohesive subgroups in a network. Through experimental results we show that the proposed algorithm yields promising results by identifying meaningful, compact and dense clusters in many real life social network data sets.