# More on Spectral Analysis of Signed Networks

Authors: Guihai Yu; Hui Qu
Journal: Complexity
 (2018)

---

## Abstract

Spectral graph theory plays a key role in analyzing the structure of social (signed) networks. In this paper we continue to study some properties of (normalized) Laplacian matrix of signed networks. Sufficient and necessary conditions for the singularity of Laplacian matrix are given. We determine the correspondence between the balance of signed network and the singularity of its Laplacian matrix. An expression of the determinant of Laplacian matrix is present. The symmetry about1 of eigenvalues of normalized Laplacian matrix is discussed. We determine that the integer 2 is an eigenvalue of normalized Laplacian matrix if and only if the signed network is balanced and bipartite. Finally an expression of the coefficient of normalized Laplacian characteristic polynomial is present.


---

## Body

## 1. Introduction

Social networks represent a large proportion of the complex socioeconomic organization in modern society which represent social entities including countries, corporations, or people. These entities interconnected through a wide range of social ties such as political treaties, commercial trade, friend, and collaboration. To display the ally/enemy, friend/foe, and trust/distrust relationships, the social system can be well represented by a signed network in which an edge of the network is assigned to be positive if two individuals are ally, friendship, trust, and negative if they are enemy, foe, and distrust. The origin of the study of signed networks can be tracked back to the work of Heider [1]. The use of signed networks was then proposed by Cartwright and Harary [2] to model the existence of balance/unbalance in the social networks.As we know, graphs are very useful ways of presenting information about signed networks. However, when there are many actors and/or many kinds of relations, they can become so visually complicated that it is very difficult to see patterns. It is also possible to present information about signed networks in the form of matrices. Representing the information in this way also allows the application of mathematical and computer tools to summarize and find patterns. Up to now, some matrices are employed by signed networks analysts in a number of different ways. This is the so-calledspectral graph theory, which is a branch of mathematical science. Its idea is to exploit numerous relationship between the structure of a network (graph) and the spectrum of some matrix (or collection of matrices) associated with the network (graph). There are many different matrices that are employed, including adjacency matrix, Laplacian matrix, and normalized Laplacian matrix. The goal of this paper is to investigate some properties of Laplacian matrix and normalized Laplacian matrix of signed networks and exploit some relation between these matrices and signed networks.LetG be an undirected network of order n with vertex set V(G)={v1,v2,…,vn} and edge set E(G). The adjacency matrix A(G)=(aij)n×n of G is defined as follows: aij=1 if vi and vj are adjacent and aij=0 otherwise. A signed network Γ=(G,σ) consists of a network G=(V,E), referred to as its underlying network, and a sign function σ:E→{+,-}. Theadjacency matrix of Γ is A(Γ)=(aijσ) with aijσ=σ(vivj)aij, where aij is an element in the adjacency matrix of the underlying network G and vivj is an edge of G. If all edges are signed positive, the adjacency matrix A(G,σ) is exactly the ordinary adjacency matrix A(G). Let DΓ=diag⁡d1,d2,…,dn be a diagonal matrix where di is the degree of vertex vi in its underlying network. TheLaplacian matrix of Γ, denoted by L(Γ), is defined as D(Γ)-A(Γ). The matrix D-1/2L(Γ)D-1/2 is said to benormalized Laplacian matrix of Γ, denoted by L(Γ).A signedi1-ik-walk W in a signed network Γ is a sequence of vertices and edges W:vi1e12vi2e23vi3⋯vik-1e(k-1)kvik such that es(s+1)=visvis+1∈E(Γ) (s=1,2,…,k-1). An i1-ik-walk W is calledeven (odd) if k is even (odd). The sign of a signed walk W=v1e12v2e23⋯vl is sgn⁡(W)=a12σa23σ⋯a(l-1)lσ and ei(i+1)=vivi+1 (i=1,2,…,l-1). A signed walk W isbalanced (unbalanced) if sgn⁡(W)=1 (sgn⁡(W)=-1). A signed cycle is calledbalanced (unbalanced) if its sign is +1 (−1). A signed networks is calledbalanced (resp. unbalanced) if each its signed cycle is balanced (resp. unbalanced).Suppose thatΓ=(G,σ) is a signed network. A signed function θ:V→{+1,-1} is a switching function if Γ is transformed to a new signed network Γθ=(G,σθ) by θ such that the underlying graph remains the same and the sign function is defined by σθ(e)=θ(vi)σ(e)θ(vj) for an edge e=vivj. Let Γ1=(G,σ1) and Γ2=(G,σ2) be two signed networks with the same underlying graph. We call Γ1 and Γ2switching equivalent and write Γ1~Γ2, if there exists a switching function θ such that Γ2=Γ1θ. Switching preserves some signed-graphic invariants such as the sign of cycles and spectrum of combinatorial matrices (adjacency matrix, normalized Laplacian matrix).This paper is organized as follows. In Section2, we study some properties of Laplacian matrix of signed networks. Sufficient and necessary conditions for the singularity of Laplacian matrix are given. The correspondence between the balance of signed network and the singularity of its Laplacian matrix is determined. An expression of the determinant of Laplacian matrix is present. In Section 3, the symmetry about 1 of eigenvalues of normalized Laplacian matrix is discussed. Sufficient and necessary condition for that the integer 2 is an eigenvalue of normalized Laplacian matrix is given. An expression of all coefficients of normalized Laplacian characteristic polynomial is present.


## 2. Laplacian Matrix and Signed Network

Hou et al. [3] introduced the incidence matrix of a signed network as follows. Let S(Γ)=(sij) be an n×m matrix indexed by the vertex and the edge of signed network Γ and (1)sij=+1ifviis the head ofej+1ifviis the tail ofejandσej=+-1ifviis the tail ofejandσej=-0otherwise.The following is immediate by the direct calculation.Theorem 1 (see [3]).
LetΓ be a signed network. Then L(Γ)=S(Γ)ST(Γ) and L(Γ) is a positive semidefinite matrix.Theorem 2.
LetΓ be a connected signed network on vertices v1,v2,…,vn. Then L(Γ) is singular if and only if any 1-i-walk has the same sign. In this case, 0 is a simple eigenvalue with an eigenvector α=(1,sgn⁡W2,sgn⁡W3,…,sgn⁡(Wn))T, where Wi is a 1-i-walk in Γ.Proof.
LetxT=(x1,x2,…,xn)∈Cn. Note that for any nonzero vector x, L(Γ)=0 if and only if ST(Γ)x=0. By (14), ST(Γ)x=0 if and only if xi=aijσxj for any edge e=vivj. Let Wi=u1u2⋯ui be any 1-i-walk and u1=v1,ui=vi. Suppose that L(Γ)=0. So we have (2)x1=a12σx2=a12σa23σx3=⋯=a12σa23σ⋯ai-1iσxi=sgn⁡Wixi,which implies that each 1-i-walk has the same sign.
Note thatsgn-1⁡Wi=sgn⁡(Wi). Hence (3)xT=x1,x2,…,xn=x1,sgn⁡W2x1,sgn⁡W3x1,…,sgn⁡Wnx1=x1αT.This implies that 0 is a simple eigenvalue of L(Γ) with an eigenvector α.
Suppose that any1-i-walk has the sign. Then for any edge eij∈E(Γ), sgn⁡(Wj)=sgn⁡Wi·aijσ. Let xT=(x1,x2,…,xn) be a column vector such that xi=sgn⁡(Wi)x1 (i=2,3,…,n). Then xj=sgn⁡(Wj)x1=sgn⁡(Wi)·aijσx1=xiaijσ, i.e., xi=aijσxj. So we have (4)xTLΓx=∑eij∈EΓxi-aijσxj2=∑eij∈EΓaijσxj-aijσxj2=0.This implies that L(Γ) is singular.Note that for the underlying network it is known that the multiplicity of the eigenvalue 0 of Laplacian matrix is equal to the number of components. For signed network, the following holds from the proof of Theorem2.Theorem 3.
The multiplicity of the eigenvalue 0 of Laplacian matrix of a signed network is the number of components whose Laplacian matrix is singular.Theorem 4 (see [4]).
A signed network is balanced if and only if for each pair of distinct verticesv1,v2 all paths joining v1 and v2 have the same sign.From Theorems2 and 4, we have the following.Theorem 5.
A signed networkΓ is balanced if and only if L(Γ) is singular.The following is immediate from Theorem5.Theorem 6.
The Laplacian matrix of a signed network is singular if and only if the Laplacian matrix of any its cycles is singular. In particular, the Laplacian matrix of any acyclic graph is singular.In [5], authors determined the determinant of the Laplacian matrix of mixed graphs. Here by the similar method we shall extend it to the case for signed graphs.Theorem 7.
det ⁡ L ( C ) = 2 [ 1 - sgn ⁡ ( C ) ] for any signed cycle C.Proof.
LetC be a signed cycle with vertex set V(C)={v1,v2,…,vn} and edge set E(C)={e1,e2,…,en} such that ei=vivi+1 (1≤i≤n-1) and en=vnv1. For the incidence matrix S(C), we expand its the first row (5)det⁡SC=∏i=1nsiei+-1n+1s1en∏i=2nsiei-1.By directly calculation and the fact that sieisjej=-σ(e)aij=-aijσ for any edge ei=vivi+1. It follows that (6)det⁡LC=det⁡SC·det⁡STC=2-2sgn⁡C.So the result holds.Theorem 8.
LetΓ be a signed unicyclic network with a cycle C. Then (7)det⁡LΓ=det⁡LC=21-sgn⁡C.Proof.
By Theorem7, the results hold if Γ is a signed cycle. Assume that Γ has a pendant vertex, say u. Let v be the unique neighbor of u in Γ. Let e be the edge joining u and v. After permutations, the first row and the first column of S(Γ) correspond to the vertex u and the edge e, respectively. Note that S(Γ) is a square matrix since Γ is unicyclic. We get the determinant of S(Γ) by expanding along the first row as follows:(8)det⁡SΓ=sue·det⁡SΓ′,where Γ′ is a signed subgraph obtained from Γ by deleting the vertex u. Hence we have (9)det⁡LΓ=det⁡SΓ·det⁡STΓ=det⁡SΓ′·det⁡STΓ′=det⁡LΓ′.Repeating the above finite steps, we have det⁡L(Γ)=det⁡L(C).LetΓ be a connected signed network. We call a subnetwork H asan essential spanning subnetwork of Γ if either Γ is balanced and H is a spanning tree of Γ, or else Γ is not balanced, V(Γ)=V(H) and every component of H is a unicyclic signed network in which the unique cycle is negative. By E(Γ) we denote the set of all essential spanning subnetworks of Γ.Theorem 9.
LetΓ be a connected signed network. Then(10)det⁡LΓ=∑l=04lbl,where bl is the number of essential spanning subgraphs which contain l unbalanced cycles and b0=0.Proof.
It is evident that the result holds ifΓ is a tree. Assume that Γ contains some cycles. By Cauchy-Binet Theorem [6] and L(Γ)=S(Γ)·ST(Γ), we have (11)det⁡LΓ=∑E′⊆EΓ;E′=VΓdet⁡SVΓ,E′·det⁡STVΓ,E′,where S[V(Γ),E′] is a square submatrix of S(Γ).
Note thatS[V(Γ),E′] is the vertex-edge incidence matrix of a spanning subgraph of Γ, say HE′, with the edge set E′=VΓ. Moreover, det⁡LHE′=S[V(Γ),E′]·ST[V(Γ),E′]. Note that every component of HE′ is unicyclic and HE′∈E(Γ). By Theorem 8, we have (12)det⁡LΓ=∑E′⊆EΓ;E′=VΓdet⁡SVΓ,E′·det⁡STVΓ,E′=∑E′⊆EΓ;E′=VΓdet⁡LHE′=∑H∈EΓdet⁡LH=∑H∈EΓ∏i=1bl21-sgn⁡CiHwheresgn⁡CiH=-1=∑l=04lbl.So the result holds.The following is immediate from Theorem9, which is coincident with the definition of balance of signed network.Theorem 10.
LetΓ be a signed network. Then Γ is balanced if and only if each cycle of Γ is balanced cycle.


## 3. Normalized Laplacian Matrix and Signed Network

For a signed networkΓ, the normalized Laplacian matrix L(Γ) is symmetric and positive semidefinite [7], so its eigenvalues are real and nonnegative, denoted by 0≤λ1≤λ2≤⋯≤λn. Firstly we recall some properties of normalized Laplacian matrix.Lemma 11 (see [7]).
LetΓ be a signed network on n vertices with normalized Laplacian eigenvalues λ1≤λ2≤⋯≤λn. Then λn≤2.Lemma 12 (see [3, 7]).
LetΓ1 and Γ2 be two signed networks with the same underlying network. Then Γ1~Γ2 if and only if L(Γ1) and L(Γ2) are signature similar.In [8], the symmetry about 1 of eigenvalues for bipartite signed network was present as follows. Here we present a stronger result.Theorem 13 (see [8]).
LetΓ=(G,σ) be a bipartite signed network. If λ is an eigenvalue of L(Γ), then 2-λ is also an eigenvalue of L(Γ).Theorem 14.
LetΓ be a connected signed network. Then Γ is bipartite if and only if all eigenvalues of L(Γ) are symmetric about 1 (including multiplicities); i.e., for each eigenvalue λi, 2-λi is also an eigenvalue of L(Γ).Proof.
It suffices to verify thatI-L(Γ) and -(I-L(Γ)) have the same spectrum. Note that I-L(Γ)=D-1/2A(Γ)D-1/2. Γ is bipartite if and only if D-1/2A(Γ)D-1/2 can be expressed as 0BBT0. It is evident that (13)-I00I0-B-BT0-I00I=0BBT0.This yields to the result.From Lemma11, the integer 2 is the upper bound of normalized Laplacian eigenvalues. In this sequel, we give a sufficient and necessary condition for that the integer 2 is an eigenvalue of normalized Laplacian matrix.Theorem 15.
LetΓ be a connected signed network. Then 2 is an eigenvalue of L(Γ) if and only if Γ is a balanced bipartite signed network.Proof.
By Courant-Fischer theorem, we have(14)λn=supf≠0⁡∑u~vfu-σuvfv2∑vf2vdv.Assume that 2 is an eigenvalue of L(Γ) with nonzero eigenvector yT=(y1,y2,…,yn). By Lemma 11 and (14), yi=-σ(vivj)yj for any edge e incident to vi and vj. So V(Γ) can be partitioned into two parts such that no edge existing between any two vertices in every part. This means that Γ is bipartite. For any even cycle C2k=v1v2⋯v2kv1, we have (15)y1=-σv1v2y2=σv1v2σv2v3y3=-σv1v2σv2v3σv3v4y4=⋯=-σv1v2σv2v3⋯σv2k-1v2ky2k.Moreover, y1=-σ(v1v2k)y2k. So σ(v1v2)σ(v2v3)⋯σ(v2k-1v2k)=σ(v1v2k) and C2k is balanced. This implies that Γ is balanced.
IfΓ is balanced bipartite, then 0 is an eigenvalue of L(Γ). By Theorem 14 and Lemma 12, 2 is an eigenvalue of L(Γ).As we know, the coefficients of characteristic polynomial of adjacency (Laplacian) matrix are related to the graph structure. In [9], expressions of coefficients of (Laplacian) characteristic polynomial was present. We would present the expression of the coefficients of normalized Laplacian characteristic polynomial. Firstly, we recall the Sachs formula for the coefficients of adjacency characteristic polynomial of signed networks. Here some definitions are needed. Anelementary figure is the graph K2 or the cycle. Abasic figure is the disjoint union of elementary figures.Lemma 16 (see [9]).
LetΓ=(G,σ) and ϕ(Γ,x)=xn+a1xn-1+⋯+an be a signed network and its adjacency characteristic polynomial, respectively. Then (16)ai=∑B∈Bi-1pB2cBσB,where Bi is the set of basic figures on i vertices in G, p(B) is the number of components of B, and c(B) is the set of cycles in B and σ(B)=∏C∈c(B)sgn⁡(C).Letψ(Γ,x) be the normalized Laplacian characteristic polynomial of Γ. By the definition of normalized Laplacian matrix, we have (17)ψΓ,x=det⁡xI-LΓ=det⁡xI-D-1/2LΓD-1/2=det⁡xI-I+D-1/2AΓD-1/2=det⁡x-1I+D-1/2AΓD-1/2=x-1n+c1x-1n-1+⋯+cn-1x-1+cn.Theorem 17.
LetΓ be a signed network on n vertices and ψ(Γ,x)=(x-1)n+c1(x-1)n-1+⋯+cn-1(x-1)+cn be its normalized Laplacian characteristic polynomial. Then (18)ck=∑B∈Bk-1pB2cBσB1Dk,where Bk is the set of basic figures on k vertices in G, p(B) is the number of components of B, c(B) is the set of cycles in B, σ(B)=∏C∈cBsgn⁡(C), Dk=∏vi∈V(B)di, and di is the degree of vi in Γ.Proof.
Note that(19)ψΓ,x=det⁡x-1I+D-1/2AΓD-1/2=-1ndet⁡1-xI-D-1/2AΓD-1/2.Set (20)det⁡1-xI-D-1/2AΓD-1/2=x-1n+c1′x-1n-1+⋯+cn-1′x-1+cn′.So ck=(-1)kck′. Moreover, (-1)kck′ equals to the sum of all k×k minors of D-1/2A(Γ)D-1/2. Then ck is the sum of all k×k minors of D-1/2A(Γ)D-1/2. It is evident that each such k×k minor of D-1/2A(Γ)D-1/2 is the product of the corresponding k×k minors of D-1/2, A(Γ), and D-1/2, respectively. Furthermore, any k×k minor of A(Γ) is the determinant of adjacency matrix of an induced subgraph of Γ with k vertices. So this result holds from Lemma 16.


## 4. Conclusion

Recently, there are some results on the spectral theory of signed graphs [10–18]. In this paper we investigate some properties of (normalized) Laplacian matrix of signed network and present a correspondence between the balance of signed networks and the singularity of Laplacian matrix. Moreover, we give the expressions of determinant of Laplacian matrix and coefficients of normalized Laplacian characteristic polynomial, respectively. Actually there are some other aspects of spectrum of signed graphs, which can be investigated. It will be left to our future study. In addition, there are many spectrum-based invariants, which are widely investigated, such as graph energy (e.g., graph theory [19, 20], incidence energy [21], and matching energy [22, 23]), HOMO-LUMO index [24, 25], and inertia [26–29]. In the future, we would like to study some properties of these spectrum-based indices of signed networks.



---

*Source: 3467158-2018-10-16.xml*