Dense Subgroup Identifying in Social Network

摘要

The densest coherent sub graphs can provide valuable knowledge about the underlying internal structure of a social network, and mining frequently occurring coherent sub graphs of a large network has been witnessed several applications and received considerable attention in the graph mining community recently. However, some key players are not always appeared in the clique, therefore, clique detection could not identify some core members in social networks. In this paper, we define a generalization of the dense sub graph problem by an additional distance restriction to the nodes of the dense sub graph which is a quasi-clique in fact. We propose a new quasi-clique detection algorithm based on the definition of dense sub graph, and a novel optimization techniques based on idea of synchronization, which can prune the unpromising and redundant alien from the dense sub graph. The proposed methods could discover quasi-cliques and core players that are not shown in clique.