Unified Dense Subgraph Detection: Fast Spectral Theory Based Algorithms
文献类型：期刊论文
| 作者 | Feng, Wenjie2,3; Liu, Shenghua3; Koutra, Danai1; Cheng, Xueqi3 |
| 刊名 | IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
 |
| 出版日期 | 2024-03-01 |
| 卷号 | 36期号:3页码:1356-1370 |
| 关键词 | Approximation algorithms Image edge detection Heuristic algorithms Greedy algorithms Optimization Collaboration Task analysis Algorithm anomaly detection dense subgraph graph spectral theory large graph mining |
| ISSN号 | 1041-4347 |
| DOI | 10.1109/TKDE.2023.3272574 |
| 英文摘要 | 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. |
| 资助项目 | National Natural Science Foundation of China |
| WOS研究方向 | Computer Science ; Engineering |
| 语种 | 英语 |
| WOS记录号 | WOS:001167452200014 |
| 出版者 | IEEE COMPUTER SOC |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/38784]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | Feng, Wenjie; Liu, Shenghua |
| 作者单位 | 1.Univ Michigan, Ann Arbor, MI 48109 USA 2.Natl Univ Singapore, Inst Data Sci, Singapore 117602, Singapore 3.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。