Identifying the social-balanced densest subgraph from signed social networks

Title : Identifying the social-balanced densest subgraph from signed social networks
Journal : The Journal of Supercomputin
Authors : Fei Hao, Doo-Soon Park, Zheng Pei, HwaMin Lee, Young-Sik Jeong
Corresponding author : Doo-Soon Park

Identifying the dense subgraphs from large graphs is important and useful to various social media mining applications. Most of existing works focus on the densest subgraph problem in the unweighted and undirected represented social network which can maximize the average degree over all possible subgraphs. However, considering the frequent signed relationships occurred in real-life social network, this paper introduces the social-balanced densest subgraph problem in signed social network by incorporating the social balance theory. We obtain a novel problem formulation that is to identify the subset of vertices that can maximize the social-balanced density in signed social networks. Further, we propose an efficient approach for identifying the social-balanced densest subgraph based on formal concept analysis. The case study illustrates that our algorithm can efficiently identify the social-balanced densest subgraph for satisfying the specific application’s requirements.

This research was supported by the MSIP (Ministry of Science, ICT and Future Planning), Korea, under the C-ITRC (Convergence Information Technology Research Center) (IITP-2015-IITP-2015-H8601-15-1009) supervised by the IITP (Institute for Information and communications Technology Promotion) and was partly supported by the Natural Science Foundation for Young Scientists of Shanxi Province, China (Grant No. 2015021102) and Z. Pei’s work is partially supported by National Nature Science Foundation of China (Grant No. 61372187).