The Hermitian Kirchhoff index and robustness of mixed graph. (English) Zbl 1512.05097
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.
MSC:
| 05C09 | Graphical indices (Wiener index, Zagreb index, Randić index, etc.) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
References:
| [1] | Jiang, J.; An, B.; Jiang, Y.; Lin, D., Context-aware reliable crowdsourcing in social networks, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 50, 2, 617-632 (2017) · doi:10.1109/TSMC.2017.2777447 |
| [2] | Rathore, S.; Sharma, P. K.; Loia, V.; Jeong, Y.-S.; Park, J. H., Social network security: issues, challenges, threats, and solutions, Information Sciences, 421, 43-69 (2017) · doi:10.1016/j.ins.2017.08.063 |
| [3] | He, Q.; Wang, X.; Mao, F., CAOM: a community-based approach to tackle opinion maximization for social networks, Information Sciences, 513, 252-269 (2020) · doi:10.1016/j.ins.2019.10.064 |
| [4] | Lin, W.; Li, M.; Zhou, S.; Liu, J.; Chen, G.; Gu, Z., Phase transitions in normalized cut of social networks, Physics Letters A, 383, 25, 3037-3042 (2019) · Zbl 1475.91257 · doi:10.1016/j.physleta.2019.06.042 |
| [5] | Wang, X.; Yang, G.-H., Fault-Tolerant consensus tracking control for linear multiagent systems under switching directed network, IEEE Transactions on Cybernetics, 50, 5, 1921-1930 (2020) · doi:10.1109/tcyb.2019.2901542 |
| [6] | Liu, Y.; Yang, G.-H., Neural learning-based fixed-time consensus tracking control for nonlinear multiagent systems with directed communication networks, IEEE Transactions on Neural Networks and Learning Systems, 32, 2, 639-652 (2021) · doi:10.1109/TNNLS.2020.2978854 |
| [7] | Wang, T.; Qiu, R. G.; Yu, M.; Zhang, R., Directed disease networks to facilitate multiple-disease risk assessment modeling, Decision Support Systems, 129 (2020) · doi:10.1016/j.dss.2019.113171 |
| [8] | Alipourfard, N.; Nettasinghe, B.; Abeliuk, A.; Krishnamurthy, V.; Lerman, K., Friendship paradox biases perceptions in directed networks, Nature Communications, 11, 1, 1-9 (2020) · doi:10.1038/s41467-020-14394-x |
| [9] | Cui, Z.-X.; Fan, Q.; Jia, C., Momentum methods for stochastic optimization over time-varying directed networks, Signal Processing, 174 (2020) · doi:10.1016/j.sigpro.2020.107614 |
| [10] | Tosyali, A.; Kim, J.; Choi, J.; Kang, Y.; Jeong, M. K., New node anomaly detection algorithm based on nonnegative matrix factorization for directed citation networks, Annals of Operations Research, 288, 1, 457-474 (2020) · Zbl 1436.90031 · doi:10.1007/s10479-019-03508-4 |
| [11] | Wu, Z.; Di, Z.; Fan, Y., An asymmetric popularity-similarity optimization method for embedding directed networks into hyperbolic space, Complexity, 2020, 5 (2020) · doi:10.1155/2020/8372928 |
| [12] | de Resende, B. M. F.; Costa, L. F., Characterization and comparison of large directed networks through the spectra of the magnetic Laplacian, Chaos, 30, 7 (2020) · Zbl 1445.05044 · doi:10.1063/5.0006891 |
| [13] | Klein, D. J.; Randić, M., Resistance distance, Journal of Mathematical Chemistry, 12, 1, 81-95 (1993) · doi:10.1007/bf01164627 |
| [14] | Xiao, W.; Gutman, I., Resistance distance and Laplacian spectrum, Theoretical Chemistry Accounts: Theory, Computation, and Modeling (Theoretica Chimica Acta), 110, 4, 284-289 (2003) · doi:10.1007/s00214-003-0460-4 |
| [15] | Chen, H.; Zhang, F., Resistance distance and the normalized Laplacian spectrum, Discrete Applied Mathematics, 155, 5, 654-661 (2007) · Zbl 1113.05062 · doi:10.1016/j.dam.2006.09.008 |
| [16] | Atik, F.; Bapat, R. B.; Rajesh Kannan, M., Resistance matrices of graphs with matrix weights, Linear Algebra and Its Applications, 571, 41-57 (2019) · Zbl 1411.05105 · doi:10.1016/j.laa.2019.02.011 |
| [17] | Lin, W.; Li, M.; Zhou, S.; Liu, J.; Chen, G.; Zhou, Q., Phase transition in spectral clustering based on resistance matrix, Physics A, 566 (2021) · Zbl 1527.91131 · doi:10.1016/j.physa.2020.125598 |
| [18] | Sardar, M. S.; Pan, X.-F.; Xu, S.-A., Computation of resistance distance and Kirchhoff index of the two classes of silicate networks, Applied Mathematics and Computation, 381, 323-336 (2020) · Zbl 1462.05127 · doi:10.1016/j.amc.2020.125283 |
| [19] | Patterson, S.; Yi, Y.; Zhang, Z., A resistance-distance-based approach for optimal leader selection in noisy consensus networks, IEEE Transactions on Control of Network Systems, 6, 1, 191-201 (2019) · Zbl 1515.93186 · doi:10.1109/tcns.2018.2805639 |
| [20] | Thulasiraman, K.; Yadav, M.; Naik, K., Network science meets circuit theory: resistance distance, Kirchhoff index, and foster’s theorems with generalizations and unification, IEEE Transactions on Circuits and Systems I: Regular Papers, 66, 3, 1090-1103 (2019) · doi:10.1109/tcsi.2018.2880601 |
| [21] | Zhang, T.; Bu, C., Detecting community structure in complex networks via resistance distance, Physica A: Statistical Mechanics and Its Applications, 526 (2019) · doi:10.1016/j.physa.2019.04.018 |
| [22] | Liu, J.; Li, X., Hermitian-adjacency matrices and hermitian energies of mixed graphs, Linear Algebra and Its Applications, 466, 182-207 (2015) · Zbl 1302.05106 · doi:10.1016/j.laa.2014.10.028 |
| [23] | Guo, K.; Mohar, B., Hermitian adjacency matrix of digraphs and mixed graphs, Journal of Graph Theory, 489, 324-340 (2015) · Zbl 1327.05215 · doi:10.1016/j.laa.2015.10.018 |
| [24] | Zhou, J.; Jiang, Z.; Wang, S., Laplacian least learning machine with dynamic updating for imbalanced classification, Applied Soft Computing, 88 (2020) · doi:10.1016/j.asoc.2019.106028 |
| [25] | Yang, Y.; Tu, L.; Guo, T.; Chen, J., Spectral properties of Supra-Laplacian for partially interdependent networks, Applied Mathematics and Computation, 365 (2020) · Zbl 1433.65062 · doi:10.1016/j.amc.2019.124740 |
| [26] | Ma, X.; Zhang, B.; Ma, C.; Ma, Z., Co-regularized nonnegative matrix factorization for evolving community detection in dynamic networks, Information Sciences, 528, 265-279 (2020) · doi:10.1016/j.ins.2020.04.031 |
| [27] | Byun, J.-E.; Song, J., Efficient probabilistic multi-objective optimization of complex systems using matrix-based Bayesian network, Reliability Engineering and System Safety, 200 (2020) · doi:10.1016/j.ress.2020.106899 |
| [28] | Mohar, B., A new kind of Hermitian matrices for digraphs, Linear Algebra and Its Applications, 584, 343-352 (2020) · Zbl 1426.05009 · doi:10.1016/j.laa.2019.09.024 |
| [29] | Yu, G.; Dehmer, M.; Emmert-Streib, F.; Jodlbauer, H., Hermitian normalized Laplacian matrix for directed networks, Information Sciences, 495, 175-184 (2019) · Zbl 1451.05150 · doi:10.1016/j.ins.2019.04.049 |
| [30] | Yu, G.; Qu, H., Hermitian Laplacian matrix and positive of mixed graphs, Applied Mathematics and Computation, 269, 70-76 (2015) · Zbl 1410.05145 · doi:10.1016/j.amc.2015.07.045 |
| [31] | Yu, G.; Liu, X.; Qu, H., Singularity of Hermitian (quasi-)Laplacian matrix of mixed graphs, Applied Mathematics and Computation, 293, 287-292 (2017) · Zbl 1411.05176 · doi:10.1016/j.amc.2016.08.032 |
| [32] | Kang, B.; Wu, K.; Yan, Z.-W.; Yang, J.; Zhao, W.-Z., Exact correlators in the Gaussian Hermitian matrix model, Physics Letters B, 798 (2019) · Zbl 1434.81043 · doi:10.1016/j.physletb.2019.134986 |
| [33] | Dehghan, M.; Shirilord, A., A generalized modified Hermitian and skew-Hermitian splitting (GMHSS) method for solving complex Sylvester matrix equation, Applied Mathematics and Computation, 348, 632-651 (2019) · Zbl 1429.65085 · doi:10.1016/j.amc.2018.11.064 |
| [34] | Truhar, N.; Tomljanović, Z.; Li, R.-C., Perturbation theory for Hermitian quadratic eigenvalue problem C damped and simultaneously diagonalizable systems, Applied Mathematics and Computation, 371 (2020) · Zbl 1433.15019 · doi:10.1016/j.amc.2019.124921 |
| [35] | Bermudo, S.; NRandiápoles, J. E.; Rada, J., Extremal trees for the Randić index with given domination number, Applied Mathematics and Computation, 375 (2020) · doi:10.1016/j.amc.2020.125122 |
| [36] | Martínez-Martínez, C. T.; Méndez-Bermúdez, J. A.; Rodríguez, J. M., Computational and analytical studies of the Randić index in Erdös-Rényi models, Applied Mathematics and Computation, 377 (2020) · Zbl 1462.05094 · doi:10.1016/j.amc.2020.125137 |
| [37] | Dalfó, C., On the Randić index of graphs, Discrete Mathematics, 342, 10, 2792-2796 (2019) · Zbl 1417.05033 · doi:10.1016/j.disc.2018.08.020 |
| [38] | De Meo, P.; Messina, F.; Rosaci, D.; Sarne, G. M. L.; Vasilakos, A. V., Estimating graph robustness through the randic index, IEEE Transactions on Cybernetics, 48, 11, 3232-3242 (2018) · doi:10.1109/tcyb.2017.2763578 |
| [39] | Peng, Y.; Li, J.; He, W., Estimating robustness through Kirchhoff index in mesh graphs, IEEE Access, 8, 111822-111828 (2020) · doi:10.1109/access.2020.3003318 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
