This paper presents a spectral analysis of signed networks from both theoretical and practical aspects. On the theoretical aspect, we conduct theoretical studies based on results from matrix perturbation for analyzing community structures of complex signed networks and show how the negative edges affect distributions and patterns of node spectral coordinates in the spectral space. We prove and demonstrate that node spectral coordinates form orthogonal clusters for two types of signed networks: graphs with dense inter-community mixed sign edges and$k$-dispute graphs where inner-community connections are absent or very sparse but inter-community connections are dense with negative edges. The cluster orthogonality pattern is different from the line orthogonality pattern (i.e., node spectral coordinates form orthogonal lines) observed in the networks with$k$-block structure. We show why the line orthogonality pattern does not hold in the spectral space for these two types of networks. On the practical aspect, we have developed a clustering method to study signed networks and$k$-dispute networks. Empirical evaluations on both synthetic networks (with up to one million nodes) and real networks show our algorithm outperforms existing clustering methods on signed networks in terms of accuracy and efficiency.

This paper presents a study of signed networks from both theoretical and practical aspects. On the theoretical aspect, we conduct theoretical study based on matrix perturbation theorem for analyzing community structures of complex signed networks and show how the negative edges affect distributions and patterns of node spectral coordinates in the spectral space. We prove and demonstrate cluster orthogonality for two types of signed networks: graph with dense inter-community mixed sign edges and k-dispute graph. We show why the line orthogonality pattern does not hold in the spectral space for these two types of networks. On the practical aspect, we have developed a clustering method to study signed networks and k-dispute networks. Empirical evaluations on both synthetic and real networks show our algorithm outperforms existing clustering methods on signed networks in terms of accuracy.

Different from Laplacian or normal matrix, the properties of the adjacency eigenspace received much less attention. Recent work showed that nodes projected into the adjacency eigenspace exhibit an orthogonal line pattern and nodes from the same community locate along the same line. In this paper, we conduct theoretical studies based on graph perturbation to demonstrate why this line orthogonality property holds in the adjacency eigenspace and why it generally disappears in the Laplacian and normal eigenspaces. Using the orthogonality property in the adjacency eigenspace, we present a graph partition algorithm, AdjCluster, which first projects node coordinates to the unit sphere and then applies the classic k-means to find clusters. Empirical evaluations on synthetic data and real-world social networks validate our theoretical findings and show the effectiveness of our graph partition algorithm.

Social networks tend to contain some amount of randomness and some amount of nonrandomness. The amount of randomness versus nonrandomness affects the properties of a social network. In this paper, we theoretically analyze graph randomness and present a framework which provides a series of nonrandomness measures at levels of edge, node, subgraph, and the overall graph. We show that graph nonrandomness can be obtained mathematically from the spectra of the adjacency matrix of the network. We derive the upper bound and lower bound of nonrandomness value of the overall graph. We investigate whether other graph spectra (such as Laplacian and normal spectra) could also be used to derive a nonrandomness framework. Our theoretical results showed that they are unlikely, if not impossible, to have a consistent framework to evaluate randomness. We also compare our proposed nonrandomness measures with some traditional measures such as modularity. Our theoretical and empirical studies show our proposed nonrandomness measures can characterize and capture graph randomness.

The privacy concerns associated with data analysis over social networks have spurred recent research on privacy-preserving social network analysis, particularly on privacy-preserving publishing of social network data. In this paper, we focus on whether we can reconstruct a graph from the edge randomized graph such that accurate feature values can be recovered. In particular, we present a low rank approximation based reconstruction algorithm. We exploit spectral properties of the graph data and show why noise could be separated from the perturbed graph using low rank approximation. We also show key differences from previous findings of point-wise reconstruction methods on numerical data through empirical evaluations and theoretical justifications.