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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

\(\alpha \) -Persistent Temporal Clique Enumeration with an Application

  • Bithika Pal,
  • Sudeshna Kolay,
  • Suman Banerjee

摘要

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.