SantoFortunato,GiuseppeMangioni,RonaldoMenezes, andVincenzoNicosia(Eds.) ComplexNetworks StudiesinComputationalIntelligence,Volume207 Editor-in-Chief Prof.JanuszKacprzyk SystemsResearchInstitute PolishAcademyofSciences ul.Newelska6 01-447Warsaw Poland E-mail:[email protected] Furthervolumesofthisseriescanbefoundonour Vol.196.ValentinaEmiliaBalas,Ja´nosFodorand homepage:springer.com AnnamáriaR.Va´rkonyi-Ko´czy(Eds.) SoftComputingBasedModeling Vol.185.AnthonyBrabazonandMichaelO’Neill(Eds.) inIntelligentSystems,2009 NaturalComputinginComputationalFinance,2009 ISBN978-3-642-00447-6 ISBN978-3-540-95973-1 Vol.197.MauroBirattari TuningMetaheuristics,2009 Vol.186.Chi-KeongGohandKayChenTan ISBN978-3-642-00482-7 EvolutionaryMulti-objectiveOptimizationinUncertain Environments,2009 Vol.198.Efre´nMezura-Montes(Ed.) ISBN978-3-540-95975-5 Constraint-HandlinginEvolutionaryOptimization,2009 ISBN978-3-642-00618-0 Vol.187.MitsuoGen,DavidGreen,OsamuKatai,BobMcKay, AkiraNamatame,RuhulA.SarkerandByoung-TakZhang Vol.199.KazumiNakamatsu,GloriaPhillips-Wren, (Eds.) LakhmiC.Jain,andRobertJ.Howlett(Eds.) IntelligentandEvolutionarySystems,2009 NewAdvancesinIntelligentDecisionTechnologies,2009 ISBN978-3-540-95977-9 ISBN978-3-642-00908-2 Vol.188.AgustínGutie´rrezandSantiagoMarco(Eds.) Vol.200.DimitriPlemenos,andGeorgiosMiaoulis BiologicallyInspiredSignalProcessingforChemicalSensing, VisualComplexityandIntelligentComputerGraphics 2009 TechniquesEnhancements,2009 ISBN978-3-642-00175-8 ISBN978-3-642-01258-7 Vol.189.SallyMcClean,PeterMillard,EliaEl-Darziand Vol.201.Aboul-EllaHassanien,AjithAbraham, ChrisNugent(Eds.) AthanasiosV.Vasilakos,andWitoldPedrycz(Eds.) IntelligentPatientManagement,2009 FoundationsofComputationalIntelligenceVolume1,2009 ISBN978-3-642-00178-9 ISBN978-3-642-01081-1 Vol.190.K.R.Venugopal,K.G.SrinivasaandL.M.Patnaik Vol.202.Aboul-EllaHassanien,AjithAbraham, SoftComputingforDataMiningApplications,2009 andFranciscoHerrera(Eds.) ISBN978-3-642-00192-5 FoundationsofComputationalIntelligenceVolume2,2009 ISBN978-3-642-01532-8 Vol.191.ZongWooGeem(Ed.) Vol.203.AjithAbraham,Aboul-EllaHassanien, Music-InspiredHarmonySearchAlgorithm,2009 PatrickSiarry,andAndriesEngelbrecht(Eds.) ISBN978-3-642-00184-0 FoundationsofComputationalIntelligenceVolume3,2009 Vol.192.AgusBudiyono,BambangRiyantoandEndra ISBN978-3-642-01084-2 Joelianto(Eds.) Vol.204.AjithAbraham,Aboul-EllaHassanien,and IntelligentUnmannedSystems:TheoryandApplications,2009 Andre´PoncedeLeonF.deCarvalho(Eds.) ISBN978-3-642-00263-2 FoundationsofComputationalIntelligenceVolume4,2009 Vol.193.RaymondChiong(Ed.) ISBN978-3-642-01087-3 Nature-InspiredAlgorithmsforOptimisation,2009 Vol.205.AjithAbraham,Aboul-EllaHassanien,and ISBN978-3-642-00266-3 VáclavSnášel(Eds.) FoundationsofComputationalIntelligenceVolume5,2009 Vol.194.IanDempsey,MichaelO’NeillandAnthony ISBN978-3-642-01535-9 Brabazon(Eds.) FoundationsinGrammaticalEvolutionforDynamic Vol.206.AjithAbraham,Aboul-EllaHassanien, Environments,2009 AndréPoncedeLeonF.deCarvalho,andVáclavSnášel(Eds.) ISBN978-3-642-00313-4 FoundationsofComputationalIntelligenceVolume6,2009 ISBN978-3-642-01090-3 Vol.195.VivekBannoreandLeszekSwierkowski Iterative-InterpolationSuper-ResolutionImage Vol.207.SantoFortunato,GiuseppeMangioni, Reconstruction: RonaldoMenezes,andVincenzoNicosia(Eds.) AComputationallyEfficientTechnique,2009 ComplexNetworks,2009 ISBN978-3-642-00384-4 ISBN978-3-642-01205-1 Santo Fortunato,Giuseppe Mangioni, Ronaldo Menezes,andVincenzo Nicosia (Eds.) Complex Networks Results of the 2009 InternationalWorkshop on Complex Networks (CompleNet 2009) C 123 SantoFortunato RonaldoMenezes ComplexNetworksLagrangeLaboratory FloridaInstituteofTechnology ISIFoundation DepartmentofComputerSciences VialeS.Severo65 150W.UniversityBlvd 10133Torino MelbourneFL32901 Italy USA E-mail:[email protected] E-mail:rmenezes@cs.fit.edu GiuseppeMangioni VincenzoNicosia DipartimentodiIngegneria LaboratoriosuiSistemiComplessi InformaticaedelleTelecomunicazioni ScuolaSuperiorediCatania Universita`degliStudidiCatania ViaS.Nullo5/i–95123Catania VialeAndreaDoria,6 Italy I95125Catania E-mail:[email protected] Italy E-mail:[email protected] ISBN 978-3-642-01205-1 e-ISBN978-3-642-01206-8 DOI 10.1007/978-3-642-01206-8 Studiesin Computational Intelligence ISSN1860949X Library of Congress Control Number:Applied for (cid:2)c 2009 Springer-VerlagBerlin Heidelberg Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpart of the material is concerned, specifically therights of translation, reprinting,reuse ofillustrations, recitation,broadcasting, reproductiononmicrofilmorinanyother way, and storage in data banks. Duplication of this publication or parts thereof is permittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution undertheGerman Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typeset&CoverDesign:ScientificPublishing ServicesPvt. Ltd., Chennai, India. Printed in acid-free paper 9 8 7 6 5 4 3 2 1 springer.com Editorial SantoFortunatoandRonaldoMenezes Complex Networks Complexityscienceisamajorscientificrevolutionofourtime.Asystemiscomplex if its macroscopic behavior cannot be simply reduced to the microscopic behav- ior of its constituents. Nonlinear dynamics and feedback effects are the dominant characters of the dynamics of complex systems. A major contribution of the last years is the discovery that many complex systems in biology, physics, social and computersciences,canbestudiedthroughtheirgraph(network)representation,in which the elementaryunits of a system become nodesand their interactionslinks connectingnodes[1,2,3,5,4,6].Examplesaresocialnetworksofacquaintances, protein-proteininteraction networks, food webs, the Internet and the World Wide Web.Networksrepresentingrealsystemsarecharacterizedbyasetofcommonfea- tures,whichmarkedlydifferfromfeaturesofsimplelatticesorrandomgraphs.This is why one refers to them as complex networks. The most striking feature is the factthatthedistributionofthenumberofneighborsofanode(degree)istypically broad, with a tail that often follows a power law [7]. This means that nodes with lowdegreecoexistwith nodeswithlargedegree,orhubs.Thepresenceofhubsis responsibleforanumberofremarkablefeaturesofcomplexnetworks,liketheirre- silience againstrandomattacks or failures[8], and the absence of percolationand epidemic thresholds [8, 9]. Another importantcharacteristic of complexnetworks concerns clustering, i.e. the probability that neighbors of a node are themselves neighbors[10].Realnetworksusuallydisplayhighvaluesforthisprobability,much higherthaninrandomgraphs,andthispropertyplaysanimportantroleinspreading SantoFortunato ISIFoundation,VialeS.Severo65,10133Torino,Italy. e-mail:[email protected] RonaldoMenezes Bio-InspiredComputingLab,DepartmentofComputerSciences,FloridaInstituteof Technology,Melbourne,Florida,USA. e-mail:[email protected] VI Editorial phenomena. Finally, complex networks are characterized by short geodesic paths betweennodes,i.e.itispossibletoreacheverynodefromanyothernodeinasmall numberofsteps,thatgrowsonlylogarithmicallywiththesizeofthesystem(small- world property) [10]. The small-world property holds as well for simple random graphs,butincomplexnetworksgeodesicpathsaremuchshorter,duetothepres- enceofthehubs,whicharefundamentalcommunicationstations. The main issues in the theoryof complexnetworksconcerntheirstructure and their dynamics. A lot of work has been devoted to describe the structure of com- plexnetworks.Localpropertieslike degree,clusteringcoefficient,nodecentrality, etc.havebeenstudied,alongwiththeirstatisticaldistributions.Moreover,complex networksdisplayinterestingstructuresatthemesoscopiclevel,consistingingroups ofnodeswithmanylinksbetweennodesofthesamegroupandcomparativelyfew betweennodesofdifferentgroups[11].Suchgroupsofnodesarecalledcommuni- ties,andrepresentanessentialaspectoftheorganizationofnetworks,whichallow toinfernontrivialrelationshipsbetweenthenodes. Asfarasthedynamicsisconcerned,onehastodistinguishthedynamicsofcom- plex networks, from the dynamics of processes taking place on them. Models of networkdynamicshavebeenproposedsincetheoriginsofcomplexnetworks.They aremostlymodelsofgrowth,inwhichnodesareiterativelyaddedtoasmallinitial core. The fat-tailed distributions of degree observed in real systems are produced by the tendency of nodesto set links with nodeswith large degree [12], although severalothermechanismshavebeenproposed.Studyingprocessestakingplaceon networks is essential to understand how networks function. Many traditionalpro- cesses,likepercolation,spinmodelsdynamics,synchronization,opiniondynamics, epidemic spreading, etc. have been thoroughly analyzed, highlighting the role of hubsasfundamentalactorsinsuchprocesses. Nowadaysnetworktheoryisratherdeveloped.Still,thereareseveralopenprob- lemsandtheresearchactivityinthisfieldremainsintense.Forinstance,theproblem of detecting communities in networks is still far from being solved and it is now probablythemostactiveresearchtopicinthearea.Similarly,alotofefforthasbeen putinthestudyofweightednetworks,whereoneisconfrontedwiththeissueofthe interplaybetweenthestrengthoftheinteractionsandthenetworktopology.Finally, arecentresearchdirectionfocusesontheissueofthecoevolutionofnetworksand dynamics,i.e.withtheissueoftheinterplaybetweentheevolutionofthenetwork andthatofdynamicalprocessestakingplaceonit,whenbothevolutionsoccuron comparativetimescales. This volume aims at increasingour knowledgeon network theoryand applica- tionsbydiscussingsomeveryrecentresultsinthefield.Theenclosedpaperscover many of the issues above mentioned, and were contributed by a widely interdis- ciplinarycommunityofscientists, includingphysicists, mathematicians,computer sciences,engineersandeconomists.Wedistinguishfivesubjectareasforthe18pa- pers of this volume: analysis of real networks (3 papers), community structure (4 papers), network modeling (3 papers), network dynamics (3 papers) and applica- tions(5papers). Editorial VII AnalysisofRealNetworks The paper by Fagiolo, Reyes and Schiavo deals with the InternationalTrade Net- work,i.e.thenetworkofimport-exportrelationshipsbetweencountries.Theauthors analyzedthemostimportantstatisticsofnetworkpropertiesinatimespanoftwenty yearsandfoundthatthenode-statisticdistributionsarestable,whereasthedistribu- tionofpositivelinkweightsisturningfromalognormaltoapowerlaw.Thepaper by Nunnari, Puglisi, Bonforte and Spata presents a study of a network built from theanalysisofplanetarycorrelationsbetweentheactivitiesofvolcanosoverthelast two thousandyears.Thenetworkdisplaysboththesmall-worldpropertyandhigh clustering coefficient. Last, the paper by Z˘ivkovic´,Mitrovic´ and Tadic´ focuses on thenetworkderivedfromcorrelationsinthetimeseriesofgeneexpressionsofyeast. Modulesofgenescanbeidentifiedbyanalyzingtheeigenvectorsoftheadjacency matrix,whichisobtainedfromthecorrelationmatrixthroughstandardfiltering. CommunityStructure ThepaperbyCristino,AndradeandCosta,likepaperbyFagioloetal.,dealswith thegeneinteractionsofyeast.Thegoalistoidentifythemodularstructureingene transcriptionnetworks.Communitiesarefoundwiththemodularityoptimizational- gorithmbyClausetetal.[13].Structurallysimilarcommunitiestendtosharefunc- tionalproperties.ThepaperbyGregoryproposesanewmethodtofindoverlapping communitiesinnetworks.Itconsistsoftwosteps:first,thenetworkistransformedin anewonewherenodessharedbetweenmodulesaresplit,i.e.representedinmultiple copies;second,atraditionalcommunitydetectionmethodisappliedtotheresulting network.ForthesecondphaseGregoryadoptedseveralalgorithms,basedonmod- ularityoptimizationandrandomwalks.Thetwo-stepstrategyyieldsmoreaccurate resultsthanspecializedmethodstofindoverlappingcommunities,liketheC-finder byPalla etal. [14]. In nextpaper,Fiumicello,Longheuand Mangioniintroducea fastimplementationofacommunitydetectionmethodrecentlyproposedbyLanci- chinettietal.[15],whichconsistsinthelocaloptimizationofafitnessfunctionwith the possibility to find overlapsbetween clusters. The gain in speed is obtained by portingtheoriginalalgorithmonagridenvironment.Inthelastpaperinthisgroup, Xiang,ChenandZhouintroducedanagglomerativecommunitydetectionmethod, basedonameasurequantifyingthestructuralsimilaritybetweengraphs.Theproce- dureismuchfasterthanthefastmethodofClausetetal.[13],basedongreedymod- ularityoptimization.Ahybridstrategy,combiningthenewmethodwiththemethod byClausetetal.yieldsbetterestimatesforthemaximummodularityofnetworks. NetworkModeling The first paper in this group, by Brandes, Lerner, Nagel and Nick, introduces a methodtoidentifystructuraltrendsinnetworkensembles.Theensemblesaremix- turesofplantedpartitionmodels,i.e.classesofgraphswithwelldefinedgroupsof nodes. The method relies on the relative comparison of the vectors whose com- ponents are the eigenvalues of the adjacency matrix of graph instances of the VIII Editorial ensembles. The paperby Gustedtproposesmodelsthatgenerategraphswith high clusteringcoefficient.Themodelsareageneralizationoftherecipesbehindthecon- structionofthe randomgraphsa´ la Erdo¨sandRe´nyi[16]andscale-freenetworks a´ laBaraba´si-Albert[12].ThepaperbyVillasBoas,RodriguesandCostasuggests a modelofhighwaynetworks,whichgeneralizesthe conceptof geographicalnet- works, in that new nodesare introducedbetween pairs of importantnodes, which simulatesthepresenceofsmallintermediatetownsbetweenimportantcenters.The modelis ableto describethe UShighwaynetworkbetterthantraditionalcomplex networksmodels. NetworkDynamics This group starts with the paper by Maletic´ and Rajkovic´ where they introduce a generalmodelforopiniondynamicsthatcombinestwootherpopulardynamics.At variancewithtraditionalmodels,herenewopinionsareformed.Thedynamicsruns on different types of scale-free networks, and the final opinion state strongly de- pendson whetherthe network has a modularstructure or not. The paper by Loya andLucasprovesanalyticallyresultsonthe stationarystate of a generalepidemic model,includingasspecialcasespopularmodelsliketheSIS(susceptible-infected- susceptible) model. The dynamics runs on networks with degree-degree correla- tions. The epidemic threshold is also rigorously defined. The paper authored by Melnik and Gleeson, presents an analytical approach to determine the thresholds and the sizes of the giant components for bond percolation on random networks withnon-zeroclustering.Thisstudysuggeststhat,foranetworkwithagivenlevel ofclustering,thepercolationthresholdmaybehigherorlowerthanthethresholdon a randomized(unclustered)network with the same degreedistribution, depending onthedegreedistribution. Applications The first paper of the application group, authored by Funabashi, Chavalarias and Cointet, studied the correlations between variables on network nodes beyond the classic dyadicinteractions.Theyuse informationgeometryto decomposecorrela- tionsintodifferentordersofstatistics. Highordercorrelationsareused toanalyze networksofwordoccurrencesderivedfrompoliticalweblogdata. Inthe paperby Hoche,HardcastleandFlach,theyintroduceamethodtoreducethecomputational complexityoftopicpredictioninco-authorshipgraphs.Themethodconsistsinre- ducingthenumberoflinksofthegraph,byusingthepublicationdatesofthepapers. Testsonrealdatasetsshowthatthemethodisabletorecoverthesamepredictions as for the full graph, even when a large fraction of links is removed, with a gain in computationalefficiencyof oneorderof magnitude.The groupfollowwith the paperbyAoyama,Saito,YamadaandUeda,whichpresentsagraph-basedapproach forafastsearchofthemostsimilarobjecttoagivenqueryobject.Theapproachis basedonthefactthatsmall-worldnetworksare“searchable”,inthatanynodecan reachanytargetnodeusingonlylocalinformation.Thesimilaritysearchisturned into a search problem on the similarity network of objects. The method performs Editorial IX wellwiththegainofalowexpectedsearchcost.ThepaperbyLawniczak,Wuand DiStefanodealswiththeproblemofnetworksecurity,byfocusingonthedetection of anomalous traffic packets in networks like the Internet. They use information entropyto monitorpacket traffic, and find that the entropyprofiles of packet traf- fic at selected nodes/routers may indeed give information on the traffic behavior over the whole network, and revealanomalies due to distributed denial-of-service attacks.Finally,inthepaperbyCollingsworthandMenezes,atemporalanalysisof the email network of Enron employees is performed,with the goal of identifying propertiesofthenetworkthatanticipatetheoccurrenceofsocialtensionsbetween people.In particular,theyfindthatan increasein the numberoftightlyconnected groupsseemstobeasignalofsocialtension. Acknowledgements. We would like to thank Springer for the publication of this volume.Wearealsoverygratefultoalltheauthorsofpaperscontainedinthevol- umeandto the membersof CompleNet2009ProgramCommittee,whose activity hasbeeninvaluabletoguaranteeacarefulscreeningofthesubmittedcontributions. References 1. Albert, R., Baraba´si, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys.74,47–97(2002) 2. Mendes, J.F.F.,Dorogovtsev, S.N.:EvolutionofNetworks: frombiological netstothe InternetandWWW.OxfordUniversityPress,Oxford(2003) 3. Newman,M.E.J.:Thestructureandfunctionofcomplexnetworks.SIAMRev.45,167– 256(2003) 4. Pastor-Satorras,R.,Vespignani,A.:EvolutionandstructureoftheInternet:astatistical physicsapproach.CambridgeUniversityPress,Cambridge(2004) 5. Boccaletti,S.,Latora,V.,Moreno, Y.,Chavez,M.,Hwang, D.-U.:Complexnetworks: Structureanddynamics.Phys.Rep.424,175–308(2006) 6. Barrat,A.,Barthe´lemy,M.,Vespignani,A.:DynamicalProcessesonComplexNetworks. CambridgeUniversityPress,Cambridge(2008) 7. Albert,R.,Jeong,H.,Baraba´si,A.-L.:ThediameteroftheWorldWideWeb.Nature401, 130–131(1999) 8. Cohen,R.,Erez,K.,benAvraham,D.,Havlin,S.:ResilienceoftheInternettoRandom Breakdown.Phys.Rev.Lett.85,4626–4628(2000) 9. Pastor-Satorras, R., Vespignani, A.: Epidemic spreading in scale-free networks. Phys. Rev.Lett.86,3200–3203(2001) 10. Watts,D.J.,Strogatz,S.H.:Collectivedynamicsof“small-world”networks.Nature393, 440–442(1998) 11. Girvan, M.,Newman, M.E.J.:Community structureinsocial andbiological networks. Proc.Natl.Acad.Sci.USA99,7821–7826(2002) 12. Baraba´si, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512(1999) 13. Clauset,A.,Newman,M.E.J.,Moore,C.:Phys.Rev.E70,066111(2004) 14. Palla,G.,Dere´nyi,I.,Farkas,I.,Vicsek,T.:Nature435,814–818(June9,2005) 15. Lancichinetti,A.,Fortunato,S.,Kerte´sz,J.:Detectingtheoverlappingandhierarchical communitystructureofcomplexnetworksEprintarXiv:0802.1218 16. Erdo¨s,P.,Re´nyi,A.:OnrandomgraphsI.Publ.Math.Debrecen6,290–297(1959) CompleNet Workshop on Complex Networks Welcome to Catania, Italy, for the first International Workshop on Complex Net- works(CompleNet2009).Thisworkshopserieswasaninitiativeofresearchgroups from: Dipartimento di Ingegneria Informatica e delle Telecomunicazioni(DIIT) - UniversityofCatania-Italy,theLaboratoriosuiSistemiComplessi–ScuolaSuperi- orediCatania,Italy,andtheBio-InspiredComputingLaboratoryintheDepartment ofComputerSciences,FloridaInstituteofTechnology,USA.CompleNet2009was hosted by the DIIT, EngineeringFaculty, University of Catania, Italy during May 26–27,2009. CompleNet aims at bringing together researchers and practitioners working on areas related to complex networks into an intensive 2 days high quality program. Despite the existence of other meetings, this is the first attemptto bring Complex NetworkresearchersintoaformatlongknownbytheComputerScienceandEngi- neeringcommunitiesbutrelativelyuncommonforthe Sciences(Physics,Biology, SocialSciences,etc.).ThemaindifferenceliesonthefactthatCompleNetrequires full papers to be submitted and not only abstracts. We believe this improves the qualityoftheworkshopandthisbookisproofofthis. Inthepasttwodecadeswehavebeenwitnessinganexponentialincreaseonthe numberofpublicationsinComplexNetworks.Frombiologicalsystemstocomputer science,fromeconomictosocialsystems, complexnetworksarebecomingperva- siveinmanyfieldsofscience.Itisthisinterdisciplinarynatureofcomplexnetworks thatthisworkshopaimsataddressingaswebelievethereisstillalongfruitfulway forustoexplore.Theexchangeofideasbetweentheareashelpsintheacceleration ofthisprocess. Wewouldliketothankfirstalltheauthorsandparticipantsoftheworkshop;they arethemainreasonthiseventwasasucess.Puttingaworkshoptogetherrequiresa lotofworkanddedicationparticularlywhenwewantedtomakesuretheresults(this book)would stand on its own. We are particularly gratefulto the ProgramChairs Santo FortunatoandRonaldo Menezesfortheir many contributionsand extensive worktowardsputtingtogetheraverysuccessfulprogram.Wewouldliketothankthe memberstheProgramCommitteefortheirdedicationandinvaluableexpertreviews, ensuringa high-qualitytechnicalprogram.We are also particularlygratefulto the