K-truss is an efficient model to detect cohesive subgraphs in ordinary graphs. Many works about trussness decomposition and maintenance on ordinary graphs have been proposed in recent years. However, few studies have focused on hypergraph trussness calculation, and the state-of-art algorithm for hypergraph trussness [7] is for static hypergraphs and is unable to distinguish certain cohesive structures. In this paper, we propose a novel truss definition on hypergraphs that considers the unique structure of hypergraphs. To recognize the structure, we present a parallel decomposition algorithm and a parallel maintenance algorithm based on the h-index. The time complexities of the decomposition and maintenance algorithms are \(O(m*c^2_{max}*h_{max})\) and \(O(L*c_{max}*h_{max})\) , respectively. Here m is the number of hypergraph edges, \(c_{max}\) is the maximum size of a hyperedge, \(h_{max}\) is the maximum number of hyperedges that a vertex is in, and L means the largest Degree Level [14] of vertex pairs in the hypergraph. We also implement our algorithms on real-world hypergraphs and the results show that the maintenance algorithm can speed up two orders of magnitude compared to the decomposition algorithm in terms of time consumption.

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

Parallel Truss Maintenance Algorithms for Dynamic Hypergraphs

  • Meng Wang,
  • Qiang-Sheng Hua,
  • Yefei Wang,
  • Hai Jin,
  • Zhiyuan Shao

摘要

K-truss is an efficient model to detect cohesive subgraphs in ordinary graphs. Many works about trussness decomposition and maintenance on ordinary graphs have been proposed in recent years. However, few studies have focused on hypergraph trussness calculation, and the state-of-art algorithm for hypergraph trussness [7] is for static hypergraphs and is unable to distinguish certain cohesive structures. In this paper, we propose a novel truss definition on hypergraphs that considers the unique structure of hypergraphs. To recognize the structure, we present a parallel decomposition algorithm and a parallel maintenance algorithm based on the h-index. The time complexities of the decomposition and maintenance algorithms are \(O(m*c^2_{max}*h_{max})\) and \(O(L*c_{max}*h_{max})\) , respectively. Here m is the number of hypergraph edges, \(c_{max}\) is the maximum size of a hyperedge, \(h_{max}\) is the maximum number of hyperedges that a vertex is in, and L means the largest Degree Level [14] of vertex pairs in the hypergraph. We also implement our algorithms on real-world hypergraphs and the results show that the maintenance algorithm can speed up two orders of magnitude compared to the decomposition algorithm in terms of time consumption.