Title: Examining spectral space of complex networks with positive and negative links

Authors: Leting Wu; Xiaowei Ying; Xintao Wu; Aidong Lu; Zhi-Hua Zhou

Addresses: Software and Information Systems Department, University of North Carolina at Charlotte, 9201 University City Blvd., Charlotte, NC 28223, USA. ' Software and Information Systems Department, University of North Carolina at Charlotte, 9201 University City Blvd., Charlotte, NC 28223, USA. ' Software and Information Systems Department, University of North Carolina at Charlotte, 9201 University City Blvd., Charlotte, NC 28223, USA. ' Computer Science Department, University of North Carolina, 9201 University City Blvd., Charlotte, NC 28223, USA. ' National Key Laboratory for Novel Software Technology, Nanjing University, 163 Xianlin Avenue, Nanjing 210046, China

Abstract: Previous studies on social networks are often focused on networks with only positive relations between individual nodes. As a significant extension, we conduct the spectral analysis on graphs with both positive and negative edges. Specifically, we investigate the impacts of introducing negative edges and examine patterns in the spectral space of the graph's adjacency matrix. Our theoretical results show that communities in a k-balanced signed graph are distinguishable in the spectral space of its signed adjacency matrix even if connections between communities are dense. This is quite different from recent findings on unsigned graphs, where communities tend to mix together in the spectral space when connections between communities become dense. We further conduct theoretical studies based on graph perturbation to examine spectral patterns of general unbalanced signed graphs. We illustrate our theoretical findings with various empirical evaluations on both synthetic data and real world Correlates of War data.

Keywords: spectral analysis; balanced graph; matrix perturbation; social networks; complex networks; negative edges; spectral space; adjacency matrix.

DOI: 10.1504/IJSNM.2012.045107

International Journal of Social Network Mining, 2012 Vol.1 No.1, pp.91 - 111

Received: 18 Apr 2011
Accepted: 13 Sep 2011
Published online: 21 Aug 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article