Scholarlink

<p>Cycle detection on massive graphs becomes increasingly important given many large real applications such as anti-money laundering and complex fraud analysis. Most of the existing works focus on finding simple cycles with certain constraints. In this work, we study efficiently finding arbitrary non-simple and simple cycles without any constraints, which is highly needed in real applications, as it is unknown what constraints are needed beforehand. Conventional searching approaches based on vertex or edge traversal exhibit limited time efficiency and scalability in finding arbitrary cycles, especially when a graph is large. In order to find arbitrary cycles over a massive graph <i>G</i>, we construct a cycle basis <i>B</i>(<i>G</i>), where a cycle basis is a minimum set of cycles in <i>G</i> with which all possible cycles in <i>G</i> can be enumerated. The efficiency of cycle enumeration heavily relies on the quality of the cycle basis computed. However, the existing cycle basis cannot be effectively used to enumerate cycles. In this paper, we study a new query-efficient cycle basis (<i>QCB</i>) problem and devise efficient algorithms to find <i>QCB</i> with enhanced efficiency to enumerate cycles. Our experimental studies using 10 synthetic/real datasets demonstrate the efficiency of our approaches to find <i>QCB</i>, and also the efficiency and scalability of our cycle enumeration algorithm based on <i>QCB</i>.</p>

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

Efficient discovery of arbitrary cycles in large-scale networks

  • 期刊论文

  • 发表日期：

    2026年7月11日

查看全文
  • Siyi Teng,
  • Jeffrey Xu Yu,
  • Jiadong Xie

摘要

Cycle detection on massive graphs becomes increasingly important given many large real applications such as anti-money laundering and complex fraud analysis. Most of the existing works focus on finding simple cycles with certain constraints. In this work, we study efficiently finding arbitrary non-simple and simple cycles without any constraints, which is highly needed in real applications, as it is unknown what constraints are needed beforehand. Conventional searching approaches based on vertex or edge traversal exhibit limited time efficiency and scalability in finding arbitrary cycles, especially when a graph is large. In order to find arbitrary cycles over a massive graph G, we construct a cycle basis B(G), where a cycle basis is a minimum set of cycles in G with which all possible cycles in G can be enumerated. The efficiency of cycle enumeration heavily relies on the quality of the cycle basis computed. However, the existing cycle basis cannot be effectively used to enumerate cycles. In this paper, we study a new query-efficient cycle basis (QCB) problem and devise efficient algorithms to find QCB with enhanced efficiency to enumerate cycles. Our experimental studies using 10 synthetic/real datasets demonstrate the efficiency of our approaches to find QCB, and also the efficiency and scalability of our cycle enumeration algorithm based on QCB.