IEICE TRANSACTIONS on Fundamentals
A Game-Theoretic Approach for Community Detection in Signed Networks
Summary :
Signed networks are ubiquitous in the real world. It is of great significance to study the problem of community detection in signed networks. In general, the behaviors of nodes in a signed network are rational, which coincide with the players in the theory of game that can be used to model the process of the community formation. Unlike unsigned networks, signed networks include both positive and negative edges, representing the relationship of friends and foes respectively. In the process of community formation, nodes usually choose to be in the same community with friends and between different communities with enemies. Based on this idea, we proposed a game theory model to address the problem of community detection in signed networks. Taking nodes as players, we build a gain function based on the numbers of positive edges and negative edges inside and outside a community, and prove the existence of Nash equilibrium point. In this way, when the game reaches the Nash equilibrium state, the optimal strategy space for all nodes is the result of the final community division. To systematically investigate the performance of our method, elaborated experiments on both synthetic networks and real-world networks are conducted. Experimental results demonstrate that our method is not only more accurate than other existing algorithms, but also more robust to noise.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.6 pp.796-807
- Publication Date
- 2019/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E102.A.796
- Type of Manuscript
- PAPER
- Category
- Graphs and Networks
Authors
Shuaihui WANG
University of PLA
Guyu HU
Army Engineering University of PLA
Zhisong PAN
Army Engineering University of PLA
Jin ZHANG
University of PLA,Army Military Transportation University
Dong LI
University of PLA
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shuaihui WANG, Guyu HU, Zhisong PAN, Jin ZHANG, Dong LI, "A Game-Theoretic Approach for Community Detection in Signed Networks" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 6, pp. 796-807, June 2019, doi: 10.1587/transfun.E102.A.796.
Abstract: Signed networks are ubiquitous in the real world. It is of great significance to study the problem of community detection in signed networks. In general, the behaviors of nodes in a signed network are rational, which coincide with the players in the theory of game that can be used to model the process of the community formation. Unlike unsigned networks, signed networks include both positive and negative edges, representing the relationship of friends and foes respectively. In the process of community formation, nodes usually choose to be in the same community with friends and between different communities with enemies. Based on this idea, we proposed a game theory model to address the problem of community detection in signed networks. Taking nodes as players, we build a gain function based on the numbers of positive edges and negative edges inside and outside a community, and prove the existence of Nash equilibrium point. In this way, when the game reaches the Nash equilibrium state, the optimal strategy space for all nodes is the result of the final community division. To systematically investigate the performance of our method, elaborated experiments on both synthetic networks and real-world networks are conducted. Experimental results demonstrate that our method is not only more accurate than other existing algorithms, but also more robust to noise.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.796/_p
Copy
@ARTICLE{e102-a_6_796,
author={Shuaihui WANG, Guyu HU, Zhisong PAN, Jin ZHANG, Dong LI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Game-Theoretic Approach for Community Detection in Signed Networks},
year={2019},
volume={E102-A},
number={6},
pages={796-807},
abstract={Signed networks are ubiquitous in the real world. It is of great significance to study the problem of community detection in signed networks. In general, the behaviors of nodes in a signed network are rational, which coincide with the players in the theory of game that can be used to model the process of the community formation. Unlike unsigned networks, signed networks include both positive and negative edges, representing the relationship of friends and foes respectively. In the process of community formation, nodes usually choose to be in the same community with friends and between different communities with enemies. Based on this idea, we proposed a game theory model to address the problem of community detection in signed networks. Taking nodes as players, we build a gain function based on the numbers of positive edges and negative edges inside and outside a community, and prove the existence of Nash equilibrium point. In this way, when the game reaches the Nash equilibrium state, the optimal strategy space for all nodes is the result of the final community division. To systematically investigate the performance of our method, elaborated experiments on both synthetic networks and real-world networks are conducted. Experimental results demonstrate that our method is not only more accurate than other existing algorithms, but also more robust to noise.},
keywords={},
doi={10.1587/transfun.E102.A.796},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - A Game-Theoretic Approach for Community Detection in Signed Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 796
EP - 807
AU - Shuaihui WANG
AU - Guyu HU
AU - Zhisong PAN
AU - Jin ZHANG
AU - Dong LI
PY - 2019
DO - 10.1587/transfun.E102.A.796
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2019
AB - Signed networks are ubiquitous in the real world. It is of great significance to study the problem of community detection in signed networks. In general, the behaviors of nodes in a signed network are rational, which coincide with the players in the theory of game that can be used to model the process of the community formation. Unlike unsigned networks, signed networks include both positive and negative edges, representing the relationship of friends and foes respectively. In the process of community formation, nodes usually choose to be in the same community with friends and between different communities with enemies. Based on this idea, we proposed a game theory model to address the problem of community detection in signed networks. Taking nodes as players, we build a gain function based on the numbers of positive edges and negative edges inside and outside a community, and prove the existence of Nash equilibrium point. In this way, when the game reaches the Nash equilibrium state, the optimal strategy space for all nodes is the result of the final community division. To systematically investigate the performance of our method, elaborated experiments on both synthetic networks and real-world networks are conducted. Experimental results demonstrate that our method is not only more accurate than other existing algorithms, but also more robust to noise.
ER -
English
