High-Order Local Clustering on Hypergraphs

被引:0
作者
Wei, Jingtian [1 ]
Yang, Zhengyi [1 ]
Luo, Qi [1 ]
Zhang, Yu [2 ]
Qin, Lu [3 ]
Zhang, Wenjie [1 ]
机构
[1] Univ New South Wales, Sydney, Australia
[2] Univ New South Wales Canberra, Canberra, Australia
[3] Univ Technol Sydney, Sydney, Australia
来源
EAI ENDORSED TRANSACTIONS ON SCALABLE INFORMATION SYSTEMS | 2024年 / 11卷 / 06期
关键词
Local Clustering; Hypergraphs; Conductance;
D O I
10.4108/eetsis.7431
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Graphs are a commonly used model in data mining to represent complex relationships, with nodes representing entities and edges representing relationships. However, graphs have limitations in modeling high-order relationships. In contrast, hypergraphs offer a more versatile representation, allowing edges to join any number of nodes. This capability empowers hypergraphs to model multiple relationships and capture high-order information present in real-world applications. We focus on the problem of local clustering in hypergraphs, which computes a cluster near a given seed node. Although extensively explored in the context of graphs, this problem has received less attention for hypergraphs. Current methods often directly extend graph-based local clustering to hypergraphs, overlooking their inherent high-order features and resulting in low-quality local clusters. To address this, we propose an effective hypergraph local clustering model. This model introduces a novel conductance measurement that leverages the high-order properties of hypergraphs to assess cluster quality. Based on this new definition of hypergraph conductance, we propose a greedy algorithm to find local clusters in real time. Experimental evaluations and case studies on real-world datasets demonstrate the effectiveness of the proposed methods.
引用
收藏
页码:1 / 9
页数:9
相关论文
共 37 条
  • [1] Agarwal S, 2005, PROC CVPR IEEE, P838
  • [2] A New Suppression-based Possibilistic Fuzzy c-means Clustering Algorithm
    Arora, J.
    Tushir, M.
    Dadhwal, S. K.
    [J]. EAI ENDORSED TRANSACTIONS ON SCALABLE INFORMATION SYSTEMS, 2023, 10 (03)
  • [3] Backstrom L., 2006, P ACM SIGKDD INT C K
  • [4] Chierichetti F, 2010, PROC APPL MATH, V135, P1657
  • [5] Hybrid clustering based on content and connection structure using joint nonnegative matrix factorization
    Du, Rundong
    Drake, Barry
    Park, Haesun
    [J]. JOURNAL OF GLOBAL OPTIMIZATION, 2019, 74 (04) : 861 - 877
  • [6] Reduce and Aggregate: Similarity Ranking in Multi-Categorical Bipartite Graphs
    Epasto, Alessandro
    Feldman, Jon
    Lattanzi, Silvio
    Leonardi, Stefano
    Mirrokni, Vahab
    [J]. WWW'14: PROCEEDINGS OF THE 23RD INTERNATIONAL CONFERENCE ON WORLD WIDE WEB, 2014, : 349 - 359
  • [7] Set-Sequence-Graph: A Multi-View Approach Towards Exploiting Reviews for Recommendation
    Gao, Jingyue
    Lin, Yang
    Wang, Yasha
    Wang, Xiting
    Yang, Zhao
    He, Yuanduo
    Chu, Xu
    [J]. CIKM '20: PROCEEDINGS OF THE 29TH ACM INTERNATIONAL CONFERENCE ON INFORMATION & KNOWLEDGE MANAGEMENT, 2020, : 395 - 404
  • [8] Gargi U., 2011, P INT AAAI C WEB SOC
  • [9] Influence maximization on hypergraphs via multi-hop influence estimation
    Gong, Xulu
    Wang, Hanchen
    Wang, Xiaoyang
    Chen, Chen
    Zhang, Wenjie
    Zhang, Ying
    [J]. INFORMATION PROCESSING & MANAGEMENT, 2024, 61 (03)
  • [10] Think locally, act locally: Detection of small, medium-sized, and large communities in large networks
    Jeub, Lucas G. S.
    Balachandran, Prakash
    Porter, Mason A.
    Mucha, Peter J.
    Mahoney, Michael W.
    [J]. PHYSICAL REVIEW E, 2015, 91 (01)