nach oben

Data Mining and Knowledge Discovery

Erschienen in:

01.09.2015

MassExodus: modeling evolving networks in harsh environments

verfasst von: Saket Navlakha, Christos Faloutsos, Ziv Bar-Joseph

Erschienen in: Data Mining and Knowledge Discovery | Ausgabe 5/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Consider networks in harsh environments, where nodes may be lost due to failure, attack, or infection—how is the topology affected by such events? Can we mimic and measure the effect? We propose a new generative model of network evolution in dynamic and harsh environments. Our model can reproduce the range of topologies observed across known robust and fragile biological networks, as well as several additional transport, communication, and social networks. We also develop a new optimization measure to evaluate robustness based on preserving high connectivity following random or adversarial bursty node loss. Using this measure, we evaluate the robustness of several real-world networks and propose a new distributed algorithm to construct secure networks operating within malicious environments.

Vorheriger Artikel Finding the longest common sub-pattern in sequences of temporal intervals

Nächster Artikel Beyond rankings: comparing directed acyclic graphs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Acemoglu D, Ozdaglar A, Tahbaz-Salehi A (2013) Systemic risk and stability in financial networks. NBER Working Papers 18727, National Bureau of Economic Research Inc. http://ideas.repec.org/p/nbr/nberwo/18727.html

Akoglu L, Faloutsos C (2009) Rtg: a recursive realistic graph generator using random typing. Data Min Knowl Discov 19(2):194–209. doi:10.1007/s10618-009-0140-7 MathSciNetCrossRef

Albert R (2007) Network inference, analysis, and modeling in systems biology. Plant Cell 19(11):3327–3338CrossRef

Albert R, Jeong H, Barabasi AL (2000) Error and attack tolerance of complex networks. Nature 406(6794):378–382CrossRef

Albert R, Albert I, Nakarado GL (2004) Structural vulnerability of the North American power grid. Phys Rev E Stat Nonlinear Soft Matter Phys 69(2 Pt 2):025,103CrossRef

Alippi C, Galperti C (2008) An adaptive system for optimal solar energy harvesting in wireless sensor network nodes. IEEE Trans Circuits Syst I 55(6):1742–1750. doi:10.1109/TCSI.2008.922023 MathSciNetCrossRef

Ashburner M, Ball CA, Blake JA, Botstein D, Butler H, Cherry JM, Davis AP, Dolinski K, Dwight SS, Eppig JT, Harris MA, Hill DP, Issel-Tarver L, Kasarskis A, Lewis S, Matese JC, Richardson JE, Ringwald M, Rubin GM, Sherlock G (2000) Gene ontology: tool for the unification of biology. The gene ontology consortium. Nat Genet 25(1):25–29CrossRef

Barabasi AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512MathSciNetCrossRef

Broder A, Kumar R, Maghoul F, Raghavan P, Rajagopalan S, Stata R, Tomkins A, Wiener J (2000) Graph structure in the web. In: Proceedings of the 9th international world wide web conference on computer networks: the international journal of computer and telecommunications netowrking, North-Holland Publishing Co., Amsterdam, The Netherlands, The Netherlands, pp 309–320. http://dl.acm.org/citation.cfm?id=347319.346290

Buldyrev SV, Parshani R, Paul G, Stanley HE, Havlin S (2010) Catastrophic cascade of failures in interdependent networks. Nature 464(7291):1025–1028CrossRef

Bullmore E, Sporns O (2012) The economy of brain network organization. Nat Rev Neurosci 13(5):336–349

Carle J, Simplot-Ryl D (2004) Energy-efficient area monitoring for sensor networks. Computer 37(2):40–46CrossRef

Chakrabarti D, Faloutsos C (2012) Graph mining: laws, tools, and case studies. Synthesis lectures on data mining and knowledge discovery. Morgan & Claypool Publishers, San Rafael, CA

Chan H, Akoglu L, Tong H (2014) Make it or break it: manipulating robustness in large netwotks. In: SIAM International conference on data mining (SDM)

Chatr-Aryamontri A, Breitkreutz BJ, Heinicke S, Boucher L, Winter A, Stark C, Nixon J, Ramage L, Kolas N, O’Donnell L, Reguly T, Breitkreutz A, Sellam A, Chen D, Chang C, Rust J, Livstone M, Oughtred R, Dolinski K, Tyers M (2013) The BioGRID interaction database: 2013 update. Nucleic Acids Res 41(Database issue):D816–D823

Cho A (2013) Computer science. Network science at center of surveillance dispute. Science 340(6138):1272CrossRef

Chung F, Lu L, Vu V (2003) Eigenvalues of random power law graphs. Ann Comb 7:21–33MathSciNetCrossRefMATH

De Domenico M, Sole-Ribalta A, Gomez S, Arenas A (2014) Navigability of interconnected networks under random failures. Proc Natl Acad Sci USA 111(23):8351–8356MathSciNetCrossRef

Easley D, Kleinberg J (2010) Networks, crowds, and markets: reasoning about a highly connected world. Cambridge University Press, New York, NYCrossRef

Fabrikant A, Luthra A, Maneva E, Papadimitriou CH, Shenker S (2003) On a network creation game. In: Proceedings of the twenty-second annual symposium on principles of distributed computing, ACM, New York, NY, PODC ’03, pp 347–351. doi:10.1145/872035.872088

Fredi Z, Komls J (1981) The eigenvalues of random symmetric matrices. Combinatorica 1(3):233–241. doi:10.1007/BF02579329 MathSciNetCrossRef

Gerdes SY, Scholle MD, Campbell JW, Balazsi G, Ravasz E, Daugherty MD, Somera AL, Kyrpides NC, Anderson I, Gelfand MS, Bhattacharya A, Kapatral V, D’Souza M, Baev MV, Grechkin Y, Mseeh F, Fonstein MY, Overbeek R, Barabasi AL, Oltvai ZN, Osterman AL (2003) Experimental determination and system level analysis of essential genes in Escherichia coli MG1655. J Bacteriol 185(19):5673–5684CrossRef

Giaever G, Chu AM, Ni L, Connelly C et al (2002) Functional profiling of the Saccharomyces cerevisiae genome. Nature 418(6896):387–391CrossRef

Gidalevitz T, Prahlad V, Morimoto RI (2011) The stress of protein misfolding: from single cells to multicellular organisms. Cold Spring Harb Perspect Biol. doi:10.1101/cshperspect.a009704

Gu Z, Steinmetz LM, Gu X, Scharfe C, Davis RW, Li WH (2003) Role of duplicate genes in genetic robustness against null mutations. Nature 421(6918):63–66CrossRef

Guell O, Sagues F, Serrano MA (2012) Predicting effects of structural stress in a genome-reduced model bacterial metabolism. Sci Rep 2:621CrossRef

Haldane AG, May RM (2011) Systemic risk in banking ecosystems. Nature 469(7330):351–355CrossRef

Helbing D (2013) Globally networked risks and how to respond. Nature 497(7447):51–59CrossRef

Ispolatov I, Yuryev A, Mazo I, Maslov S (2005) Binding properties and evolution of homodimers in protein–protein interaction networks. Nucleic Acids Res 33(11):3629–3635CrossRef

Jin EM, Girvan M, Newman MEJ (2001) Structure of growing social networks. Phys Rev E 64(046):132. doi:10.1103/PhysRevE.64.046132

Kitano H (2004) Biological robustness. Nat Rev Genet 5(11):826–837CrossRef

Kitano H, Oda K (2006) Robustness trade-offs and host-microbial symbiosis in the immune system. Mol Syst Biol 2(2006):0022

Kleinberg JM, Kumar R, Raghavan P, Rajagopalan S, Tomkins AS (1999) The web as a graph: measurements, models, and methods. In: Proceedings of the 5th annual international conference on computing and combinatorics, Springer, Berlin, COCOON’99, pp 1–17. http://dl.acm.org/citation.cfm?id=1765751.1765753

Krebs V (2002) Mapping networks of terrorist cells. CONNECTIONS 24(3):43–52

Leskovec J, Chakrabarti D, Kleinberg J, Faloutsos C (2005a) Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication. In: Proceedings of the 9th European conference on principles and practice of knowledge discovery in databases, Springer, Berlin, PKDD’05, pp 133–145. doi:10.1007/11564126_17

Leskovec J, Kleinberg J, Faloutsos C (2005b) Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the 11th international conference on knowledge discovery and data mining, pp 177–187. doi:10.1145/1081870.1081893

Leskovec J, Backstrom L, Kumar R, Tomkins A (2008) Microscopic evolution of social networks. In: Proceedings of the 14th international conference on knowledge discovery and data mining, pp 462–470. doi:10.1145/1401890.1401948

Louf R, Jensen P, Barthelemy M (2013) Emergence of hierarchy in cost-driven growth of spatial networks. Proc Natl Acad Sci USA 110(22):8824–8829MathSciNetCrossRefMATH

MacIsaac KD, Wang T, Gordon DB, Gifford DK, Stormo GD, Fraenkel E (2006) An improved map of conserved regulatory sites for Saccharomyces cerevisiae. BMC Bioinf 7:113CrossRef

Middendorf M, Ziv E, Wiggins CH (2005) Inferring network mechanisms: the Drosophila melanogaster protein interaction network. Proc Natl Acad Sci USA 102(9):3192–3197CrossRef

Moore D, Shannon C, Brown J (2002) Code-Red: a case study on the spread and victims of an Internet worm. SIGCOMM/USENIX Internet Measurement Workshop. Marseille, France, pp 273–284

Moore D, Shannon C, Voelker G, Savage S (2003) Internet quarantine: requirements for containing self-propagating code. In: Proc. of the IEEE Intl. Conf. on Computer and Communications, vol 3, pp 1901–1910 vol. 3, doi:10.1109/INFCOM.2003.1209212

Navlakha S, Kingsford C (2011) Network archaeology: uncovering ancient networks from present-day interactions. PLoS Comput Biol 7(4):e1001,119MathSciNetCrossRef

Navlakha S, He X, Faloutsos C, Bar-Joseph Z (2014) Topological properties of robust biological and computational networks. J R Soc Interface 11(96):20140,283CrossRef

Newman JR, Ghaemmaghami S, Ihmels J, Breslow DK, Noble M, DeRisi JL, Weissman JS (2006) Single-cell proteomic analysis of S. cerevisiae reveals the architecture of biological noise. Nature 441(7095):840–846CrossRef

Pereira-Leal JB, Levy ED, Kamp C, Teichmann SA (2007) Evolution of protein complexes by duplication of homomeric interactions. Genome Biol 8(4):R51CrossRef

Prakash B, Tong H, Valler N, Faloutsos M, Faloutsos C (2010) Virus propagation on time-varying networks: theory and immunization algorithms. In: Proceedings of the European conference on machine learning and knowledge discovery in databases, Springer, Berlin, pp 99–114. http://dl.acm.org/citation.cfm?id=1889788.1889796

Schneider CM, Moreira AA, Andrade JS, Havlin S, Herrmann HJ (2011) Mitigation of malicious attacks on networks. Proc Natl Acad Sci USA 108(10):3838–3841CrossRef

Siganos G, Tauro SL, Faloutsos M (2006) Jellyfish: a conceptual model for the as internet topology. J Commun Netw 8(3):339–350. doi:10.1109/JCN.2006.6182774 CrossRef

Sole RV, Rosas-Casals M, Corominas-Murtra B, Valverde S (2008) Robustness of the European power grids under intentional attack. Phys Rev E Stat Nonlinear Soft Matter Phys 77(2 Pt 2):026,102CrossRef

Valencia A, Pazos F (2003) Prediction of protein–protein interactions from evolutionary information. Methods Biochem Anal 44:411–426

Vazquez A, Flammini A, Maritan A, Vespignani A (2003) Modeling of protein interaction networks. Complexus 1(1):38–44CrossRef

Wu S, Das Sarma A, Fabrikant A, Lattanzi S, Tomkins A (2013) Arrival and departure dynamics in social networks. In: Proceedings of the sixth ACM international conference on web search and data mining, ACM, New York, NY, WSDM ’13, pp 233–242. doi:10.1145/2433396.2433425

Titel: MassExodus: modeling evolving networks in harsh environments
verfasst von: Saket Navlakha
Christos Faloutsos
Ziv Bar-Joseph
Publikationsdatum: 01.09.2015
Verlag: Springer US
Erschienen in: Data Mining and Knowledge Discovery / Ausgabe 5/2015
Print ISSN: 1384-5810
Elektronische ISSN: 1573-756X
DOI: https://doi.org/10.1007/s10618-014-0399-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 5/2015

Efficient and effective community search

Mining outlying aspects on numeric data

Generalization of clustering agreements and distances for overlapping clusters and network communities

Assessing the impact of a health intervention via user-generated Internet content

DRESS: dimensionality reduction for efficient sequence search

Beyond rankings: comparing directed acyclic graphs