×

A review of two network curvature measures. (English) Zbl 1477.28002

Rassias, Themistocles M. (ed.) et al., Nonlinear analysis and global optimization. Cham: Springer. Springer Optim. Appl. 167, 51-69 (2021).
Authors’ abstract: The curvature of higher-dimensional geometric shapes and topological spaces is a natural and powerful generalization of its simpler counterpart in planes and other two-dimensional spaces. Curvature plays a fundamental role in physics, mathematics, and many other areas. However, graphs are discrete objects that do not necessarily have an associated natural geometric embedding. There are many ways in which curvature definitions of a continuous surface or other similar space can be adapted to graphs depending on what kind of local or global properties the measure is desired to reflect. In this chapter, we review two such measures, namely the Gromov-hyperbolic curvature measure and a geometric measure based on topological associations to higher-dimensional complexes.
For the entire collection see [Zbl 1470.49002].

MSC:

28A75 Length, area, volume, other geometric measure theory
49Q15 Geometric measure and integration theory, integral and normal currents in optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albert, R.; Barabási, A-L, Statistical mechanics of complex networks, Rev. Mod. Phys., 74, 1, 47-97 (2002) · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47
[2] R. Albert, B. DasGupta, A. Gitter, G. Gürsoy, R. Hegde, P. Pal, G.S. Sivanathan, E.D. Sontag, A new computationally efficient measure of topological redundancy of biological and social networks. Phys. Rev. E 84(3), 036117 (2011)
[3] R. Albert, B. DasGupta, N. Mobasheri, Topological implications of negative curvature for biological and social networks. Phys. Rev. E 89(3), 032811 (2014)
[4] Aminikhanghahi, S.; Cook, DJ, A survey of methods for time series change point detection, Knowl. Inf. Syst., 51, 2, 339-367 (2017) · doi:10.1007/s10115-016-0987-z
[5] F. Ariaei, M. Lou, E. Jonckeere, B. Krishnamachari, M. Zuniga, Curvature of sensor network: clustering coefficient. EURASIP J. Wirel. Commun. Netw. 213185 (2008)
[6] Bassett, DS; Wymbs, NF; Porter, MA; Mucha, PJ; Carlson, JM; Grafton, ST, Dynamic reconfiguration of human brain networks during learning, PNAS, 108, 18, 7641-7646 (2011) · doi:10.1073/pnas.1018985108
[7] Benjamini, I., Expanders are not hyperbolic, Isr. J. Math., 108, 33-36 (1998) · Zbl 0915.05072 · doi:10.1007/BF02783040
[8] Benjamini, I.; Schramm, O., Finite transitive graph embedding into a hyperbolic metric space must stretch or squeeze, in Geometric Aspects of Functional Analysis, 123-126 (2012), Berlin: Springer, Berlin · Zbl 1261.53076
[9] Benjamini, I.; Hoppen, C.; Ofek, E.; Pralat, P.; Wormald, N., Geodesics and almost geodesic cycles in random regular graphs, J. Graph Theory, 66, 115-136 (2011) · Zbl 1218.05074 · doi:10.1002/jgt.20496
[10] Berger, M., A Panoramic View of Riemannian Geometry (2012), Berlin: Springer, Berlin · Zbl 1038.53002
[11] E. Bloch, Combinatorial Ricci curvature for polyhedral surfaces and posets. arXiv:1406.4598v1 (2014)
[12] Bosc, M.; Heitz, F.; Armspach, JP; Namer, I.; Gounot, D.; Rumbach, L., Automatic change detection in multimodal serial MRI: application to multiple sclerosis lesion evolution, Neuroimage, 20, 2, 643-656 (2003) · doi:10.1016/S1053-8119(03)00406-3
[13] Bridson, MR; Haefliger, A., Metric Spaces of Non-positive Curvature (1999), Berlin: Springer, Berlin · Zbl 0988.53001 · doi:10.1007/978-3-662-12494-9
[14] J. Chalopin, V. Chepoi, F.F. Dragan, G. Ducoffe, A. Mohammed, Y. Vaxès, Fast approximation and exact computation of negative curvature parameters of graphs, in 34th International Symposium on Computational Geometry (2018) · Zbl 1489.68346
[15] Chowdhury, MFR; Selouani, SA; O’Shaughnessy, D., Bayesian on-line spectral change point detection: a soft computing approach for on-line ASR, Int. J. Speech Technol., 15, 1, 5-23 (2011) · doi:10.1007/s10772-011-9116-2
[16] Chepoi, V.; Estellon, B.; Charikar, M.; Jansen, K.; Reingold, O.; Rolim, JDP, Packing and covering δ-hyperbolic spaces by balls, Lecture Notes in Computer Science 4627, 59-73 (2007), Springer: Berlin, Springer · Zbl 1171.05315
[17] V. Chepoi, F.F. Dragan, B. Estellon, M. Habib, Y. Vaxès, Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs, in 24th Annual Symposium on Computational Geometry (2008), pp. 59-68 · Zbl 1221.68295
[18] Chepoi, V.; Dragan, FF; Estellon, B.; Habib, M.; Vaxès, Y.; Xiang, Y., Additive spanners and distance and routing labeling schemes for δ-hyperbolic graphs, Algorithmica, 62, 3-4, 713-732 (2012) · Zbl 1239.05048 · doi:10.1007/s00453-010-9478-x
[19] Cormen, TH; Leiserson, CE; Rivest, RL; Stein, C., Introduction to Algorithms (2001), Cambridge: MIT Press, Cambridge · Zbl 1047.68161
[20] DasGupta, B.; Desai, D., Complexity of Newman’s community finding approach for social networks, J. Comput. Syst. Sci., 79, 50-67 (2013) · Zbl 1258.05118 · doi:10.1016/j.jcss.2012.04.003
[21] DasGupta, B.; Karpinski, M.; Mobasheri, N.; Yahyanejad, F., Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications, Algorithmica, 80, 2, 772-800 (2018) · Zbl 1391.68049 · doi:10.1007/s00453-017-0291-7
[22] DasGupta, B.; Janardhanan, MV; Yahyanejad, F., How did the shape of your network change? (On detecting network anomalies via non-local curvatures), Algorithmica, 82, 7, 1741-1783 (2020) · Zbl 1441.68172 · doi:10.1007/s00453-019-00665-7
[23] F. de Montgolfier, M. Soto, L. Viennot, Treewidth and hyperbolicity of the internet, in 10th IEEE International Symposium on Networking Computing and Applications (2011), pp. 25-32
[24] R. Duan, S. Pettie, Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths, in 20th Annual ACM-SIAM Symposium on Discrete Algorithms (2009), pp. 384-391 · Zbl 1423.05167
[25] Ducre-Robitaille, JF; Vincent, LA; Boulet, G., Comparison of techniques for detection of discontinuities in temperature series, Int. J. Climatol., 23, 9, 1087-1101 (2003) · doi:10.1002/joc.924
[26] Forman, R., Bochner’s method for cell complexes and combinatorial Ricci curvature, Discret. Comput. Geom., 29, 3, 323-374 (2003) · Zbl 1040.53040 · doi:10.1007/s00454-002-0743-x
[27] Fournier, H.; Ismail, A.; Vigneron, A., Computing the Gromov hyperbolicity of a discrete metric space, Inf. Process. Lett., 115, 6-8, 576-579 (2015) · Zbl 1328.68301 · doi:10.1016/j.ipl.2015.02.002
[28] Gamelin, TW; Greene, RE, Introduction to Topology (1999), Mineola: Dover Publications, Mineola · Zbl 0935.54001
[29] Garey, MR; Johnson, DS, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), New York: W. H. Freeman, New York · Zbl 0411.68039
[30] Gavoille, C.; Ly, O.; Deng, X.; Du, D-Z, Distance labeling in hyperbolic graphs, Lecture Notes in Computer Science 3827, 1071-1079 (2005), Springer: Berlin, Springer · Zbl 1175.05050
[31] L. Giot, J.S. Bader, C. Brouwer, A. Chaudhuri, B. Kuang, Y. Li, Y.L. Hao, C.E. Ooi, B. Godwin, E. Vitols, G. Vijayadamodar, P. Pochart, H. Machineni, M. Welsh, Y. Kong, B. Zerhusen, R. Malcolm, Z. Varrone, A. Collis, M. Minto, S. Burgess, L. McDaniel, E. Stimpson, F. Spriggs, J. Williams, K. Neurath, N. Ioime, M. Agee, E. Voss, K. Furtak, R. Renzulli, N. Aanensen, S. Carrolla, E. Bickelhaupt, Y. Lazovatsky, A. DaSilva, J. Zhong, C.A. Stanyon, R.L. Finley, K.P. White, M. Braverman, T. Jarvie, S. Gold, M. Leach, J. Knight, R.A. Shimkets, M.P. McKenna, J. Chant, J.M. Rothberg, A protein interaction map of Drosophila melanogaster. Science 302(5651), 1727-1736 (2003)
[32] Girvan, M.; Newman, MEJ, Community structure in social and biological networks, PNAS, 99, 7821-7826 (2002) · Zbl 1032.91716 · doi:10.1073/pnas.122653799
[33] Gromov, M., Hyperbolic groups, Essays Group Theory, 8, 75-263 (1987) · Zbl 0634.20015 · doi:10.1007/978-1-4613-9586-7_3
[34] Henle, M., A Combinatorial Introduction to Topology (1994), Mineola: Dover Publications, Mineola · Zbl 0852.55002
[35] Jonckheere, EA; Lohsoonthorn, P., Geometry of network security, Am. Control Conf., 2, 976-981 (2004)
[36] Jonckheere, E.; Lohsoonthorn, P.; Bonahon, F., Scaled Gromov hyperbolic graphs, J. Graph Theory, 57, 2, 157-180 (2007) · Zbl 1160.05017 · doi:10.1002/jgt.20275
[37] Jonckheere, E.; Lohsoonthorn, P.; Ariaei, F., Scaled Gromov four-point condition for network graph curvature computation, Int. Math., 7, 3, 137-177 (2011) · Zbl 1451.05218
[38] Jonckheere, E.; Lou, M.; Bonahon, F.; Baryshnikov, Y., Euclidean versus hyperbolic congestion in idealized versus experimental networks, Int. Math., 7, 1, 1-27 (2011) · Zbl 1245.68033
[39] Kannan, R.; Tetali, P.; Vempala, S., Markov-chain algorithms for generating bipartite graphs and tournaments, Random Struct. Algorithm., 14, 293-308 (1999) · Zbl 0933.05145 · doi:10.1002/(SICI)1098-2418(199907)14:4<293::AID-RSA1>3.0.CO;2-G
[40] Y. Kawahara, M. Sugiyama, Sequential change-point detection based on direct density-ratio estimation, in SIAM International Conference on Data Mining (2009), pp. 389-400 · Zbl 07260318
[41] Kolb, B.; Whishaw, IQ, Fundamentals of Human Neuropsychology (1996), New York: Freeman, New York
[42] Latora, V.; Marchior, M., A measure of centrality based on network efficiency, New J. Phys., 9, 188 (2007) · doi:10.1088/1367-2630/9/6/188
[43] Leicht, EA; Newman, MEJ, Community structure in directed networks, Phys. Rev. Lett., 100, 118703 (2008) · doi:10.1103/PhysRevLett.100.118703
[44] S. Li, C.M. Armstrong, N. Bertin, H. Ge, S. Milstein, M. Boxem, P.-O. Vidalain, J.-D.J. Han, A. Chesneau, T. Hao, D.S. Goldberg, N. Li, M. Martinez, J.-F. Rual, P. Lamesch, L. Xu, M. Tewari, S.L. Wong, L.V. Zhang, G.F. Berriz, L. Jacotot, P. Vaglio, J. Reboul, T. Hirozane-Kishikawa, Q. Li, H.W. Gabel, A. Elewa, B. Baumgartner, D.J. Rose, H. Yu, S. Bosak, R. Sequerra, A. Fraser, S.E. Mango, W.M. Saxton, S. Strome, S. van den Heuvel, F. Piano, J. Vandenhaute, C. Sardet, M. Gerstein, L. Doucette-Stamm, K.C. Gunsalus, J.W. Harper, M.E. Cusick, F.P. Roth, D.E. Hill, M. Vidal, A map of the interactome network of the metazoan C. elegans. Science 303, 540-543 (2004)
[45] A. Malyshev, Expanders are order diameter non-hyperbolic. arXiv:1501.07904 (2015)
[46] Narayan, D.; Saniee, I., Large-scale curvature of networks, Phys. Rev. E, 84 (2011) · doi:10.1103/PhysRevE.84.066108
[47] Narayan, O.; Saniee, I.; Tucci, GH, Lack of hyperbolicity in asymptotic Erdös-Rényi sparse random graphs, Int. Math., 11, 3, 277-288 (2015) · Zbl 1465.05162
[48] Newman, MEJ, The structure and function of complex networks, SIAM Rev., 45, 167-256 (2003) · Zbl 1029.68010 · doi:10.1137/S003614450342480
[49] Newman, MEJ, Detecting community structure in networks, Eur. Phys. J. B, 38, 321-330 (2004) · doi:10.1140/epjb/e2004-00124-y
[50] Newman, MEJ, Networks: An Introduction (2010), Oxford: Oxford University Press, Oxford · Zbl 1195.94003 · doi:10.1093/acprof:oso/9780199206650.001.0001
[51] Newman, MEJ; Girvan, M., Finding and evaluating community structure in networks, Phys. Rev. E, 69 (2004) · doi:10.1103/PhysRevE.69.026113
[52] Newman, MEJ; Strogatz, SH; Watts, DJ, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E, 64, 2, 026118-026134 (2001) · doi:10.1103/PhysRevE.64.026118
[53] Y. Ollivier, A visual introduction to Riemannian curvatures and some discrete generalizations, in Analysis and Geometry of Metric Measure Spaces: Lecture Notes of the 50th Séminaire de Mathématiques Supérieures, vol. 56, ed. by G. Dafni, R. John McCann, A. Stancu (2011), pp. 197-219 · Zbl 1279.53013
[54] Papadimitriou, CH; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Upper Saddle River: Prentice-Hall Inc., Upper Saddle River · Zbl 0503.90060
[55] F. Papadopoulos, D. Krioukov, M. Boguna, A. Vahdat, Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. IEEE Conf. Comput. Commun. 1-9 (2010)
[56] Reeves, J.; Chen, J.; Wang, XL; Lund, R.; Lu, QQ, A review and comparison of changepoint detection techniques for climate data, J. Appl. Meteorol. Climatol., 46, 6, 900-915 (2007) · doi:10.1175/JAM2493.1
[57] Robertson, N.; Seymour, PD, Graph minors, I. excluding a forest. J. Combinatorial Theory Ser. B, 35, 1, 39-61 (1983) · Zbl 0521.05062 · doi:10.1016/0095-8956(83)90079-5
[58] Roe, J., Index theory, coarse geometry, and topology of manifolds, in Conference Board of the Mathematical Sciences Regional Conference, Series 90 (1996), Providence: American Mathematical Society, Providence · Zbl 0853.58003
[59] A. Samal, R.P. Sreejith, J. Gu, S. Liu, E. Saucan, J. Jost, Comparative analysis of two discretizations of Ricci curvature for complex networks. Sci. Rep. 8, Article number: 8650 (2018)
[60] Shen-Orr, SS; Milo, R.; Mangan, S.; Alon, U., Network motifs in the transcriptional regulation network of Escherichia coli, Nat. Gen., 31, 64-68 (2002) · doi:10.1038/ng881
[61] Tononi, G.; Sporns, O.; Edelman, GM, Measures of degeneracy and redundancy in biological networks, PNAS, 96, 3257-3262 (1999) · doi:10.1073/pnas.96.6.3257
[62] M. Weber, J. Jost, E. Saucan, Forman-Ricci flow for change detection in large dynamic data sets, in International Conference on Information and Computational Science (2016) · Zbl 1422.53054
[63] M. Weber, E. Saucan, J. Jost, Can one see the shape of a network? arXiv:1608.07838 (2016)
[64] V.V. Williams, Multiplying matrices faster than Coppersmith-Winograd, in 44th ACM Symposium on Theory of Computing (2012), pp. 887-898 · Zbl 1286.65056
[65] Yang, P.; Dumont, G.; Ansermino, JM, Adaptive change detection in heart rate trend monitoring in anesthetized children, IEEE Trans. Biomed. Eng., 53, 11, 2211-2219 (2006) · doi:10.1109/TBME.2006.877107
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.