Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Robustness of Spatial Preferential Attachment Networks Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Hyperbolicity, Degeneracy, and Expansion of Random Intersection Graphs

Authors : Matthew Farrell, Timothy D. Goodrich, Nathan Lemons, Felix Reidl, Fernando Sánchez Villaamil, Blair D. Sullivan

Published in: Algorithms and Models for the Web Graph

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We establish the conditions under which several algorithmically exploitable structural features hold for random intersection graphs, a natural model for many real-world networks where edges correspond to shared attributes. Specifically, we fully characterize the degeneracy of random intersection graphs, and prove that the model asymptotically almost surely produces graphs with hyperbolicity at least \(\log {n}\). Further, we prove that when degenerate, the graphs generated by this model belong to a bounded-expansion graph class with high probability, a property particularly suitable for the design of linear time algorithms.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Local Clustering Coefficient in Generalized Preferential Attachment Models
next chapter Degree-Degree Distribution in a Power Law Random Intersection Graph with Clustering
Footnotes
1
Not related to the notion of expander graphs.
 
2
It should be noted that constant clustering and bounded expansion are not orthogonal [9].
 
Literature
1.
2.
Blackburn, S.R., Stinson, D.R., Upadhyay, J.: On the complexity of the herding attack and some related attacks on hash functions. Des. Codes Crypt. 64(1–2), 171–193 (2012)CrossRefMathSciNetMATH
3.
4.
Bloznelis, M., Jaworski, J., Kurauskas, V.: Assortativity and clustering of sparse random intersection graphs. Electron. J. Probab. 18, 1–24 (2013)CrossRefMathSciNet
5.
Bridson, M., Häfliger, A.: Metric Spaces of Non-Positive Curvature. Grundlehren Der Mathematischen Wissenschaften. Springer, Heidelberg (2009)
6.
Chen, W., Fang, W., Hu, G., Mahoney, M.W.: On the hyperbolicity of small-world and tree-like random graphs. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 278–288. Springer, Heidelberg (2012) CrossRef
7.
Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vaxès, Y.: Diameters, centers, and approximating trees of \(\delta \)-hyperbolic geodesic spaces and graphs. In: Symposium on Computational Geometry, pp. 59–68 (2008)
8.
Deijfen, M., Kets, W.: Random intersection graphs with tunable degree distribution and clustering. Probab. Eng. Informational Sci. 23, 661–674 (2009)CrossRefMathSciNetMATH
9.
Demaine, E.D., Reidl, F., Rossmanith, P., Sánchez Villaamil, F., Sikdar, S., Sullivan, B.D.: Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs. CoRR, abs/1406.2587 (2014)
10.
Dvořák, Z., Král’, D., Thomas, R.: Testing first-order properties for subclasses of sparse graphs. J. ACM 60(5), 36 (2013)MathSciNet
11.
Farrell, M., Goodrich, T., Lemons, N., Reidl, F., Sánchez Villaamil, F., Sullivan, B.D.: Hyperbolicity, degeneracy, and expansion of random intersection graphs. CoRR, abs/1409.8196 (2014)
12.
Godehardt, E., Jarowski, J., Rybarczyk, K.: Clustering coefficients of random intersection graphs. In: Gaul, W.A., Geyer-Schulz, A., Schmidt-Thieme, L., Kunze, J. (eds.) Challenges at the Interface Of Data Analysis Computer Science And Optimization, pp. 243–253. Springer, Heidelberg (2012)CrossRef
13.
Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.) Essays in Group Theory. Mathematical Sciences Research Institute Publications, vol. 8, pp. 75–263. Springer, New York (1987)CrossRef
14.
Jaworski, J., Karoński, M., Stark, D.: The degree of a typical vertex in generalized random intersection graph models. Discrete Math. 306, 2152–2165 (2006)CrossRefMathSciNetMATH
15.
16.
Karoński, M., Scheinerman, E.K., Singer-Cohen, K.B.: On random intersection graphs: the subgraph problem. Combin. Probab. Comput. 8, 131–159 (1999)CrossRefMathSciNetMATH
17.
Kleinberg, R.: Geographic routing using hyperbolic space. In: Proceedings of the 26th INFOCOM, pp. 1902–1909 (2007)
18.
Narayan, O., Saniee, I.: Large-scale curvature of networks. Phys. Rev. E 84, 066108 (2011)CrossRef
19.
Nešetřil, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. and II. Eur. J. Comb. 29(3), 760–791 (2008)CrossRefMATH
20.
Nešetřil, J., Ossona de Mendez, P.: First order properties on nowhere dense structures. J. Symbolic Logic 75(3), 868–887 (2010)CrossRefMathSciNetMATH
21.
Nešetřil, J., Ossona de Mendez, P.: On nowhere dense graphs. Eur. J. Comb. 32(4), 600–617 (2011)CrossRefMATH
22.
Nešetřil, J., Ossona de Mendez, P.: Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics, vol. 28. Springer, Heidelberg (2012)
23.
Nešetřil, J., Ossona de Mendez, P., Wood, D.R.: Characterisations and examples of graph classes with bounded expansion. Eur. J. Comb. 33(3), 350–373 (2012)CrossRefMATH
24.
Newman, M.E.J., Strogatz, S.H., Watts, D.J.: Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64(2), 026118 (2001)CrossRef
25.
Rybarczyk, K.: Diameter, connectivity, and phase transition of the uniform random intersection graph. Discrete Math. 311, 1998–2019 (2011)CrossRefMathSciNetMATH
26.
27.
Singer-Cohen, K.: Random intersection graphs. Ph.D. thesis, Department of Mathematical Sciences, The Johns Hopkins University (1995)
28.
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)CrossRef
29.
Zhao, J.: Minimum node degree and k-connectivity in wireless networks with unreliable links. In: 2014 IEEE International Symposium on Information Theory (ISIT), pp. 246–250. IEEE (2014)
30.
Zhao, J., Yagan, O., Gligor, V.: On \(k\)-connectivity and minimum vertex degree in random \(s\)-intersection graphs. In: ANALCO (2015)
31.
Zhao, J., Yagan, O., Gligor, V.: Connectivity in secure wireless sensor networks under transmission constraints. In: 2014 52nd Annual Allerton Conference on Communication, Control, and Computing, pp. 1294–1301. IEEE (2014)
32.
Zhao, J., Yagan, O., Gligor, V.: On the strengths of connectivity and robustness in general random intersection graphs. In: 2014 IEEE 53rd Annual Conference on Decision and Control (CDC), pp. 3661–3668. IEEE (2014)
Metadata
Title
Hyperbolicity, Degeneracy, and Expansion of Random Intersection Graphs
Authors
Matthew Farrell
Timothy D. Goodrich
Nathan Lemons
Felix Reidl
Fernando Sánchez Villaamil
Blair D. Sullivan
Copyright Year
2015
Book
Algorithms and Models for the Web Graph

Print ISBN: 978-3-319-26783-8

Electronic ISBN: 978-3-319-26784-5

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-26784-5_3

Premium Partner

    Image Credits