Abstract
We propose a method that allows to detect the subset of the sparse nodes in a complex network, providing supplementary informations about its structure and features. The aim is to produce a complementary approach to the classical ones dealing with dense communities, and in the end to develop mixed models of community classification which are articulated around the network’s sparse skeleton. We will present in this article different metrics that measure sparsity in a network, and introduce a method that uses these metrics to extract the sparse part from it, which we tested on a toy network and on data coming from the real world.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Albert, R., Barabási, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74(1), 47 (2002). https://doi.org/10.1103/RevModPhys.74.47
Barthélemy, M.: Spatial networks. Phys. Rep. 499(1–3), 1–101. http://linkinghub.elsevier.com/retrieve/pii/S037015731000308X (2011). https://doi.org/10.1016/j.physrep.2010.11.002
Burt, R.: Structural Holes: The Social Structure of Competition. Harvard University Press. https://books.google.fr/books?id=FAhiz9FWDzMC (2009)
Eades, P., Foulds, L., Giffin, J.: An efficient heuristic for identifying a maximum weight planar subgraph. In: Billington, E.J., Oates-Williams, S., Street, A.P. (eds.) Combinatorial Mathematics IX: Proceedings of the Ninth Australian Conference on Combinatorial Mathematics Held at the University of Queensland, Brisbane, Australia, August 24–28, 1981, pp. 239–251. Springer, Berlin Heidelberg (1982). https://doi.org/10.1007/BFb0061982
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174. http://linkinghub.elsevier.com/retrieve/pii/S0370157309002841 (2010). https://doi.org/10.1016/j.physrep.2009.11.002
Fruchterman, T.M., Reingold, E.M.: Graph drawing by force-directed placement. Softw. Pract. Exp. 21(11), 1129–1164 (1991). https://doi.org/10.1002/spe.4380211102
Le Couédic, M., Leturcq, S., Rodier, X., Hautefeuille, F., Fieux, E., Jouve, B.: Du cadastre ancien au graphe. Les dynamiques spatiales dans les sources fiscales médiévales et modernes. ArchéoSciences 36, 71–84. http://archeosciences.revues.org/3758 (2012). https://doi.org/10.4000/archeosciences.3758
Leskovec, J., Mcauley, J.J.: Learning to discover social circles in ego networks. Adv. Neural Inf. Process. Syst. 539–547. http://papers.nips.cc/paper/4532-learning-to-discover-social-circles-in-ego-networks (2012)
Martin, S., Brown, W.M., Klavans, R., Boyack, K.W.: OpenOrd: an open-source toolbox for large graph layout, p. 786806 (2011). https://doi.org/10.1117/12.871402
Miele, V., Matias, C.: Revealing the hidden structure of dynamic ecological networks. R. Soc. Open Sci. 4(6), 170251 (2017). https://doi.org/10.1098/rsos.170251
Newman, M.E.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. 103(23), 8577–8582. http://www.pnas.org/content/103/23/8577.short (2006)
Qiao, J., Huang, H.Q., Li, G.Y., Fan, Y.: Bridging the gap between different social networks. Phys. A Stat. Mech. Appl. 410, 535–549. http://linkinghub.elsevier.com/retrieve/pii/S0378437114004488 (2014). https://doi.org/10.1016/j.physa.2014.05.067
Ravasz, E., Barabási, A.L.: Hierarchical organization in complex networks. Phys. Rev. E 67(2) (2003). https://doi.org/10.1103/PhysRevE.67.026112
Souma, W., Fujiwara, Y., Aoyama, H.: Complex networks and economics. Phys. A Stat. Mech. Appl. 324(1–2), 396–401. http://linkinghub.elsevier.com/retrieve/pii/S0378437102018587 (2003). https://doi.org/10.1016/S0378-4371(02)01858-7
Vuillon, L., Lesieur, C.: From local to global changes in proteins: a network view. Curr. Opin. Struct. Biol. 31, 1–8. http://linkinghub.elsevier.com/retrieve/pii/S0959440X1500024X (2015). https://doi.org/10.1016/j.sbi.2015.02.015
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Djellabi, M., Jouve, B., Amblard, F. (2018). Behind the Communities, a Focus on the Sparse Part of a Network. In: Cherifi, C., Cherifi, H., Karsai, M., Musolesi, M. (eds) Complex Networks & Their Applications VI. COMPLEX NETWORKS 2017. Studies in Computational Intelligence, vol 689. Springer, Cham. https://doi.org/10.1007/978-3-319-72150-7_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-72150-7_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-72149-1
Online ISBN: 978-3-319-72150-7
eBook Packages: EngineeringEngineering (R0)