The Hermitian Kirchhoff Index and Robustness of Mixed Graph

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 resistan...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical problems in engineering 2021, Vol.2021, p.1-10
Main Authors: Lin, Wei, Zhou, Shuming, Li, Min, Chen, Gaolin, Zhou, Qianru
Format: Article
Language:English
Subjects:
Algorithms
Distance measurement
Eigenvalues
Eigenvectors
Graph theory
Information theory
Mathematical problems
Phase transitions
Robustness
Social networks
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1024-123X
1563-5147
DOI:10.1155/2021/5534472