×

Frustration and isoperimetric inequalities for signed graphs. (English) Zbl 1358.05133

Summary: Let \(G_\sigma=(V,E,\sigma)\) be a connected signed graph. Using the equivalence between signed graphs and 2-lifts of graphs, we show that the frustration index of \(G_\sigma\) is bounded from below and above by expressions involving another graph invariant, the smallest eigenvalue of the (signed) Laplacian of \(G_\sigma\). From the proof, stricter bounds are derived. Additionally, we show that the frustration index is the solution to a \(l^1\)-norm optimization problem over the 2-lift of the signed graph. This leads to a practical implementation to compute the frustration index. Also, leveraging the 2-lifts representation of signed graphs, a straightforward proof of Harary’s theorem on balanced graphs is derived. Finally, real world examples are considered.

MSC:

05C22 Signed and weighted graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bandeira, A. S.; Singer, A.; Spielman, D. A., A cheeger inequality for the graph connection laplacian, SIAM J. Matrix Anal. Appl., 34, 4, 1611-1630 (2013) · Zbl 1287.05081
[2] Belardo, F., Balancedness and the least eigenvalue of laplacian of signed graphs, Linear Algebra Appl., 446, 133-147 (2014) · Zbl 1285.05112
[3] Bilu, Y.; Linial, N., Lifts, discrepancy and nearly optimal spectral gap, Combinatorica, 26, 495-519 (2006) · Zbl 1121.05054
[4] Boué, S.; Talikka, M.; Westra, J. W.; Hayes, W.; Di Fabio, A.; Park, J.; Schlage, W. K.; Sewer, A.; Fields, B.; Ansari, S.; Martin, F.; Veljkovic, E.; Kenney, R.; Peitsch, M. C.; Hoeng, J., Causal biological network database: A comprehensive platform of causal biological network models focused on the pulmonary and vascular systems, Database, 2015, bav030 (2015)
[6] DasGupta, B.; Enciso, G.; Sontag, E.; Zhang, Y., Algorithmic and complexity results for decompositions of biological networks into monotone subsystems, Biosystems, 90, 1, 161-178 (2007)
[9] Gournay, A., An isoperimetric constant for signed graphs, Expo. Math., 34, 3, 339-351 (2016) · Zbl 1342.05085
[10] Harary, F., On the notion of balance of a signed graph, Michigan Math. J., 2, 2, 143-146 (1953) · Zbl 0056.42103
[11] Harary, F.; Kabell, J. A., A simple algorithm to detect balance in signed graphs, Math. Social Sci., 1, 1, 131-136 (1980) · Zbl 0497.05056
[12] Hou, Y. P., Bounds for the least laplacian eigenvalue of a signed graph, Acta Math. Sinica, 21, 4, 955-960 (2005) · Zbl 1080.05060
[13] Hou, Y. P.; Li, J.; Pan, Y.; Dewey, C., On the laplacian eigenvalues of signed graphs, Linear Multilinear Algebra, 51, 1 (2003)
[14] Huffner Falk, N. R.; Betzler, N., Optimal edge deletions for signed graph balancing, (Proc. 6th WEA. Proc. 6th WEA, LNCS, vol. 4525 (2007)), 297-310 · Zbl 1203.68125
[15] Iacono, G.; Altafini, C., Monotonicity, frustration, and ordered response: an analysis of the energy landscape of perturbed large-scale biological networks, BMC Syst. Biol., 4, 83 (2010)
[16] Iacono, G.; Ramezani, F.; Soranzo, N.; Altafini, C., Determining the distance to monotonicity of a biological network: a graph-theoretical approach, IET Syst. Biol., 4, 3, 223-235 (2010)
[17] Li, H.-H.; Dewey, C., Note on the normalized laplacian eigenvalues of signed graphs, Aust. J. Combin., 44 (2009) · Zbl 1177.05050
[19] Martin, F.; Thomson, T.; Sewer, A.; Drubin, D.; Mathis, C.; Weisensee, D.; Pratt, D.; Hoeng, J.; Peitsch, M., Assessment of network perturbation amplitudes by applying high-throughput data to causal biological networks, BMC Syst. Biol., 6, 54 (2012)
[20] Mohar, B., Isoperimetric inequalities, growth, and the spectrum of graphs, Linear Algebra Appl., 103, 119-131 (1988) · Zbl 0658.05055
[21] Read, K. E., Cultures of the central highlands, new guinea, Southwes. J. Anthropol., 1-43 (1954)
[22] Sontag, E. D., Monotone and near-monotone biochemical networks, Syst. Synth. Biol., 1, 2, 59-87 (2007)
[23] Soranzo, N.; Ramezani, F.; Iacono, G.; Altafini, C., Decompositions of large-scale biological systems based on dynamical properties, Bioinformatics, 28, 1, 76-83 (2012)
[24] Thomson, T.; Sewer, A.; Martin, F.; Belcastro, V.; Frushour, B.; Gebel, S.; Park, J.; Schlage, W.; Talikka, M.; Vasilyev, D.; Westra, J.; Hoeng, J.; Peitsch, M., Quantitative assessment of biological impact using transcriptomic data and mechanistic network models, Toxicol. Appl. Pharmacol., 272, 3, 863-878 (2013)
[25] Vasilyev, D.; Thomson, T.; Frushour, B.; Martin, F.; Sewer, A., An algorithm for score aggregation over causal biological networks based on random walk sampling, BMC Res. Notes, 7, 516 (2014)
[26] Wang, H.; Nie, F.; Huang, H., Robust distance metric learning via simultaneous l1-norm minimization and maximization, (ICML (2014)), 1836-1844
[28] Zaslavsky, T., Signed graphs, Discrete Appl. Math., 4, 1, 47-74 (1982) · Zbl 0476.05080
[29] Zaslavsky, T., Balanced decompositions of a signed graph, J. Combin. Theory Ser. B, 43, 1, 1-13 (1987) · Zbl 0624.05056
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.