×

Cheeger constants, structural balance, and spectral clustering analysis for signed graphs. (English) Zbl 1429.05120

Summary: We introduce a family of multi-way Cheeger-type constants \(\{h_k^\sigma, k = 1, 2, \ldots, n \}\) on a signed graph \(\varGamma = (G, \sigma)\) such that \(h_k^\sigma = 0\) if and only if \(\varGamma\) has \(k\) balanced connected components. These constants are switching invariant and bring together in a unified viewpoint a number of important graph-theoretical concepts, including the classical Cheeger constant, those measures of bipartiteness introduced by M. Desai and V. Rao [J. Graph Theory 18, No. 2, 181–194 (1994; Zbl 0792.05096)], L. Trevisan [in: Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM). 263–272 (2009; Zbl 1304.05140)], F. Bauer and J. Jost [Commun. Anal. Geom. 21, No. 4, 787–845 (2013; Zbl 1290.05100)], respectively, on unsigned graphs, and the frustration index (originally called the line index of balance by Harary) on signed graphs. We further unify the (higher-order or improved) Cheeger and dual Cheeger inequalities for unsigned graphs as well as the underlying algorithmic proof techniques by establishing their corresponding versions on signed graphs. In particular, we develop a spectral clustering method for finding \(k\) almost-balanced subgraphs, each defining a sparse cut. The proper metric for such a clustering is the metric on a real projective space. We also prove estimates of the extremal eigenvalues of signed Laplace matrix in terms of number of signed triangles (3-cycles).

MSC:

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

References:

[1] Abelson, R. P.; Rosenberg, M. J., Symbolic psycho-logic: A model of attitudinal cognition, Behav. Sci., 3, 1-13 (1958)
[2] Akiyama, J.; Avis, D.; Chvátal, V.; Era, H., Balancing signed graphs, Discrete Appl. Math., 3, 4, 227-233 (1981) · Zbl 0468.05066
[3] Alon, N., Eigenvalues and expanders, Combinatorica, 6, 2, 83-96 (1986), Theory of Computing, Singer Island, Fla, 1984 · Zbl 0661.05053
[4] Alon, N.; Milman, V., \( \lambda_1\), isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, 38, 1, 73-88 (1985) · Zbl 0549.05051
[5] Atay, F. M.; Tunçel, H., On the spectrum of the normalized Laplacian for signed graphs: Interlacing, contraction, and replication, Linear Algebra Appl., 442, 165-177 (2014) · Zbl 1282.05088
[6] Bauer, F.; Jost, J., Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplacian, Comm. Anal. Geom., 21, 4, 787-845 (2013) · Zbl 1290.05100
[7] Bauer, F.; Jost, J.; Liu, S., Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator, Math. Res. Lett., 19, 6, 1185-1205 (2012) · Zbl 1297.05143
[8] Belardo, F., Balancedness and the least eigenvalue of Laplacian of signed graphs, Linear Algebra Appl., 446, 133-147 (2014) · Zbl 1285.05112
[9] Bieche, I.; Maynard, R.; Rammal, R.; Uhry, J. P., On the ground states of the frustration model of a spin glass by a matching method of graph theory, J. Phys. A: Math. Gen., 13, 2553-2576 (1980)
[10] Bilu, Y.; Linial, N., Lifts, discrepancy and nearly optimal spectral gap, Combinatorica, 26, 5, 495-519 (2006) · Zbl 1121.05054
[11] Cameron, P. J., Cohomological aspects of two-graphs, Math. Z., 157, 101-119 (1977) · Zbl 0353.20004
[12] Cameron, P. J.; Seidel, J. J.; Tsaranov, S. V., Signed graphs root lattices and Coxeter groups, J. Algebra, 164, 1, 173-209 (1994) · Zbl 0802.05043
[13] Cameron, P. J.; Wells, A. L., Signatures and signed switching classes, J. Combin. Theory Ser. B, 40, 3, 344-361 (1986) · Zbl 0591.05061
[14] Cartwright, D.; Harary, F., Structural balance: a generalization of Heider’s theory, Psychol. Rev., 63, 5, 277-293 (1956)
[15] N. Cesa-Bianchi, C. Gentile, F. Vitale, G. Zappella, A correlation clustering approach to link classification in signed networks, in: Proceedings of the 25th Conference on Learning Theory, COLT 2012, 2012.
[16] Cheeger, J., A lower bound for the smallest eigenvalue of the Laplacian, (Problems in Analysis (1970), Princeton Univ. Press: Princeton Univ. Press Princeton, N.J.), 195-199, (Papers dedicated to Salomon Bochner, 1969) · Zbl 0212.44903
[17] Chung, F. R.K., (Spectral Graph Theory. Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, vol. 92 (1997), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 0867.05046
[18] S. Costantini, A. Provetti, Graph representations of logic programs: properties and comparison, in: Proceedings of the Sixth Latin American Workshop on Non-monotonic Reasoning, 2010, pp. 1-14.
[19] Das, K. Ch., An improved upper bound for Laplacian graph eigenvalues, Linear Algebra Appl., 368, 269-278 (2003) · Zbl 1020.05040
[20] Desai, M.; Rao, V., A characterization of the smallest eigenvalue of a graph, J. Graph Theory, 18, 2, 181-194 (1994) · Zbl 0792.05096
[21] Dodziuk, J., Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc., 284, 2, 787-794 (1984) · Zbl 0512.39001
[22] Facchetti, G.; Iacono, G.; Altafini, C., Computing global structural balance in large-scale signed social networks, Proc. Natl. Acad. Sci. USA, 108, 52, 20953-20958 (2011)
[23] Germina, K. A.; Hameed, S. K.; Zaslavsky, T., On products and line graphs of signed graphs, their eigenvalues and energy, Linear Algebra Appl., 435, 10, 2432-2450 (2011) · Zbl 1222.05223
[24] Harary, F., On the notion of balance of a signed graph, Michigan Math. J., 2, 2, 143-146 (1953) · Zbl 0056.42103
[25] Harary, F., Structural duality, Behav. Sci., 2, 4, 255-265 (1957)
[26] Harary, F., On the measurement of structural balance, Behav. Sci., 4, 316-323 (1959)
[27] 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
[28] Hou, Y.-P., Bounds for the least Laplacian eigenvalue of a signed graph, Acta Math. Sin. (Engl. Ser.), 21, 4, 955-960 (2005) · Zbl 1080.05060
[29] Hou, Y.-P.; Li, J.-S.; Pan, Y.-L., On the Laplacian eigenvalues of signed graphs, Linear Multilinear Algebra, 51, 1, 21-30 (2003) · Zbl 1020.05044
[30] Jost, J.; Liu, S., Ollivier’s Ricci curvature, local clustering and curvature-dimension inequalities on graphs, Discrete Comput. Geom., 51, 2, 300-322 (2014) · Zbl 1294.05061
[31] Kunegis, J., Applications of structural balance in signed social networks (2014)
[32] Kunegis, J.; Lommatzsch, A.; Bauckhage, C., The Slashdot Zoo: Mining a social network with negative edges, (Proceedings of the 18th International Conference on World Wide Web (2009), ACM), 741-750
[33] J. Kunegis, S. Schmidt, A. Lommatzsch, J. Lerner, E.W. De Luca, S. Albayrak, Spectral analysis of signed graphs for clustering, prediction and visualization, in: SIAM International Conference on Data Mining, SDM, 2010, pp. 559-570.
[34] Kwok, T.-C.; Lau, L.-C.; Lee, Y.-T.; Oveis Gharan, S.; Trevisan, L., Improved Cheeger’s inequality: Analysis of spectral partitioning algorithms through higher order spectral gap, (Proceedings of the 2013 ACM Symposium on Theory of Computing. Proceedings of the 2013 ACM Symposium on Theory of Computing, STOC’13 (2013), ACM: ACM New York), 11-20 · Zbl 1293.05301
[35] Lee, J. R.; Oveis Gharan, S.; Trevisan, L., Multi-way spectral partitioning and higher-order Cheeger inequalities, (Proceedings of the 2012 ACM Symposium on Theory of Computing. Proceedings of the 2012 ACM Symposium on Theory of Computing, STOC’12 (2012), ACM: ACM New York), 1117-1130 · Zbl 1286.05091
[36] Li, H.-H.; Li, J.-S., An upper bound on the Laplacian spectral radius of the signed graphs, Discuss. Math. Graph Theory, 28, 2, 345-359 (2008) · Zbl 1156.05035
[37] Li, H.-H.; Li, J.-S., Note on the normalized Laplacian eigenvalues of signed graphs, Australas. J. Combin., 44, 153-162 (2009) · Zbl 1177.05050
[38] Liu, S., Multi-way dual Cheeger constants and spectral bounds of graphs, Adv. Math., 268, 306-338 (2015) · Zbl 1309.05122
[39] A.W. Marcus, D.A. Spielman, N. Srivastava, Interlacing families I: bipartite Ramanujan graphs of all degrees, in: Proceedings of FOCS, 2013, pp. 529-537; Ann. of Math. 182 (2015) 307-325. · Zbl 1316.05066
[40] Marcus, A. W.; Spielman, D. A.; Srivastava, N., Ramanujan graphs and the solution of the Kadison-Singer problem, (Proceedings of the International Congress of Mathematicians, Vol. III. Proceedings of the International Congress of Mathematicians, Vol. III, Seoul 2014 (2014), Kyung Moon Sa: Kyung Moon Sa Seoul), 363-386 · Zbl 1373.05108
[41] Miclo, L., On eigenfunctions of Markov processes on trees, Probab. Theory Related Fields, 142, 3-4, 561-594 (2008) · Zbl 1149.60059
[42] Mohar, B., Isoperimetric numbers of graphs, J. Combin. Theory Ser. B, 47, 3, 274-291 (1989) · Zbl 0719.05042
[43] Ng, A.; Jordan, M.; Weiss, Y., On spectral clustering: analysis and an algorithm, (Dietterich, T.; Becker, S.; Ghahramani, Z., Advances in Neural Information Processing System, Vol. 14 (2001), MIT Press), 849-856
[44] Polyá, G.; Szegö, S., Isoperimetric inequalities in mathematical physics, Annals Math. Studies, 27 (1951) · Zbl 0044.38301
[45] Reff, N., New bounds for the Laplacian spectral radius of a signed graph (2011)
[46] Rojo, O., A nontrivial upper bound on the largest Laplacian eigenvalue of weighted graphs, Linear Algebra Appl., 420, 625-633 (2007) · Zbl 1110.05062
[47] Solé, P.; Zaslavsky, T., A coding approach to signed graphs, SIAM J. Discrete Math., 7, 4, 544-553 (1994) · Zbl 0811.05034
[48] Swamy, C., Correlation clustering: maximizing agreements via semidefinite programming, (Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2004), ACM: ACM New York), 526-527, (electronic) · Zbl 1318.68197
[49] Symeonidis, P.; Iakovidou, N.; Mantas, N.; Manolopoulos, Y., From biological to social networks: Link prediction based on multi-way spectral clustering, Data Knowl. Eng., 87, 226-242 (2013)
[50] Symeonidis, P.; Mantas, N., Spectral clustering for link prediction in social networks with positive and negative links, Soc. Netw. Anal. Min., 3, 1433-1447 (2013)
[51] Trevisan, L., Max cut and the smallest eigenvalue, (Proceedings of the 2009 ACM International Symposium on Theory of Computing. Proceedings of the 2009 ACM International Symposium on Theory of Computing, STOC’09 (2009), ACM: ACM New York). (Proceedings of the 2009 ACM International Symposium on Theory of Computing. Proceedings of the 2009 ACM International Symposium on Theory of Computing, STOC’09 (2009), ACM: ACM New York), SIAM J. Comput., 41, 6, 1769-1786-271 (2012) · Zbl 1271.68245
[52] Vannimenus, J.; Toulouse, G., Theory of the frustration effect: II. Ising spins on a square lattice, J. Phys. C: Solid State Phys., 10, L537 (1977)
[53] von Luxburg, U., A tutorial on spectral clustering, Statist. Comput., 17, 4, 395-416 (2007)
[54] Wu, L.; Ying, X.; Wu, X.; Lu, A.; Zhou, Z.-H., Examining spectral space of complex networks with positive and negative links, Int. J. Soc. Netw. Min., 1, 1, 91-111 (2012)
[55] Zaslavsky, T., Signed graphs, Discrete Appl. Math., 4, 1, 47-74 (1982) · Zbl 0476.05080
[56] Zaslavsky, T., Balance and clustering in signed graphs, (Slides from Lectures at the C.R. Rao Advanced Institute of Mathematics, Statistics and Computer Science (2010), Univ. of Hyderabad: Univ. of Hyderabad India)
[57] Zaslavsky, T., Matrices in the theory of signed simple graphs, (Advances in Discrete Mathematics and Applications: Mysore, 2008. Advances in Discrete Mathematics and Applications: Mysore, 2008, Ramanujan Math. Soc. Lect. Notes Ser., vol. 13 (2010), Ramanujan Math. Soc.: Ramanujan Math. Soc. Mysore), 207-229 · Zbl 1231.05120
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.