\(\alpha \) -Persistent Temporal Clique Enumeration with an Application
摘要
Finding, Counting, and Enumerating different structural patterns in a large graph is a fundamental task in graph mining and forms the basis of many disciplines such as social network analysis, computational epidemiology, etc. Clique is one such structural pattern which is basically a subset of the vertices such that every pair of vertices in this subset is an edge in the graph. In practice, many graphs that we deal with are time-varying, i.e., the edge set of the graph is changing over time. To analyze the structural patterns of such graphs, the notion of temporal clique has been introduced. In this paper, we define the concept of \(\alpha \) -Persistent Temporal Clique ( \(\alpha \) -PT Clique) in a binary node-attributed temporal network and propose an enumeration strategy for such cliques present in a given temporal network. The correctness of the proposed methodology has been illustrated and the complexity analysis has been done. Several experiments have been conducted with real-world temporal network datasets to illustrate the efficiency and effectiveness of the proposed solution approach. We have also demonstrated that \(\alpha \) -PT Clique enumeration will be useful to choose Top-k people to be vaccinated to reduce the propagation of pandemic.