期刊
2018 IEEE 34TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE)
卷 -, 期 -, 页码 245-256出版社
IEEE
DOI: 10.1109/ICDE.2018.00031
关键词
-
资金
- NSFC [61772091, 61732003, 61772346]
- Guangdong Natural Science Foundation [2017B030314073]
- Guangdong Provincial General University National Development Program [2014GKXM054]
- ARC [DP 160101513]
- MOE, Singapore [MOE2015-T2-2-069]
- NUS, Singapore under SUG
- Research Grants Council of the Hong Kong SAR, China [14221716]
Mining cohesive subgraphs from a network is a fundamental problem in network analysis. Most existing cohesive subgraph models are mainly tailored to unsigned networks. In this paper, we study the problem of seeking cohesive subgraphs in a signed network, in which each edge can be positive or negative, denoting friendship or conflict respectively. We propose a novel model, called maximal (alpha, kappa)-clique, that represents a cohesive subgraph in signed networks. Specifically, a maximal (alpha, kappa)-clique is a clique in which every node has at most.. negative neighbors and at least [alpha kappa] positive neighbors (alpha >= 1). We show that the problem of enumerating all maximal (alpha, kappa)cliques in a signed network is NP-hard. To enumerate all maximal (alpha, kappa)-cliques efficiently, we first develop an elegant signed network reduction technique to significantly prune the signed network. Then, we present an efficient branch and bound enumeration algorithm with several carefully-designed pruning rules to enumerate all maximal (alpha, kappa)-cliques in the reduced signed network. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据