Clique as a fundamental model within graph theory, has been extensively studied in various single-layer graphs. However, in multilayer (ML) graphs, which provide a more expressive representational framework, research in this area remains relatively limited. In this paper, we propose a novel model, named (k, \(\lambda \) )-frequent clique ((k, \(\lambda \) )-FC), designed to capture complex patterns of interactions that across various domains in ML graph. Given a ML graph G, a node set H is a \((k,\lambda )\) -FC if i) \(|H| \ge k\) , and ii) H is a clique in at least \(\lambda \) layers. We aim to enumerate all the maximal \((k,\lambda )\) -FCs, which is proved to be NP-hard. To tackle the problem, we introduce the concept of the projection graph and develop a merged-based search method based on it. To further enhance efficiency, we implement optimizations in graph reduction, branch pruning, and intersection acceleration. Extensive experiments on 10 real-world ML graphs are conducted to demonstrate the efficiency and effectiveness of the proposed model and techniques.

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

Efficient Maximal Frequent Clique Enumeration in Multilayer Networks

  • Han Wang,
  • Renjie Sun,
  • Yongye Li,
  • Chen Chen,
  • Xiaoyang Wang,
  • Ying Zhang

摘要

Clique as a fundamental model within graph theory, has been extensively studied in various single-layer graphs. However, in multilayer (ML) graphs, which provide a more expressive representational framework, research in this area remains relatively limited. In this paper, we propose a novel model, named (k, \(\lambda \) )-frequent clique ((k, \(\lambda \) )-FC), designed to capture complex patterns of interactions that across various domains in ML graph. Given a ML graph G, a node set H is a \((k,\lambda )\) -FC if i) \(|H| \ge k\) , and ii) H is a clique in at least \(\lambda \) layers. We aim to enumerate all the maximal \((k,\lambda )\) -FCs, which is proved to be NP-hard. To tackle the problem, we introduce the concept of the projection graph and develop a merged-based search method based on it. To further enhance efficiency, we implement optimizations in graph reduction, branch pruning, and intersection acceleration. Extensive experiments on 10 real-world ML graphs are conducted to demonstrate the efficiency and effectiveness of the proposed model and techniques.