Unified Dense Subgraph Detection: Fast Spectral Theory Based Algorithms

doi:10.1109/TKDE.2023.3272574

CSpace

	Unified Dense Subgraph Detection: Fast Spectral Theory Based Algorithms
	Feng, Wenjie 1,2; Liu, Shenghua 1; Koutra, Danai 3; Cheng, Xueqi 1
	2024-03-01
发表期刊	IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
ISSN	1041-4347
卷号	36 期号:3 页码:1356-1370
摘要	How can we effectively detect fake reviews or fraudulent links on a website? How can we spot communities that suddenly appear based on users' interactions? And how can we efficiently find the minimum cut in a large graph? All of these are related to the finding of dense subgraphs, a significant primitive problem in graph analysis with extensive applications across various domains. In this paper, we focus on formulating the problem of the densest subgraph detection and theoretically compare and contrast several correlated problems. Moreover, we propose a unified framework, GenDS , for the densest subgraph detection, provide some theoretical analysis based on the network flow and spectral graph theory, and devise simple and computationally efficient algorithms, SpecGDS and GepGDS , to solve it by leveraging the spectral properties and greedy search. We conduct thorough experiments on 40 real-world networks with up to 1.47 billion edges from various domains. We demonstrate that our SpecGDS yields up to 58.6 x speedup and achieves better or approximately equal-quality solutions for the densest subgraph detection compared to the baselines. GepGDS also reveals some properties of generalized eigenvalue problems for the GenDS . Also, our methods scale linearly with the graph size and are proven effective in applications such as finding collaborations that appear suddenly in an extensive, time-evolving co-authorship network.
关键词	Approximation algorithms Image edge detection Heuristic algorithms Greedy algorithms Optimization Collaboration Task analysis Algorithm anomaly detection dense subgraph graph spectral theory large graph mining
DOI	10.1109/TKDE.2023.3272574
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Artificial Intelligence ; Computer Science, Information Systems ; Engineering, Electrical & Electronic
WOS记录号	WOS:001167452200014
出版者	IEEE COMPUTER SOC
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/38785
专题	中国科学院计算技术研究所
通讯作者	Feng, Wenjie; Liu, Shenghua
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 2.Natl Univ Singapore, Inst Data Sci, Singapore 117602, Singapore 3.Univ Michigan, Ann Arbor, MI 48109 USA
推荐引用方式 GB/T 7714	Feng, Wenjie,Liu, Shenghua,Koutra, Danai,et al. Unified Dense Subgraph Detection: Fast Spectral Theory Based Algorithms[J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,2024,36(3):1356-1370.
APA	Feng, Wenjie,Liu, Shenghua,Koutra, Danai,&Cheng, Xueqi.(2024).Unified Dense Subgraph Detection: Fast Spectral Theory Based Algorithms.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,36(3),1356-1370.
MLA	Feng, Wenjie,et al."Unified Dense Subgraph Detection: Fast Spectral Theory Based Algorithms".IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 36.3(2024):1356-1370.