Name
Abstract | ||
|---|---|---|
Many networks can be modeled as signed graphs. These include social networks, and relationships/interactions networks. Detecting sub-structures in such networks helps us understand user behavior, predict links, and recommend products. In this paper, we detect dense sub-structures from a signed graph, called quasi antagonistic communities (s). An antagonistic community consists of two groups of users expressing positive relationships within each group but negative relationships across groups. Instead of requiring complete set of negative links across its groups, a allows a small number of inter-group negative links to be missing. We propose an algorithm, , to find all maximal quasi antagonistic communities (s). consists of two stages: pruning and enumeration stages. Based on the properties of , we propose four pruning rules to reduce the size of candidate graphs in the pruning stage. We use an enumeration tree to enumerate all in a top–down fashion in the second stage before they are used to construct s. We have conducted extensive experiments using synthetic signed graphs and two real networks to demonstrate the efficiency and accuracy of the algorithm. We have also found that detecting s helps us to predict the signs of links. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10618-015-0405-2 | Data Mining and Knowledge Discovery |
Keywords | Field | DocType |
Signed graph,Bi-clique,Quasi antagonistic community,Enumeration tree,Power law distribution | Small number,Data mining,Graph,Signed graph,Social network,Computer science,Enumeration,Artificial intelligence,Strongly connected component,Machine learning,Mascot | Journal |
Volume | Issue | ISSN |
30 | 1 | 1384-5810 |
Citations | PageRank | References |
5 | 0.42 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ming Gao | 1 | 76 | 9.41 |
| Ee-Peng Lim | 2 | 5889 | 754.17 |
| David Lo | 3 | 5346 | 259.67 |
| Philips Kokoh Prasetyo | 4 | 73 | 10.52 |