Springer Theses Recognizing Outstanding Ph.D. Research Forfurthervolumes: www.springer.com/series/8790 Aimsand Scope The series “Springer Theses” brings together a selection of the very best Ph.D. theses from around the world and across the physical sciences. Nominated and endorsed by two recognized specialists, each published volume has been selected for its scientific excellence and the high impact of its contents for the pertinent fieldofresearch.Forgreateraccessibilitytonon-specialists,thepublishedversions includeanextendedintroduction,aswellasaforewordbythestudent’ssupervisor explaining the special relevance of the work for the field. As a whole, the series will provide a valuable resource both for newcomers to the research fields described, and for other scientists seeking detailed background information on special questions. Finally, it provides an accredited documentation of the valuable contributionsmadebytoday’syoungergenerationofscientists. Theses are accepted into the series by invited nomination only andmust fulfillallofthefollowingcriteria • TheymustbewritteningoodEnglish. • ThetopicshouldfallwithintheconfinesofChemistry,Physics,EarthSciences, Engineering and related interdisciplinary fields such as Materials, Nanoscience, ChemicalEngineering,ComplexSystemsandBiophysics. • Theworkreportedinthethesismustrepresentasignificantscientificadvance. • Ifthethesisincludespreviouslypublishedmaterial,permissiontoreproducethis mustbegainedfromtherespectivecopyrightholder. • They must have been examined and passed during the 12 months prior to nomination. • Eachthesisshouldincludeaforewordbythesupervisoroutliningthesignificance ofitscontent. • The theses should have a clearly defined structure including an introduction accessibletoscientistsnotexpertinthatparticularfield. Hua-Wei Shen Community Structure of Complex Networks Author Supervisor Dr.Hua-WeiShen Prof.Xue-QiCheng InstituteofComputingTechnology InstituteofComputingTechnology ChineseAcademyofSciences ChineseAcademyofScience Beijing,China Beijing,China ISSN2190-5053 ISSN2190-5061(electronic) SpringerTheses ISBN978-3-642-31820-7 ISBN978-3-642-31821-4(eBook) DOI10.1007/978-3-642-31821-4 SpringerHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2012956465 ©Springer-VerlagBerlinHeidelberg2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’slocation,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer. PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violations areliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Whiletheadviceandinformationinthisbookarebelievedtobetrueandaccurateatthedateofpub- lication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityforany errorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,withrespect tothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) To my dearest wife Yü-Yü Cheng, and our lovelysonJun-HaoShen. Supervisor’s Foreword We are now surrounded by the ubiquitous complex networks, varying from the World Wide Web to the booming online social networks, from the power grid to thetransportationnetwork,fromthecommunicationnetworkstovariouseconomic networks,fromthenetworkswithincellororganismtothenetworkofecosystem. Thesenetworksarefromvariousdisciplines,constructedfordifferentpurposes,and seemtobeunrelatedtoeachother.However,thesenetworksexhibitastoundinggen- eralcharacteristics,includingthesmall-worldphenomenonandthepower-lawde- greedistribution.Itistherighttimetosaythat“thenetworktakeover”.Meanwhile, comprehensive research on complex networks requires the revolution of method- ology. The reductionism,as a paradigm, is expired. The graph theory, as a mathe- matical discipline, hits the limit. From the perspective of complexity and with the networkthinking,data-drivenmethodologyisdevelopingintoanewdiscipline,i.e., networkscience. Asasalientstructuralcharacteristicofcomplexnetworks,communitystructure indicatestheregularityoftopologicalstructureandreflectsthelocalityofrelation- shipsamongthecomponentsofnetworks.Communitystructureisfundamentalto manyfunctionalfeaturesofcomplexnetworks,suchastherobustnessandnaviga- bility.Moreover,communitystructureaffectsorevendeterminesthebehaviorofthe dynamicalprocessestakingplaceonnetworks,includingtheinformationdiffusion, thespreadofdiseaseandrumor,andsynchronization.Therefore,communitystruc- ture is crucial to understanding the relation between the structure and function of complexnetworksandhasimportanttheoreticalandpracticalimplicationstoutilize andcontrolthedynamicson,orof,thecomplexnetworks. This book focuses on the community structure of complex networks. In partic- ular,thisbookprovidesaclearreviewfortheresearchadvancesinthecommunity detection of networks, which is one of the hottest research topics in network sci- ence. In this book, the author studies four critical aspects of communitystructure. Thefouraspectsaretheoverlapsamongcommunities,themultiscaleofcommunity structure,therelationshipbetweencommunitystructureandnetworkdynamics,and thecoexistenceofmultipletypesofstructuralregularitiesbeyondcommunitystruc- ture. Aiming to investigate the community structure in real world networks, this vii viii Supervisor’sForeword book first highlights the limitation of modularity optimization, which is a classic methodforcommunitydetection.Theauthorfirstproposesthealgorithmtosimul- taneously detect the overlapping and hierarchical community structure. Then, the author proposes a dimensionality reduction framework for uncovering the multi- scale community structure in networks with heterogeneous networks. Further, the authorstudiesthediffusiondynamicsonnetworksandrevealstherelationshipbe- tweenthetabletransientsindiffusionprocessandtheintrinsiccommunitystructure innetworks.Finally,theauthorexploresthemultipletypesofstructuralregularities innetworksusingprobabilisticgraphicalmodel.Mostofthepreliminaryworksof thisbookhavebeenpublishedinprestigiousjournalsonnetworkscience,e.g.,the Physical Review E, and Journal of Statistical Mechanics. This book is also heav- ily based on Dr. Shen’s doctoral thesis, but with a substantial expansion based on hisfollow-upresearch.Dr.Shen’sthesiswascompletedinResearchCenterforRe- searchCenterforWebDataScienceandEngineering,InstituteofComputingTech- nology,ChineseAcademyofSciences.Thisthesiswashonoredwiththe“Top100 Excellent Doctoral Dissertations Award” from the Chinese Academy of Sciences andwasnominatedasthe“OutstandingDoctoralDissertation”bytheChineseCom- puterFederation.Ingeneral,thisbookbringstogethertherecentresearcheffortsof Dr.Sheninthefieldofcommunitystructureinnetworks. I believe both the researchers and practitioners in the field of social network analysisandthebroaderareaofnetworksciencecanbenefitfromreadingthisbook. Moreover, this book shows the research track of Dr. Shen from a Ph.D. student to aprofessor,whichmaybeofinterestparticularlytonewPh.D.students.Iwantto complimentDr.Shenforhavingwrittensuchanoutstandingbookforthenetwork sciencecommunity. InstituteofComputingTechnology,Beijing,China Xue-QiCheng Acknowledgements This book was partially supported by the National Natural Science Foundation of China (NSFC) under grant Nos. 61232010, 61202215, 60873245, 60872036, 60933005,60873217,and60803123,andtheNationalBasicResearchProgramof China (the 973 program) under grant Nos. 2004CB318109, 2007CB310805, and 2012CB316303,andtheNationalHigh-TechR&DProgramofChina(the863pro- gram)undergrantNos.2006AA01Z452and2010AA012502,andtheBeijingNat- uralScienceFoundationundergrantNo.4122077.Thisbookwasalsosupportedby KeyLabofInformationNetworkSecurity,MinistryofPublicSecurity. Theauthorwouldalsoliketothankthesupportsfromvariousresearchcenters, including: (1) Research Center of Web Data Science and Engineering, Institute of ComputingTechnology,ChineseAcademyofSciences;(2)KeyLabofInformation NetworkSecurity,MinistryofPublicSecurity. ix Parts of This Book Have Been Published in the Following Articles Shen, H.W., Cheng, X.Q., Cai, K., Hu, M.B.: Detect overlapping and hierarchical community structure in networks. Physica A 388(8), 1706–1712 (2009) (Repro- ducedwithPermission) Shen, H.W., Cheng, X.Q., Guo, J.F.: Quantifying and identifying the overlapping communitystructureinnetworks.J.Stat.Mech.P07042(2009)(Reproducedwith Permission) Shen,H.W.,Cheng,X.Q.,Fang,B.X.:Covariance,correlationmatrix,andthemul- tiscale communitystructure of networks. Phys. Rev. E 82, 016114 (2010) (Repro- ducedwithPermission) Shen,H.W.,Cheng,X.Q.:Spectralmethodsforthedetectionofnetworkcommunity structure: a comparative analysis. J. Stat. Mech. P10020 (2010) (Reproduced with Permission) Shen,H.W.,Cheng,X.Q.:Uncoveringthecommunitystructureassociatedwiththe diffusion dynamics on networks. J. Stat. Mech. P04024 (2010) (Reproduced with Permission) Shen, H.W., Cheng, X.Q., Guo, J.F.: Exploring the structural regularities in net- works.Phys.Rev.E84,056111(2011)(ReproducedwithPermission) Shen,H.W.,Cheng,X.Q.,Wang,Y.Z.,Chen,Y.:Adimensionalityreductionframe- work for detection of multiscale structure in heterogeneous networks. J. Comput. Sci.Technol.27,341–357(2012)(ReproducedwithPermission) xi Contents 1 CommunityStructure:AnIntroduction . . . . . . . . . . . . . . . . 1 1.1 NetworkScience:AnEmergingDiscipline . . . . . . . . . . . . . 1 1.2 Community Structure: An Salient Structural Characteristic ofNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 ABriefReviewforCommunityDetection . . . . . . . . . . . . . 3 1.3.1 WhatIsaCommunity? . . . . . . . . . . . . . . . . . . . 4 1.3.2 CommunityDetection . . . . . . . . . . . . . . . . . . . . 6 1.3.3 CommunityValidity . . . . . . . . . . . . . . . . . . . . . 11 1.4 ConcludingRemarks. . . . . . . . . . . . . . . . . . . . . . . . . 14 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 DetectingtheOverlappingandHierarchicalCommunityStructure inNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 EAGLE:DetectingtheOverlappingandHierarchicalCommunity Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.1 TheAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 ExtendingModularitytoQuantifytheOverlappingCommunity Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3.1 QuantifyingtheOverlappingCommunityStructure . . . . 30 2.3.2 IdentifyingtheOverlappingCommunityStructure . . . . . 32 2.3.3 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.4 ConclusionsandDiscussions . . . . . . . . . . . . . . . . . . . . 42 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3 MultiscaleCommunityDetectioninNetworkswithHeterogeneous DegreeDistributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2.1 PrincipalComponentAnalysis . . . . . . . . . . . . . . . 46 xiii