Dynamic Maximal Cliques Detection and Evolution Management in Social Internet of Things: A Formal Concept Analysis Approach

Abstract

The booming of Social Internet of Things (SIoT) has witnessed the significance of graph mining and analysis for social network management. Online Social Networks (OSNs) can be efficiently managed by monitoring users behaviors within a cohesive social group represented by a maximal clique. They can further provide valued social intelligence for their users. Maximal Cliques Problem (MCP) as a fundamental problem in graph mining and analysis is to identify the maximal cliques in a graph. Existing studies on MCP mainly focus on static graphs. In this paper, we adopt the Formal Concept Analysis (FCA) theory to represent and analyze social networks. We then develop two novel formal concepts generation algorithms, termed Add-FCA and Dec-FCA, that can be applicable to OSNs for detecting the maximal cliques and characterizing the dynamic evolution process of maximal cliques in OSNs. Extensive experimental results are conducted to investigate and demonstrate the correctness and effectiveness of the proposed algorithms. The results reveal that our algorithms can efficiently capture and manage the evolutionary patterns of maximal cliques in OSNs, and a quantitative relation among them is presented. In addition, an illustrative example is presented to verify the usefulness of the proposed approach.