$K$ -Clique Community Detection in Social Networks Based on Formal Concept Analysis

Authors:
Publisher website
Google Scholar
Abstract
With the advent of ubiquitous sensing and networking, future social networks turn into cyber-physical interactions, which are attached with associated social attributes. Therefore, social network analysis is advancing the interconnections among cyber, physical, and social spaces. Community detection is an important issue in social network analysis. Users in a social network usually have some social interactions with their friends in a community because of their common interests or similar profiles. In this paper, an efficient algorithm of k-clique community detection using formal concept analysis (FCA) - a typical computational intelligence technique, namely, FCA-based k-clique community detection algorithm, is proposed. First, a formal context is constructed from a given social network by a modified adjacency matrix. Second, we define a type of special concept named k-equiconcept, which has the same k-size of extent and intent in a formal concept lattice. Then, we prove that the k-clique detection problem is equivalent to finding the k-equiconcepts. Finally, the efficient algorithms for detecting the k-cliques and k-clique communities are devised by virtue of k-equiconcepts and k-intent concepts, respectively. Experimental results demonstrate that the proposed algorithm has a higher F-measure value and significantly reduces the computational cost compared with previous works. In addition, a correlation between k and the number of k-clique communities is investigated.
Funding Information
  • Basic Science Research Program
  • National Research Foundation of Korea (NRF)
  • Ministry of Education (NRF-2014R1A1A4A01007190)
  • EU FP7 CLIMBER Project (PIRSES-GA-2012-318939)
  • National Natural Science Foundation of China (61372187)

This publication has 19 references indexed in Scilit: