# The Hermitian Kirchhoff Index and Robustness of Mixed Graph

Authors: Wei Lin; Shuming Zhou; Min Li; Gaolin Chen; Qianru Zhou
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Large-scale social graph data poses significant challenges for social analytic tools to monitor and analyze social networks. The information-theoretic distance measure, namely, resistance distance, is a vital parameter for ranking influential nodes or community detection. The superiority of resistance distance and Kirchhoff index is that it can reflect the global properties of the graph fairly, and they are widely used in assessment of graph connectivity and robustness. There are various measures of network criticality which have been investigated for underlying networks, while little is known about the corresponding metrics for mixed networks. In this paper, we propose the positive walk algorithm to construct the Hermitian matrix for the mixed graph and then introduce the Hermitian resistance matrix and the Hermitian Kirchhoff index which are based on the eigenvalues and eigenvectors of the Hermitian Laplacian matrix. Meanwhile, we also propose a modified algorithm, the directed traversal algorithm, to select the edges whose removal will maximize the Hermitian Kirchhoff index in the general mixed graph. Finally, we compare the results with the algebraic connectivity to verify the superiority of the proposed strategy.


---

## Body

## 1. Introduction

Network science has been an emerging area in big data, cyberspace security, and artificial intelligence [1–4]. Many real-world networks are mixed, such as citation networks, web page link networks, e-mail networks, and information diffusion networks. Mixed networks, just like the underlying one, emerge in the fields of multiagent systems [5, 6], biology [7], and society [8]. Many efficient algorithms have been proposed to resolve the function and topological structure of mixed networks, such as decentralized optimization [9], node anomaly detection algorithm [10], embedding algorithm [11], and magnetic Laplacian [12]. Undoubtedly, further analysis of mixed networks has become an indispensable topic in the research of network science and interdisciplinary.1993, Klein and Randić first proposed resistance distance [13]. Xiao and Gutman [14] uncovered some properties of a resistance matrix. Combining the normalized Laplacian matrix and the transition probability matrix, Chen and Zhang [15] proposed a new degree-Kirchhoff index. Atik et al. [16] extended the resistance distance to the weighted graph. Up to this day, resistance distance has many important applied areas, such as phase transition [17], silicate network [18], electrical network [19, 20], and complex networks [21]. Compared to the calculation of eigenvalues and eigenvectors, the advantage of resistance distance as a metric is that it better reflects the overall nature of the network, and it can reduce the computational complexity in a large-scale network. To the best of my knowledge, the research of resistance distance is mainly carried out in the unweighted and undirected networks. There are few research studies about the resistance distance in mixed networks, which is the motivation of this paper. The focus in this paper is to establish a new resistance distance metric for the mixed networks.As it is known to all, the study of the resistance distance is inseparable from matrix theory. Matrix theory, including Hermitian adjacency matrix [22, 23], Laplacian matrix [24, 25], nonnegative matrix factorization [26], and conditional probability matrix [27], is a powerful tool to deal with graph topology structure and function because it can transform complex calculations into a series of four operations, which are easy to improve computational performance. On the basis of [23], Mohar [28] proposed the Hermitian matrix of the second kind. Yu et al. [29–31] have been devoted to the study of Hermitian spectral theory for mixed graphs. The extension from the underlying graph to the mixed graph is actually an extension from the real field to the complex field. The importance of the Hermitian matrix is becoming increasingly prominent. The matrix construction depends on the graph direction, so how to give the graph direction that meets the conditions is also an urgent problem to be solved. With the development of the Hermitian matrix, more and more models and strategies have been put forward [32–34]. The Randic index has been widely used in network centrality, clustering algorithm, network connectivity, and robustness [35–37]. Meo et al. [38] estimated graph robustness through the Randic Index. Along the direction of the Hermitian matrix, we attempt to introduce the Hermitian resistance matrix and the Kirchhoff index of the general mixed graph to estimate robustness of the mixed graph.In this paper, analogue to pseudoinverse matrix of the Laplacian matrix for underlying graph, we extend the corresponding invertible matrixXℋ for mixed graph. Our main contributions are as follows:(1)
We propose the Hermitian resistance matrix and the Hermitian Kirchhoff index for positive mixed graph and then establish a formula for the determinant and the inverse of the Hermitian resistance matrix(2)
We propose a positive walk algorithm for the general mixed graph(3)
Robustness of the general mixed graph is evaluated by the modified directed traversal algorithm based on the Hermitian Kirchhoff indexThe remainder of the paper is organized as follows. Section1 presents related work of the resistance matrix and the Kirchhoff index. Section 2 introduces the Hermitian Laplacian matrix. In Section 3, we define the Hermitian resistance matrix Rℋ and compute its determinant in the positive mixed graph. In Section 4, we derive formulae for inverse of the Hermitian resistance matrix. Section 5 characterizes the Hermitian Kirchhoff index in the positive mixed graph. The statistical experimental analysis in the general mixed graph is shown in Section 6. Section 7 concludes the paper.


## 2. Hermitian Laplacian Matrix

LetG be a mixed graph with a finite vertices set VG and a subset EG⊆VG×VG. The edge set EG is the union of undirected edges and the directed edges. For convenience, we define the undirected edge as vi↔vj and the directed edge is vi⟶vj if the orientation is from vi to vj. The diagonal matrix D=diagd1,d2,…,dn is the degree matrix, where di is the degree of vi of the underlying graph ΩG. We denote H∗=H¯T. Then, H is a Hermitian matrix if H∗=H. The Hermitian adjacency matrix of a mixed graph is the matrix ℋ∈ℂV×V [22, 23], whose element(1)ηij=1,ifvi↔vj,i,ifvi⟶vj,−i,ifvi←vj,0,otherwise.The value of a mixed walkT=v1v2,…,vk in G is ηT=η12η23,…,ηk−1k. A mixed walk is positive (negative) if ηT=1 (ηT=−1).Lemma 1.
(see [30]). A mixed graph G is positive if and only if, for any two vertices v1andv2, all mixed paths from v1 to v2 have the same value.Lemma 2.
(see [31]). Let G be a connected mixed graph on vertices v1v2,…,vn. If Lℋ=D−ℋ is a positive semidefinite matrix and singular, then 0 is a simple eigenvalue with an eigenvector:(2)1ℋ=1,ηT2¯,ηT3¯,…,ηTn¯T,where Ti is a 1−i-walk in G.The Hermitian Laplacian eigenvalues and orthogonal eigenvectors will be denoted byλi and ui=ui1,ui2,…,uinT, respectively. Denote the unitary matrix:(3)Uℋ=u1,u2,u3,…,un,where un=1/n1ℋ.Then, we have(4)Uℋ∗LℋUℋ=diagλ1,…,λn−1,0,and(5)UℋUℋ∗=Uℋ∗Uℋ=I,i.e.,(6)∑k=1nukiukj¯=∑k=1nuik¯ujk=1,ifi=j,0,ifi≠j.


## 3. Hermitian Resistance Matrix in Positive Mixed Graph

In this section, we establish the relationship between the Hermitian resistance matrix and the Hermitian Laplacian matrix in the positive mixed graph.Lemma 3.
(see [22]). Let G be a mixed graph. Then, the following are equivalent:(1)
Gis a positive(2)
G∼GuLemma 4.
(see [30]). Let G be a positive mixed graph. Then, the following statements hold:(1)
SPℋG=SPAGu, where SPAGu is the spectrum of the adjacency matrix of Gu(2)
SPLℋG=SPLGu, where SPLGu is the spectrum of the Laplacian matrix of GuBy Lemma3 and Lemma 4, we give the definition of n×n orientation matrix Oℋ∈ℂ:(7)Oℋ=1ηT2¯⋱ηTn¯.Then, we establish the relationship between the Hermitian matrix and the corresponding matrix in the underlying graph by the orientation matrixOℋ.Lemma 5.
(see [22]). Let G be a positive mixed graph on n vertices and ℋ and A be the Hermitian adjacency matrix and the adjacency matrix, respectively. For a diagonal matrix Oℋ=diag1,ηT2¯,…,ηTn¯, we have(8)Oℋ∗ℋOℋ=A.Corollary 1.
LetG be a positive mixed graph on n vertices, Lℋ be the Hermitian Laplacian matrix, and L be the Laplacian matrix of the underlying graph. For the orientation matrix Oℋ=diag1,ηT2¯,…,ηTn¯, we have Oℋ∗LℋOℋ=L.Now, we denote(9)Jℋ=1ℋ1ℋ∗.Therefore,(10)Uℋ∗JℋUℋ=Uℋ∗1ℋUℋ∗1ℋ∗=diag0,0,…,n.By equations (4) and (10), we have(11)Uℋ∗Lℋ+1nJℋUℋ=diagλ1,…,λn−1,1.The matrixLℋ+1/nJℋ is nonsingular, and we define its inverse(12)Xℋ=Lℋ+1nJℋ−1.Similarly, we have the following corollary.Corollary 2.
LetG be a positive mixed graph on n vertices and X=L+1/nJ−1, where J denote the square with all entries equal to 1. Then, Xℋ is Hermitian and(13)Oℋ∗XℋOℋ=X.Now, we apply this process to the resistance matrix.Theorem 1.
LetG is a positive mixed graph and R is the resistance matrix of the underlying graph; then, the Hermitian resistance matrix is(14)Rℋ=OℋROℋ∗.Proof 1.
By Theorem3 and the definition of resistance matrix, we have(15)OℋROℋ∗=x11⋱xnnOℋJOℋ∗+OℋJOℋ∗x11⋱xnn−OℋXOℋ∗=x11⋱xnnJℋ+Jℋx11⋱xnn−Xℋ=Rℋ,where xii is the diagonal member of X.In view of Theorem1, we have(16)Uℋ∗Rℋ∗Uℋ=Uℋ∗x11⋱xnnJℋ+Jℋx11⋱xnn−2XℋUℋ,(17)Rℋ=−2λ10…0n∑i=1nu1i¯ηTi¯xii0−2λ2…0n∑i=1nu2i¯ηTi¯xii⋮⋮⋱⋮⋮00…−2λn−1n∑i=1nu2n−1,i¯ηTi¯xiin∑i=1nu1iηTixiin∑i=1nu2iηTixii…n∑i=1nun−1,iηTixii2∑i=1n−11λi=−2λ10…0n∑i=1nu1i¯ηTi¯xii0−2λ2…0n∑i=1nu2i¯ηTi¯xii⋮⋮⋱⋮⋮00…−2λn−1n∑i=1nu2n−1,i¯ηTi¯xii00…0Sℋ+2∑i=1n−11λi,where(18)Sℋ=n2∑i=1n−1λi∑k=1nuik¯ηTk¯xkk∑t=1nuitηTtxtt=n2∑k=1n∑t=1nηTk¯xkkηTtxtt∑i=1n−1uitλiuik¯=n2∑t=1n∑k=1nηTtxttηTk¯xkkLℋtk=n2xii,x22,…,xnnDℋ∗LℋDℋxii,x22,…,xnn′.Therefore, we have(19)Rℋ=−1n−12n−1∏i=1n−1λiSℋ+2∑i=1n−11λi=−1n−12n−1ntGSℋ+2∑i=1n−11λi,where tG is the number of spanning trees of the G.


## 4. Inverse of the Hermitian Resistance Matrix

In this section, we will show that the Hermitian resistance matrices are nonsingular and derive a formula for the inverse of them.Fori=1,2,…,n, we define the n×1 vector ω=ω1,ω2,…,ωnT, such that(20)ωi=2ηTi¯−∑j∼iηTj¯rℋi,j.Theorem 2.
LetG be a positive mixed graph on n vertices and Lℋ be the Hermitian Laplacian matrix associated with G. If the X˜ℋ=diagx11,x22,…,xnn and ω are defined as above, then(21)ω=LℋX˜ℋ1ℋ+2n1ℋ.Proof 2.
Letdi be the degree of vertex i. According to Lℋ+1/nJℋXℋ∗=I, we have(22)dixii−ηTi∑j∼iηTj¯xij¯+1nηTi∑j=1nηTj¯xij¯=1.
Then,(23)diixii−ηTi∑j∼iηTj¯xij¯+1n=1.
Thus,(24)∑j∼iηTj¯xij¯=ηTi¯diixii+ηTi¯1n−ηTi¯.
Now, fori=1,2,…,n, we have(25)ωi=2ηTi¯−∑j∼iηTjrℋi,j=2ηTi¯−∑j∼iηTj¯rℋi,j=2ηTi¯−∑j∼iηTi¯xii+ηTi¯xjj−2ηTj¯xij=2ηTi¯−ηTi¯dixii−ηTi¯∑j∼ixjj+2∑j∼iηTj¯xij=ηTi¯dixii−ηTi¯∑j∼ixjj+2nηTi¯By24.
Hence,ω=Lℋ∗X˜ℋ1ℋ+2/n1ℋ.Now, by Theorem2, we have(26)1ℋ∗ω=2n1ℋ∗1ℋ=2.Theorem 3.
LetG be a positive mixed graph on n vertices. Let Lℋ and Rℋ be the Hermitian Laplacian matrix and the Hermitian resistance matrix, respectively. If the n×1 vector xℋ˜=Xℋ˜1ℋ, then(27)ω∗Rℋω=2xℋ˜∗Lℋxℋ˜+8ntraceLℋ†.Proof 3.
By Theorem2, we have(28)ω∗Rℋω=1ℋ∗Xℋ˜Lℋ∗+2n1ℋ∗RℋLℋXℋ˜1ℋ+2n1ℋ=1ℋ∗Xℋ˜Lℋ∗RℋLℋXℋ˜1ℋ+2n1ℋ∗RℋLℋXℋ˜1ℋ+2n1ℋ∗Xℋ˜Lℋ∗Rℋ1ℋ+4n21ℋ∗Rℋ1ℋ.
In view of Theorem1, we obtain(29)Lℋ∗RℋLℋ=−2Lℋ∗XℋLℋ=−2Lℋ∗Lℋ†Lℋ=−2Lℋ.
That is,(30)1ℋ∗Xℋ˜Lℋ∗RℋLℋXℋ˜1ℋ=−2xℋ˜∗Lℋxℋ˜.
Then,(31)2n1ℋ∗Xℋ˜Lℋ∗Rℋ1ℋ=2xℋ˜∗Lℋxℋ˜.
In a similar way,(32)2n1ℋ∗RℋLℋXℋ˜1ℋ=2xℋ˜∗Lℋxℋ˜.
Finally,(33)4n21ℋ∗Rℋ1ℋ=8ntraceXℋ˜−1=8ntraceLℋ†.
Applying equations (32)–(35), we obtain(34)ω∗Rℋω=2xℋ˜∗Lℋxℋ˜+8ntraceLℋ†.
Obviously,ω∗Rℋω is a positive definite matrix.Next, we show that the Hermitian resistance matrix is nonsingular and establish the inverse of them.Theorem 4.
LetG be a positive mixed graph on n vertices. Let Lℋ and Rℋ be the Hermitian Laplacian Matrix and the Hermitian resistance matrix, respectively. Then, Rℋ is nonsingular and(35)Rℋ−1=−12Lℋ+1ω∗Rℋωωω∗.Proof 4.
By Theorem1, we have(36)Lℋ∗Rℋ+2I=Lℋ∗X˜ℋJℋ+2nJℋ=ω1ℋ∗,Lℋ∗Rℋ+2I∗ω=ω1ℋ∗ω=2ω.
Then,(37)Lℋ∗Rℋω=0.
By Theorem1, Rℋω is nonzero. In view of Lℋ∗1ℋ=0, there exists a nonzero scalar β such that(38)Rℋω=β1ℋ,β=12ω∗Rℋω.
That is,(39)Rℋω=ω∗Rℋω21ℋ.
Hence,(40)−12Lℋ∗+ωω∗ω∗RℋωRℋ=−12Lℋ∗Rℋ+ωω∗Rℋω∗Rℋω=−12Lℋ∗Rℋ+ω1ℋ∗ω∗Rℋωω∗Rℋω2By39=−12Lℋ∗Rℋ+12ω1ℋ∗=I.By36.
Therefore, the matrixRℋ is nonsingular, and Rℋ−1=−1/2Lℋ+1/ω∗Rℋωωω∗.


## 5. Hermitian Kirchhoff Index in Positive Mixed Graph

In this section, we establish the Hermitian Kirchhoff index in terms of the spectrum ofLℋ in a positive mixed graph.Theorem 5.
LetG be a positive mixed graph on n vertices. Then, the Hermitian Kirchhoff index is(41)Kf=∑i<jηTiηTj¯rℋi,j=n∑k=1n−11λk.Proof 5.
By Theorem1, we have(42)Kf=∑i<jηTiηTj¯rℋi,j=12∑i=1n∑j=1nri,j=n∑k=1n−11λk.


## 6. Experimental Analysis of Hermitian Kirchhoff Index in General Mixed Graph

According to Lemma5, we propose a positive walk algorithm (see Algorithm 1) to give a positive direction for a given undirected graph G.Algorithm 1: The positive walk algorithm.
Input: The adjacency matrix An×nOutput: The Hermitian adjacency matrix Hn×n(1)
LetO be a null matrix(2)
LetT=−1,1,−i,i(3)
LetO00=1.(4)
Randomly select an element ofT\−1 for O11(5)
for each i in 2,ndo(6)
Randomly select an element ofT for Oii(7)
for each j in 0,ido(8)
ifOjj=−Oii and Aij=1then(9)
T\Oii(10)
Randomly select an element ofT for Oii(11)
end if(12)
end for(13)
end for(14)
H=OAO∗In the real world, not all mixed graphs are positive. IfLℋ is nonsingular, we compute the Hermitian resistance matrix by the Moore–Penrose generalized inverse L† of the Hermitian Laplacian matrix of the mixed graph:(43)rℋi,j=Lℋ†ii+Lℋ†jj−Lℋ†ij−Lℋ†ji.We establish the Hermitian Kirchhoff index in terms of the Hermitian resistance matrix in a mixed graph.Theorem 6.
LetG be a mixed graph on n vertices. Then, the Hermitian Kirchhoff index is(44)Kf=∑i<jrℋi,j.There is a close relationship between the Kirchhoff index and the robustness of network, for example, the bigger the Kirchhoff index, the lower the ability of network to function in an emergency situation. The Kirchhoff index and the robustness of the network are negative correlation. Further more, algebraic connectivity is also widely used to measure the robustness of networks; however, algebraic connectivity is positively correlated with robustness. That is to say, algebraic connectivity is negatively correlated with the Kirchhoff index. Next, we will use Hermitian algebraic connectivity and Hermitian Kirchhoff index to measure the robustness of the general mixed graph, as a comparison of different robustness measures. In order to verify the rationality and applicability of our suggestion, we propose a directed traversal algorithm (see Algorithm2) to obtain the edge set Emax whose removal from a mixed graph G will maximize the Hermitian Kirchhoff index. Then, we compare it with the results of algebraic connectivity. Peng et al. [39] investigated the robustness of undirected mesh graphs. We generalize mixed mesh graphs to random graphs.Algorithm 2:The directed transversal algorithm.
Input: The mixed graph GOutput: Edge set Emax(1)
Random select an edgee0 of the mixed graph G(2)
Obtain the Hermitian resistance matrixH of G−e0(3)
Calculate theKG−e0 and initialize Kmax=KG−e0(4)
for each edge e∈EGdo(5)
removee from G(6)
calculateKG−e(7)
ifKG−e>Kmaxthen(8)
Kmax=KG−e(9)
Emax=e(10)
else(11)
ifKG−e=Kmaxthen(12)
Emax=Emax∪e(13)
end if(14)
end if(15)
end forWe take two E-R mixed graphs as examples. A mixed graph of 12 points is established as in Figure1 and a mixed graph of 34 points is established as in Figure 2. Then, we use the directed traversal algorithm (see Algorithm 2) to calculate Emax in the graphs, and we show the result in Table 1.Figure 1
A mixed graph of 12 points.Figure 2
A mixed graph of 34 points.Table 1
Data statistics of the Hermitian Kirchhoff index after the edge is removed.
Mixed graphRemoved edgeKmaxλminG125,8139.25500.1381G3417,7470.93810.5091


## 7. Conclusion

Many strategies of community detection in social networks have been developed, among them the spectral clustering based on the resistance matrix is widely used in community detection. In this paper, we focus on the Hermitian resistance matrix for positive mixed graphs and general mixed graphs. The Hermitian resistance matrix is a generalization for the resistance matrix in underlying graphs. In addition, we derive the formulae for the determinant, inverse of the Hermitian resistance matrix, and obtain the Hermitian Kirchhoff index. In order to show the practicability of the Hermitian matrix, we utilize the Hermitian Kirchhoff index to analyze the robustness of general mixed networks. Furthermore, we put forward the positive walk algorithm and the directed graph traversal algorithm. Our future work will apply the Hermitian matrices on algorithms for mining key nodes of directed networks and community detection.



---

*Source: 5534472-2021-06-30.xml*