Clustering and connectivity problems in complex networks.pdf

《Clustering and connectivity problems in complex networks.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

ThePennsylvaniaStateUniversityTheGraduateSchoolCLUSTERINGANDCONNECTIVITYPROBLEMSINCOMPLEXNETWORKSADissertationinIndustrialEngineeringandOperationsResearchbyUshanandiniRaghavan°c2008UshanandiniRaghavanSubmittedinPartialFul¯llmentoftheRequirementsfortheDegreeofDoctorofPhilosophyAugust2008 333611333361132008 ThedissertationofUshanandiniRaghavanwasreviewedandapproved¤bythefollowing:SoundarKumaraAllenE.Pearce/AllenM.PearceProfessorofIndustrialEngineeringThesisCo-Advisor,Co-ChairofCommitteeR¶ekaAlbertAssociateProfessorofPhysicsThesisCo-Advisor,Co-ChairofCommitteeDennisLinDistinguishedProfessorofStatisticsandSupplyChainManagementTaoYaoAssistantProfessorofIndustrialEngineeringArvindRangaswamyJonasH.AnchelProfessorofMarketingRichardKoubekPeter&AngelaDalPezzoProfessorofIndustrialEngineeringHeadoftheDepartmentofIndustrialEngineering¤Signaturesareon¯leintheGraduateSchool. AbstractNetworkedsystemspervadethisworld.Fromsocialrelationshipsbetweenpeopletochemicalinteractionsbetweenbio-moleculestowiredorwirelesscommunicationsbetweentechnologicaldevices,networksplayarole.Inrecentyearstherehasbeenawidespreadinterestinthestudyofthestructuralorganizationinsuchcomplexnetworks.Thefocushereisontheorganizationoflinks(whoisconnectedtowhom)inthenetworkanditse®ectsondynamicsandbehaviorofthenetworkedsystem.Traditionallycomplexnetworksweremodeledasrandomgraphsthatwerein-troducedbyPaulErd}osandAlfr¶edR¶enyi(E-Rrandomgraphs)[1].Herepairsofnodesinanetworkarelinkedwithauniformprobabilityp.Howeverinthere-centyearsempiricalobservationsfromawiderangeoflarge-scalenetworkssuchasthemovieactorcollaborationnetwork,scienti¯cco-authorshipnetworks,protein-proteininteractionmapsofcellsandorganisms,neuralnetworks,theWorldWideWeb(WWW)andothersrevealedpropertiesthatdeviatefromthepropertiesofE-Rrandomgraphs.Forexample,manyreal-worldnetworkshaveapower-lawde-greedistribution,highdegreeoflocalorder,assortativeordis-assortativemixingpatternsandtightlyinterlinkedgroupscalledclustersasopposedtoE-RrandomgraphsthathaveaPoissondegreedistribution,noparticularlocalorderormix-ingpatternsorclusteredstructures.Thisimpliesthatinmanysocial,biologicalandtechnologicalnetworkstheorganizationoflinks(whoisconnectedtowhom)followspeci¯cprinciples(whichisnotrandom)leadingtotheobservednetworkproperties.Alotofresearchhasbeendoneinrecentyearstounderstandvari-ousstructuralpropertiesofcomplexnetworksandinidentifyingtheorganizingprinciplesde¯ningthem.Inthisthesiswefocusontwoproblemsofstructuralorganizationinnetworks,namelyclusteringandconnectivity.Thepresenceofclustershasbeenobservedinmanyreal-worldnetworks(forexample,thepresenceofgroupsorcommunitiesinsocialnetworks,functionalmod-iii ulesinbiologicalnetworksandwebpagesonsimilartopicsintheWWW)Therehasbeenalotofe®ortrecentlyinde¯ning,identifyingandextractingtheseclus-tersfromcomplexnetworkstobetterunderstandtheirstructuralorganization.Toidentifyclusteredstructuresinnetworkswedevelopanalgorithmthatusesaconsensusformationmechanismtoextractdenselyinterlinkedgroups.Toourknowledgesuchamechanismhasnotbeenpreviouslyusedtoidentifyclustersinnetworksandtherebycontributingtoanotherwayofde¯ningthem.Oneofthemainadvantagesofthisalgorithmisitsabilitytoruninanear-lineartimeandhenceitsapplicabilitytoverylargenetworks.Alsounlikemostoftheexistingalgorithmswedonotrequireanyaprioriinformationsuchasthenumberandsizesoftheclusterspresentinthenetwork.Byapplyingthealgorithmonac-torcollaboration,scienti¯cco-authorship,protein-proteininteractionandWorldWideWebnetworkswehighlightthatthereexistsmultiplesigni¯cantclusteredstructuresrevealingtherichnessoftheorderspresentinthem.Further,thisresultsupportsthepresenceofoverlappingclustersinsocialandbiologicalnetworks[2].Aconnectednetworkisoneinwhichitispossibletotravelfromanynodetoanyothernodeviathelinks.Fortheconnectivityproblemweconsideraclassofnetworksthatinitiallycontainnolinks.Ourgoalistocreateandorganizelinksinthenetwork,whichislimitedbycertainconstraints,toobtainnetworkconnectivity.WesolvetheconnectivityprobleminthedomainofWirelessSensorNetworks(WSNs).Thatis,theconstraintsthatcurbthecreationoflinksaregivenbythephysicallimitsoftinywirelesssensordevices.InWSNsthenodesaresensordevicesandthelinksarethewirelesscommunicationsbetweenthesedevices.Theconstrainthereisthatthedegreeofanynode(numberofcommunicationsofanode)shouldbestrictlyboundedandcannotincreasewithanincreasingnetworksize(N).Unlikepreviousresultsthatinsistedthatthesmallestdegreerequired,toobtainconnectivity,isafunctionofNandincreaseswithN,weshowthatitispossibletoputaboundonthedegree.Inspeci¯c,weshowthatifwecantoleratecertainnodesbeingdisconnectedtheneverynodeisrequiredtocommunicateonlytoits¯veclosestneighbors(organizationprinciple)toobtainagiantconnectedcomponentinanetworkofanysizeN.iv TableofContentsListofFiguresviiiListofTablesxAcknowledgmentsxiChapter1Introduction11.1Networks.................................31.1.1Naturalnetworks........................31.1.2Engineerednetworks......................51.1.3Sizeandcomplexity.......................61.1.4Scienti¯candEngineeringinterests..............81.2Researchobjectivesandcontributions.................91.2.1Problem1:Findingclusteredstructuresinnaturalcomplexnetworks.............................91.2.1.1Approachandcontributions.............111.2.1.2Equivalenceofclustersandcommunities......131.2.2Problem2:ConnectivityofWirelesssensornetworks....131.2.2.1Approachandcontributions.............151.3Thesisorganization...........................16Chapter2Propertiesandmodelsofcomplexnetworks-Anoverview182.1Networks:De¯nition..........................192.2Propertiesofnaturalcomplexnetworks................202.2.1Averageshortestpathlength..................21v 2.2.1.1Connectedcomponents................222.2.2Localorder...........................232.2.3Degreedistribution.......................242.2.4Mixingpatterns.........................262.2.5Clusters.............................272.3Modelsofnaturalcomplexnetworks.................292.3.1Randomgraphs.........................292.3.1.1Transitionprobabilitiesandgiantconnectedcom-ponents........................302.3.1.2Non-uniformrandomgraphs.............332.3.2Small-worldnetworks......................342.3.3Evolutionarymodelsofscale-freenetworks..........352.4Dynamicalprocessesonnaturalnetworks...............362.4.1Networkresilience........................362.4.2Spreadingprocessanddi®usion................392.4.3Searchandinformationretrieval................402.5Clusteredstructures..........................412.6Wirelesssensornetworks........................412.6.1Powere±ciency,reducedinterferenceandconnectivity...432.6.2Spatialdistributionofsensornodes..............452.6.3Modelsofwirelesssensornetworks..............462.6.3.1PoissonBooleanmodel................462.6.3.2Poissonrandomconnectionmodel..........472.6.3.3Nearestk-neighborsmodel..............472.7Summary................................48Chapter3Findingclusteredstructuresinnaturalcomplexnetworks503.1De¯nitionsandpreviouswork.....................513.2Communitydetectionusinglabelpropagation............573.2.1Multipleclusteredstructures..................623.2.2Robustnessofthesolutions..................633.2.3Aggregate............................663.3Validationoftheclusterdetectionalgorithm.............683.4Timecomplexity............................693.5Summaryanddiscussion........................69Chapter4ConnectivityofWSNs734.1BackgroundontheconnectivityprobleminWSNs..........73vi 4.1.1Criticaltransmissionradius..................744.1.2Criticalnumberofneighbors..................744.1.3Giantcomponentsandconnectivity..............754.2Backgroundontopologycontrolprotocols..............774.3ConnectivityofWSNs.........................784.3.1Criticalnumberofneighbors..................794.3.2Simulationresults........................814.3.3Energyconsumptioninthenearestneighborsmodel.....814.3.4Stronglyconnectedcomponents................834.4Summaryanddiscussion........................83Chapter5Conclusionsandfuturework855.1ProblemI:Findingclusteredstructuresinnaturalnetworks.....865.1.1Resultsandcontributions...................865.1.2Futurework...........................875.1.2.1Networkmodeling..................875.1.2.2Opinionformationinnetworks...........885.1.2.3Clustersandusergroupsinonlinesocialnetworks.895.1.2.4Citationnetworksandimpactfactors........915.1.2.5ClustersinCallgraphs................925.2ProblemII:ConnectivityofWSNs..................955.2.1Resultsandcontributions...................955.2.2Futurework...........................965.2.2.1WSNarchitectureandclustering..........965.3Closingremarks.............................97Bibliography109vii ListofFigures1.1Networktopologies...........................71.2Clusteredstructureinafriendshipnetwork..............101.3Identifyingclustersandclusteredstructuresinagivennetwork...111.4Connectivityandnetworkconstruction................141.5ApictorialillustrationofWSNs....................152.1Typesofnetworks............................202.2EvolutionofE-Rrandomgraphs...................212.3DegreedistributioninE-Rrandomgraphs..............242.4Degreedistributioninnaturalnetworks................252.5GiantconnectedcomponentsinE-Rrandomgraphs.........322.6Small-worldnetworks..........................352.7Networkresiliencetorandomandtargetedattacks..........382.8Componentsofasensornode.....................422.9TopologycontrolinWSNs.......................443.1Anillustrationofadendrogram....................533.2Consensusformationindenselyconnectednetworks.........573.3Oscillationsinbi-partitegraphs....................583.4Clusteredstructuresinafriendshipnetwork.............603.5ClusteredstructuresinaUScollegefootballnetwork........613.6Similaritiesbetweenmultiplesolutions................643.7Robustnessoftheclusteredstructures.................653.8Aggregatinglabelsfromtwosolutions.................663.9Similaritiesbetweenaggregatesolutions................673.10Distributionofclustersizesinnaturalnetworks...........714.1GiantcomponentsinWSNs......................824.2GiantstronglyconnectedcomponentsinWSNs...........835.1RelationshipbetweenclustersandusergroupsintheYoutubesocialnetwork..................................91viii 5.2Sparselyinterconnectedstar-likeclusters...............935.3Star-likeclustersinGcall........................94ix ListofTables2.1Averagepathlengthsinnaturalnetworks...............222.2Localordercoe±cientsinnaturalnetworks..............232.3Mixingpatternsinnaturalnetworks..................262.4Modularityinnaturalnetworks....................28x AcknowledgmentsIamgreatlyindebtedtomanypeoplewhohavemademystayatPennStateanenrichingexperience.Ithankthesupportofmyco-advisorDr.SoundarKumarawhoseconstantencouragementandunderstandinghascarriedmethroughthegraduateschool.Ihavegreatlyadmiredtheideasthathebringstothetable,andatthesametimeIhaveenjoyedthefreedomheo®ershisstudentstopursuetheirownideas.Ialsothankthesupportofmyco-advisorDr.R¶ekaAlbert,whohasbeenanexemplaryresearcher.Herpatientanswerstomyignorantquestionsmademyresearche®ortscomfortable.IamalsogratefultothesupportofmycommitteemembersDr.DennisLin,Dr.ArvindRangaswamyandDr.TaoYaoandIhavegainedmuchfromtheirthoughtfulsuggestionsonmyresearchwork.Ialsogreatlyenjoyedandlearnedfrommywork/conversationswithDr.AmitNanavatiandDr.SougataMukherjeaofIBMIndiaResearchLabs.Thecommitment,integrityandcheerfulnessofstudentsinDr.Kumara'sLISQlabandinDr.Albert'sgroupatthePhysicsdepartmenthasalwaysleftmeinawe.Ifeelluckytohaveworkedbythesideofsuchwonderfulpeople,andthelessonslearntwillstickwithmeforlife.Yunho'sandSeogchan'scommitmenttowork,Hari'screativesolutionstoanyproblem(academicorotherwise),Nathan'sandSeokchan'senterprise,Changsoo'sandSeunKi'shardwork,thecommitmentanddisciplineshownbyClaire,Juilee,RanranandSongintheirresearch,abreathoffreshairandcommitmentfromthenewsetofstudents(Behedad,Rodrigo,Jie,JungWoon,Supreet,Prashanth,Keerati,Satama...)andthemanyfriendlychatswithAtishaandManinithatIenjoyedinthelabhaveallbeenagreatlearningexperience.IwouldliketothankShak,Anu,Malliga,PP,TolaniandHariformakingsurethattherewasneveradullmomentinmylifeatPennState.TheovernighttripstoNJ,themanytripstocinema5,premierandIP,playinghideandseekatBellefontinthenight,chain-cutatBryceJordonwiththefungultgang(Vissu,Sai,Potineni,...),animpromptuhikedownthevistapoint,campingatBaldEagle'spark,thedesi-at-homedancepartieswithAnu'staporisongcollections,Malliga'spassionxi fortennis(Ste±Grafinparticular),Shak'svigor,independenceandinabilitytounderstandthegameofcards,Tolani'stiramisuandHari'strustedfriendshiphavekeptmesaneandsafefarawayfrommyhomeinChennai,India.IamindebtedtomyfriendsVidhya,Padma,Daisy,Barghavie,SrilakshmiandSuganthifromthegoodolddaysofmystudentlifeatIIT-Madras.Iamextremelygratefultothemforopeninganeartomyproblemsandpatientlyencouragingmeevenintimesoftheirownstruggles.IhavedrawngreatstrengthsfromtheexemplarylivesofmyparentsT.S.RaghavanandPadmaRaghavan.Theirsimplicity,humilityandunwaveringdisciplinehasplayedabigpartinshapingmylifeatPennStateandforthisandmoreIamalwaysindebtedtothem.Iwouldalsoliketothankmylategrandmotherkuppu"patti,mybrotherSudarshan,mysister-in-lawKavithaandmylittlenieceNee-lashawhohaveshownloveanda®ectionandalwaysmanagedtokeepmeingoodspirits.Ialsogreatlyenjoyedtheenthusiasmandsupportshownbymyparents-in-lawMrs.&Mr.Parthasarathy.LastbutnottheleastIwouldliketothankmyhusbandVijaywhohasamongotherthingsstressedtheimportanceofwritingtheAcknowledgementsectiontothethesis.Thishasindeedbeenoneofthemostenjoyableandreminiscingpartofwritingthedissertation.Thankyou.xii Tomyparentsxiii Chapter1IntroductionWhateveryoudomayseeminsigni¯cant,butitismostimportantthatyoudoit."|MahatmaGandhiWhydoessomeinnovationcapturetheimaginationofasocietywhileothersdonot?Howdopeopleformopinionsandhowdoesconsensusemergeinanorgani-zation?Howtocapturetheopinionsandvotesofpeopleduringelectionyears?Whatarethefundamentalsofnatureandhowdocellsandorganismsevolveandsurvive?Whatmakesacell'sfunctionsrobustandadaptabletoitsenvironment?HowcanwemakeresourcesharingthroughtheInternetsecure?Inthisinfor-mationage,howdoweasusersquickly¯ndrelevantinformationfromtheWorldWideWeb?Howdoweguardtechnologicalinfrastructuresthatformthebackboneofourdaytodaybusiness,frommaliciousattacks?Howcanwesenseandpreventforest¯resatanearlystage?Howdoweputtousesensordevicestodetectforest¯res?Howcanweuseautonomoussensornodestomonitordangerousterrainsandlargechemicalplants?Theseareonlyafewquestionstheanswerstowhichwilla®ectthelivesofpeopleandthesocietyweliveinsigni¯cantly.Scienceandengineeringintheir 2overalle®orttoaddresstheseissueshavecreatedmanydi®erentavenuesofre-search;NetworkSciencebeingoneamongthem.Networkscienceisthestudyofsystemsmainlyusingtheirnetworkstructureortopology.Thenodes(vertices)andlinks(edges)ofsuchnetworksaretheentities(people,bio-molecules,web-pagesandsensordevices)andtheinteractions(friendships,chemicalreactions,hyperlinksandcommunicationsrespectively)betweenentitiesrespectively.Peoplehaveopinionsoftheirown,buttheyalsoshapeopinionsbyinteract-ingandexchangingviewswiththeirfriendsandneighbors.Sociologistshavelongunderstoodthatanindividual'sbehaviorissigni¯cantlya®ectedbytheirsocialin-teractions[3,4].Itisnowwidelybelievedthatbiologicalfunctionsofcellsandtherobustnessofcellularprocessesariseduetotheinteractionsthatexistbetweenthecomponentsofvariouscells[5].Webpageswithcontentsandinformationrelatetootherwebpagesbymeansofhyperlinkscreatingacomplexweblikestructure;theWWW.Miniaturizedwirelesssensornodes,whichindividuallyhavelimitedcapa-bilities,achieveanoverallsensingtaskbycommunicatingandsharinginformationwithothernodes[6,7].Avastamountofresearchinrecentyearshasshownthatorganizationoflinks(whoisconnectedtowhom)inanetworkandthetopologicalpropertiescarrysigni¯cantinformationaboutthebehaviorsofthesystemitrepresents[8,4].Fur-thermore,thetopologicalpropertieshaveahugeimpactontheperformancesofprocessessuchasinformationdi®usion,opinionformation,search,navigationandothers.Organizationoflinksinlarge-scalenaturalnetworkswasoriginallyconsideredtoberandom[8,4,1].Butempiricalobservationsintherecentpasthavere-vealedtopologicalpropertiesinawiderangeofsocial,biologicalandtechnologicalnetworksthatdeviatefromrandomness[9,8,4,10].Thatis,naturalnetworksthatappearinnatureandwhoseevolutionislargelyuncontrolled(self-organized)havespeci¯corganizingprinciplesleadingtovariouspropertiesorordersintheirtopology.Thisobservationhassparkedaninterestinthescienti¯cstudyofnet-worksandnetworkmodeling,includingthedesiretoengineerman-madesystemstomimicthebehaviorsofnature.Inthisthesiswecontributetothescienti¯candengineeringaspectsinthestudyofnetworks. 31.1NetworksAsexplainedabove,complexsystemsaremodeledasnetworkstounderstandandoptimizeprocessessuchasformationofopinions,resourcesharing,informationretrieval,robustnesstoperturbationsetc.Thefollowingaresomeoftheexamplesofsystemsandtheirnetworkrepresentations.1.1.1NaturalnetworksAnaturalnetworkisarepresentationofasystemthatispresentinnatureorhasevolvedoveraperiodoftimewithoutanycentralizedcontrol.Examplesinclude;1.Movieactorcollaborations:Thisnetworkconsistsofmovieactorsasnodesandedgesrepresenttheappearanceofpairsofactorsinthesamemovie.Itisagrowingnetworkthathadabout225,226nodesand13,738,786edgesin1998[11].Interestsinthisnetworkincludethestudyofsuccessfulcollaborations(whatkindofcastingmakesamoviesuccessful?)[12]andthefamousBaconnumberexperimenttostudyhowotheractorsarelinkedtoKevinBaconthroughtheircastingroles[13].2.Scienti¯cco-authorship:Inthisnetwork,thenodesarescientistsorre-searchersandanedgeexistsbetweenscientistsiftheyhavecollaboratedtogetherinwritingapaper.Newman[14,15,16]studiedscienti¯cco-authorshipnetworksfromfourdi®erentareasofresearch.Theinformationwasobtainedinanautomatedwayfromfourdi®erentdatabasesMEDLINE,PhysicsE-printarchive,SPIRESandNCSTRLthathasacollectionofallthepapersandtheirauthorsinareasofbiomed,physics,high-energyphysicsandcomputersciencerespectively.Oneofthesenetworks,formedfromtheMedlinedatabasefortheperiodfrom1961to2001,had1,520,251nodesand2,163,923edges.Developingmetricstoquantifythescienti¯cproductivityorcumulativeimpactofascientistgivenhis/hercollaborationsisoneproblemofinterestinco-authorshipnetworks[17,18].TheErd}osNumberproject,whichmotivatedtheBaconnumber,isapopularexperimentthatisusedinthestudyofoptimalco-authorshipstructuresofsuccessfulscientists[19]. 43.TheInternet:TheInternetisanetworkofcomputersanddevicesconnectedbywiredorwirelesslinks.ThestudyoftheInternetiscarriedoutattwodi®erentlevels,namely,attherouterlevelandatthelevelofautonomoussystems[8,20].Attherouterlevel,eachrouterisrepresentedasanodeandthephysicalconnectionsbetweenthemastheedgesinthenetwork.Intheautonomoussystemslevel,everydomain(InternetProviderSystem)isrepresentedasanodeandtheinter-domainconnectionsarerepresentedbytheedges.Thenumberofnodesattherouteranddomainlevelwere150,000in2000[20]and4000in1999[21]respectively.Theproblemofidentifyingandsharing¯lese±cientlyoverpeer-to-peernetworks(suchasGnutella[22])thatarebuiltovertheInternethasreceivedsigni¯cantattentioninrecentyears[23,24].4.WWW:TheWWWisanetworkofwebpageswherethehyperlinksbetweenthewebpagesarerepresentedbytheedgesinthenetwork.Itisagrowingnetworkthathadaboutonebillionnodesin1999[25]witharecentstudyestimatingthesizetobeabout11.5billioninJanuary2005[26].InformationretrievalfromWWWisaproblemofimmenseinterest.AlgorithmssuchasPageRank[27]ortheonesproposedbyKleinbergin[28],usethenetworkstructuretoextractwebpagesintheorderofrelevancetouserrequests.5.Neuralnetworks:Herethenodesareneuronsandanedgeconnectstwoneuronsifthereisachemicalorelectricalsynapsebetweenthem.WattsandStrogatz[8,11]studiedtopologicalpropertiesoftheneuralnetworkofnematodewormC.elegansconsistingof282neuronswithpairsofneuronsconnectedbythepresenceofeitherasynapseoragapjunction.Studyofneuralnetworksisimportantforunderstandinghowthebrainstoresandprocessesinformation[10].Whilewecanobservethatthisisdoneinanoptimalandrobustwayinneuralnetworkswearestillatlossinquantifyingthismechanism[10].6.Cellularnetworks:Herethesubstratesormoleculesthatconstituteacellarerepresentedasnodesandthepresenceofbio-chemicalinteractionsorregulatoryrelationshipsbetweenthemoleculesarerepresentedasedges[8].Amongothers,theinteractionsbetweenproteinmoleculesareimportantfor 5manybiologicalfunctions[29,5].Jeongetal.[5]havestudiedthetopologyofprotein-proteininteractionmapoftheyeastS.cerevisiathatconsistsof1870nodesasproteinsandconnectedby2240identi¯edinteractions.Usingthenetworkstructuretopredictpossible(previouslyunidenti¯ed)interac-tionsbetweenproteinmoleculeshasreceivedwidespreadattentionfromresearchers[30,31].1.1.2EngineerednetworksEngineerednetworksarethoseinwhichthenodesofthenetworkfollowapre-speci¯edsetofprotocolsbywhichthelinksareformed.Whetherthecontroliscentralizedorde-centralized,theorganizationisengineeredtoachievedesiredtopologicalproperties.Someexamplesfollow.1.Agent-basedsupplychainnetworks:Heresoftwareagentsthatareresponsibleforfunctionssuchassupplier,manufacturer,distributorandretailerarethenodesandthedirect°owofinformation/tasks/commoditiesbetweenentitiesarerepresentedbytheedgesinthenetwork.Thadakamallaetal[32]studiedthetopologicalpropertiesofamilitarysupply-chain(with10,000nodes[33])andproposedmechanismsbywhichthenodescanorganizeunderfunctionalconstraintstoproviderbetterperformances.2.WSNs:Herethenodesrepresentminiaturizedwirelesssensordevicesthatconsistofashort-rangedradiotranceiverandlimitedcomputationalcapa-bilities[7,6].Thoughindividualsensorshavelimitedcapacities,thetruevalueofthesystemisachievedbysharingresponsibilitiesandinformationthroughacommunicationinfrastructure[7].ThusanedgeinaWSNrepre-sentsthepresenceofacommunicationbetweentwonodes.ThenumberofnodesinaWSNcanvaryanywherebetweenafewhundredsorthousandstoevenmillionsdependingontheapplicationscenario.Thesensornodeswhendeployedinasensingregionwillself-organizetoestablishacommunicationtopology.Thereisconsiderableinterestindevelopingtopologycontrolpro-tocolsthatwillguidethisorganizationprocesstosupporttheglobalsensingtasks[6,34,35]. 61.1.3SizeandcomplexityAswecanseefromtheaboveexamples,thesizeofmanynetworksislarge-scale.Itisthusdi±culttocharacterizeanetworkbythestatesofindividualentities.Forexample,itiscumbersometorepresentaWWWasasetof11.5billionnodeswhere25nodeshave15hyperlinkseach,32nodeshave7hyperlinkseachandsoon.Insteadwerepresentthenetworkbyitsstatisticalproperties,thatis,theWWWisanetworkwith11.5billionnodesandadegree(numberoflinksoredgesincidentonanode)distributionP(k).P(k)istheprobabilitydistributionforadegreekonanygivennodeinthenetwork.Figure1.1showsexamplesoftwodi®erentnetworks,bothwith100nodesandapproximatelythesamenumberofedges,thatarecharacterizedbytwodi®erentdistributions,namelyPoisson(P(k)»e¡¸¸kwithparameter¸=2:5)andPower-law(P(k)»k¡°withparameter°=3).Aswecansee,aPoissonnetworklookstopologicallydi®erentfromapower-lawnetwork.InaPoissonnetworkalmostallnodeshaveadegreeclosetothemean(whichis2.5in¯gure1.1(a)),whileapower-lawnetworkontheotherhandischaracterizedbyafewnodeshavingaverylargedegreeandtherestofthenodesinthenetworkhavingarelativelysmalldegree.Similarlyonecancharacterizelarge-scalenetworksbymanyotherstatisticalpropertiessuchasaveragepathlengths(whichisanaverageoftheshortestpathsbetweenallpairsofnodes),averagenumberoftriangles(whichisanaverageofthenumberoftrianglestowhichagivennodebelongs)andothers[8,10].Inadditiontolargesizes,mostnaturalnetworksdisplayemergentpropertiesorsignsoforderatthemacroscopiclevelthatcannotbeobservedwhenthefocusisrestrictedtothepropertiesoftheindividualentities.Forexample,acommonlyobservedpropertyisthehighlyheterogeneousright-skeweddegreedistributionfoundinawiderangeofsocial,biologicalandtechnologicalnetworks.Thatis,thewayinwhichthesenetworksevolveorself-organize,onlyafewnodesgrabmostoftheedges(andhencehaveverylargedegrees)whilealargenumberofnodeshaveonlyafewedgesincidentonthem(asmalldegree).LetusconsidertheWWWforinstance.Whenanewwebpageiscreated,onaspeci¯ctopic,itismorelikelytohavehyper-referencestoalreadypopularwebpagesonthesametopic.Andsuchadisposition,collectivelyfromallwebpages,willenablealreadypopularwebpagestoreceivemoreandmorehyper-referencesleadingtohighlevelsofheterogeneity 7Figure1.1.(a)and(b)aretwodi®erentnetworkson100nodeseachandbothwithapproximatelythesamenumberofedges.Thenetworkin(a)ischaracterizedbyaPoissondegreedistribution(P(k)»e¡2:52:5k),whilethenetworkin(b)ischaracterizedbyapower-lawdegreedistribution(P(k)»k¡3)inthedegreedistribution.Inmostcasesthisheterogeneityinnodedegreeiswellcapturedbyapower-lawdistribution,P(k)»k¡°,withtheparameter°usuallybetween2and3inmanynaturalnetworks[8].Anotherfeaturecommonlyobservedatthemacroscopiclevelisshortaveragepathlengthsorsmall-worldness.Small-world,acommonoccurrenceinsocialnetworks,impliesthatdespitetheirlargesizes,onanaverageonlyafewstepsarerequiredtotravelfromanynodetoanyothernodeusingtheedgesinthenetwork.Themovieactorcollaborationnetworkwithasizeof212,250nodesstudiedbyAlbertandBarabasi[36]hasanaveragepathlengthof4.54andapower-lawexponent°=2:3.ThemapoftheInternet 8attherouterlevelstudiedbyGovindan[21]has150,000nodeswithanaveragepathlengthof11and°=2:4.ThemetabolicnetworkoftheyeastE.ColistudiedbyJeongetal.,[5]has778nodeswithanaveragepathlengthof3.2and°=2:2.Seechapter2foramorethoroughreviewofvariousemergentpropertiesinnaturalnetworks.Amongmanyreasons,duetothepresenceofemergentpropertiesandtheself-organizingnatureofnaturalnetworks,theyaretermedascomplexnetworksintheNetworkScienceliterature[8,37].1.1.4Scienti¯candEngineeringinterestsInterestinthestudyofnaturalcomplexnetworkscanbebroadlyclassi¯edintotwoclasses,namelyscienti¯candengineering.Thescienti¯cinterestliesinun-derstandingthestructure,evolution,andpropertiesofnetworks,withaneventualgoalofengineeringmoree±cientprocessesonthesenetworks.Theengineeringinterest,ontheotherhand,liesindevelopingmoree±cientalgorithmsand¯ndingoptimalparameterstobettercontroltheprocessestakingplaceonsuchnetworks[8,10,4].Withanincreasingunderstandingonthestructuralorganizationleadingtoemergentproperties,arichliteratureofcomplexnetworkmodelsthatcanmimicsuchpropertieshasdeveloped[8,10,4,11].Thesenetworkmodelsthenformthebasisonwhichprocessessuchasdiseasepropagation,informationdi®usion,search,navigationandothersarestudiedandanalyzed.Someoftheinterestingquestionsthatcanbeansweredusingacombinationofbothaspectsofthisresearchinclude1)howtocontrolthespreadofdiseasesinalargeclassofpeopleinterconnectedbyphysicalcontacts,2)howtostudy,maintain,andcontrolthedi®usionofinforma-tioninWWW,and3)howtobetteridentifytargetsfordrugdiscoveryinmetabolicnetworks?Inparallelthereisalsoconsiderableinterestinengineeringnetworkssuchassupplychainsandminiaturizedwirelesssensors,where,bycontrollingtheinteractionsbetweenentitiesdesiredbehaviorsareachieved[32,6,38,39]. 91.2ResearchobjectivesandcontributionsInthisthesiswecontributetoboththeabovediscussedaspectsofinterestinthestudyofcomplexnetworks.Wesolvetwodi®erentproblems,wherein1)theobjectiveistodetectandidentifyclustersinnaturalcomplexnetworks,therebyaidingthescienti¯cstudyoftheorganizingprinciplesinnaturalnetworksandin2)theobjectiveistoengineertheconnectivityofaWSNbycontrollingthecommunicationsatindividualsensornodes.Researchintherecentpastfocusedonunderstandingtheevolutionandorgani-zationofnaturalnetworksandthee®ectofnetworktopologyonthedynamicsandbehaviorsofthesystem[8,4,10].Findingclusteredstructuresinnetworksisan-othersteptowardsunderstandingthecomplexsystemstheyrepresent.Clusteredstructuresariseinnaturalnetworksbecauseofthewaylinksareorganized.Inspe-ci¯c,itiscommonto¯ndgroupsofnodesbeingdenselyinterconnectedwithinthegroupandsparselyinterconnectedtootherpartsinthenetwork(see¯gure1.2).Inthisthesiswedevelopaformalmechanismbywhichonecanextractclustersfromcomplexnetworksinane±cientmanner.Wefurtheranalyzeandhighlightsomeoftheinterestingfeaturesoftheclusteredstructuresobtainedfromawiderangeoftestnetworks.Connectivity,thoughnotasurprisingemergentpropertyinnaturalnetworks,isneverthelessanimportantone.Inalmostallnaturalnetworksalargefractionofnodesformwhatistermedasthegiantconnectedcomponentorsimplygiantcomponent[8,1].Thatis,mostpairsofnodes(ifnotall)inthenetworkarecon-nectedeitherdirectlybyanedgeorthroughintermediarynodesformingchainsofedges.Hence,allauthors,whenconstructingnetworkmodelstorepresentnaturalnetworksgivecarefulconsiderationstoensurethepresenceofagiantcomponent[8,10].Usingthescienti¯cstudyandanalysisofnodeinteractionsleadingtogiantcomponentsinnetworks,weengineertheconnectivityofWSNs.1.2.1Problem1:FindingclusteredstructuresinnaturalcomplexnetworksAclusterinanetworkisagroupofsimilarnodesthatisdissimilarfromtherestofthenetwork.Itisusuallythoughtofasagroupwithinwhichthenodesare 10Figure1.2.Clusters(identi¯edbynodeswiththesamecolor)presentinafriendshipnetworkofmembersinaKarateclub.Herealinkconnectingtwonodesrepresentsfriendshipbetweenthetwomembers.Whentheclubsplitintotwofactionsduetoleadershipissues,eachmember(nodes)joinedoneofthetwofactions.Clustersinthisnetworkhighlightsthesetwofactions.denselyinter-connectedandsparselyconnectedtootherpartsofthenetwork(see¯gure1.3)[40,4,3].Thereisnouniversallyacceptedde¯nitionforacluster,butitiswellknownthatmostnaturalnetworksdisplayclusteredstructures(see¯gure1.2).Clusterdetectioninnaturalnetworkshasdiverseapplications.AclusterintheWWWnetworkindicatesasimilarityamongnodesinthegroup.Hence,ifweknowthecharacteristicsofthecontentsinasmallnumberofwebpages,thenitcanbeextrapolatedtootherwebpagesinthesamecluster.Clustersinsocialnetworkscanprovideinsightsaboutcommoncharacteristicsorbeliefsamongpeoplewithinacommunitythatmakesthemdi®erentfromotherclusters(orcommunities).Inbio-molecularinteractionnetworks,segregatingnodesintofunctionalmodulescanhelpidentifytherolesorfunctionsofindividualmolecules[41].Further,inmanylarge-scalenaturalnetworks,clusterscanhavedistinctpropertieswhicharelostintheircombinedanalysis[8]. 11Figure1.3.Anillustrationofclustersandclusteredstructuresinagivennetwork.Thegoalofaclusterdetectionalgorithmis,givenanetwork,topartitionthenodesintodenselyinterlinkedgroupscalledclusters.Suchapartitioniscalledtheclusteredstructureofthegivennetwork.1.2.1.1ApproachandcontributionsTherehasbeenconsiderablee®ortrecentlyinde¯ning,detectingandidentifyingclustersinnaturalnetworks[42,43,44,40,41,45,46,28,47,2,48].Aclusterdetectionalgorithmisexpectedtodothefollowing(see¯gure1.3):²Given:AnetworkG(N;M)onNnodesandMedges.²Output:1.Thenumberofclusters(c)presentinthenetwork2.Apartitioningofnodesintocclusters.Inthisthesisweinvestigateasimplelabelpropagationalgorithmthatusesthenetworkstructurealoneasitsguideandrequiresneitheroptimizationofapre-de¯nedobjectivefunctionnorpriorinformationabouttheclusters.Inouralgorithmeverynodeisinitializedwithauniquelabelandateverystepeachnodeadoptsthelabelthatmostofitsneighborscurrentlyhave.Inthisiterativeprocess 12denselyconnectedgroupsofnodesformaconsensusonauniquelabeltoformclusters.Uniquenessandcontributionsofthisclusterdetectionmethodareasfollows,1.Weproposeanovelwayofde¯ningandidentifyingclustersinnetworks.Inparticularweidentifyconsensusgroupsinagivennetworkastheclustersofthenetworkandtheclusteredstructureasthepartitionofnodesintoconsensusgroups.Toourknowledgesuchaconsensusformationmechanismhasnotbeenpreviouslyusedforclusteridenti¯cationandanalysis.2.Wevalidatethealgorithmbyapplyingittonetworkswhoseclusteredstruc-turesareknown.3.Wefurthershowthatthealgorithmidenti¯es,notjustone,butmultiplesigni¯cantclusteredstructuresinvarioussocial,biologicalandtechnologicalnetworks.Thisisunlikemostoftheexistingalgorithmsthat¯ndonlythesinglebestsolution(clusteredstructure)ofagivennetwork.4.Weshowthatallthemultipleclusteredstructuresidenti¯edbytheproposedalgorithmaresigni¯cantlymodularandrobusttoperturbations.Thisimpliesthatthesolutionsarenotanartifactofthealgorithmbutre°ectthetruenatureoftheclusteredstructurespresentinthenetworks,supportingtheexistenceofoverlappingclusters[2].5.Alsounlikemostoftheexistingalgorithmsourproposedalgorithmdoesnotrequireapriorinformationregardingthenumberandsizesoftheclus-terspresentinthenetwork.Inparticularwewillshowthattheclustersizedistributionsinsocial,biologicalandtechnologicalnetworksarehighlyhet-erogeneousandhaveapower-lawlikebehavior.Thispower-lawdistributionofclustersizesisingoodagreementwithpreviousresults[49,50].6.Wedemonstratethatourlabelpropagationalgorithmtakesanearlineartimeandhenceitiscomputationallylessexpensivethanmostofthealgo-rithmsdesignedtodate.Inspeci¯c,weusethisalgorithmto¯ndclusteredstructuresinverylargesocialnetworkssuchasthemovieactorcollaboration 13network(with374,511nodesand15,014,850edges)andanonlinesocialnet-workYoutube(with1,157,827nodesand2,990,443edges).Toourknowledgenootherclusterdetectionmethodhasbeensuccessfullyappliedonsuchlargenetworks.1.2.1.2EquivalenceofclustersandcommunitiesAclusterinanetwork,asde¯nedinthisthesis,istermedasacommunityintheNetworkScienceliterature.Thatis,thede¯nitionofaclusterandacommunityisoneandthesame.Thetermcommunityisusedtoavoidconfusionwithanothertermclusteringcoe±cientthatiscommonlyusedinthisareaofresearch[47].Theclusteringcoe±cientisameasureofcliquishnessde¯nedatanode[51].Supposeagivennodexisconnectedtokothernodesinthenetwork.Then,therecanexistk(k¡1)atmost(=K)possibleedgesbetweenallpairsofx'sneighbors.Andamong2thesesupposethatonlyEpairsofedgesexistinthenetwork.Then,theclusteringcoe±cientatnodexistheratioE.Thustheclusteringcoe±cientisameasureKofhowdenselytheneighborsofxareconnected.Acommunityontheotherhandrepresentsadenselyconnectedgroupofnodesthatcanbeofvaryingsizesandnotfocusedatthelocalneighborhoodofanindividualnode(see¯gure1.2).Inthisthesis,wewillusethetermclustertostandforadenselyconnectedgroupofnodesinagivennetworkthatcanbeofvaryingsize.Itisinthismannerthatthetermclusteriscommonlyandwidelyusedinthe¯eldofIndustrialEngineeringandOperationsResearch.Thetermclusteringcoe±cientasde¯nedinthepreviousparagraphwillbecalledaslocalordercoe±cientandsparinglyusedinthisthesis.1.2.2Problem2:ConnectivityofWirelesssensornetworksConnectivityandnetworkconstructionareimportantproblemsincomplexnet-worksandWSNsinparticular.Firstlyconnectivityisoneoftheparametersusedindeterminingtheperformanceofanetworktonavigationandinformationdi®u-sionamongothers.In¯gure1.4(a)wecanseethatitispossibletonavigatefromanynodetoanyothernodeusingtheedgesofthenetworkunlike¯gure1.4(b)and¯gure1.4(c).Thereforeinformationdi®usestotheentirenetworkin¯gure1.4(a)unlike¯gure1.4(b)and¯gure1.4(c). 14Figure1.4.Examplesofnetworkswithdi®erentconnectivitypropertiesandrobustness.Thenetworkin(a)isconnectedandhenceaMsgoriginatingatanynodecanreachanyothernodeinthenetwork.Whereasin(b)and(c)aMsgcanonlydi®usetoapartofthenetworkindicatedbydashedcircles.Removalofnodexinthenetworkin(b)leadstotheremovalofalledgesincidentonx.Asaresultthenetworkbreaksdownintomanydisconnectedcomponents.Howeverforthenetworkin(c)failureofanynodewillstillmaintaintheconnectivityintherestofthenetwork.Secondly,whennodexfails,thenetworkstructurein¯gure1.4(b)breaksdownintomanydisconnectedcomponentsandlosesitsconnectivityproperty.Whereasin¯gure1.4(c)thefailureofanynodewillcontinuetomaintaintheconnectivityintherestofthenetwork.Similarlyweveryoftencomeacrossproblemswhereweneedtodeterminewhichnetworkstructuresarerobustandwhicharevulnerabletofailures[8,32].Whichtopologyisbetter?WhichnetworkisbestsuitedforWSNoperationsandcommunications?[6].Toengineersuchoptimalnetworktopologies,networkconstructionhasemergedasanimportanttool.WewillsolvetheproblemofengineeringnetworkconnectivityinthedomainofWSNs.Connectivityisoneofthemostbasicandstandardrequirementsforacommunicationtopology.AconnectedWSNconsistsofcommunicationpathsconnectinganypairofnodesinthenetwork,eitherdirectlyorinmultiplehops.Thesensornodesarespatiallydistributedandagivensensorcancommunicate(havelinks)tonodesthatarewithinitscommunicationrange(see¯gure1.5).While 15Figure1.5.Apictorialrepresentationofspatiallydistributedsensornodesandtheircommunicationlinks.Eachnodecancontrolitscommunicationradiusorrangeandhencehaslinkstoonlythosenodeswiththerange.connectivityistheobjective,thedesignofsensornodesposeconstraintsthatcurbthecreationofcommunicationlinks[6].Twosuchconstraintsarelimitedpowerandreducedinterference.Theseconstraintsnecessitatethatthenumberofcommunicationlinks(orde-gree)ateachnodetobeminimal[38,6].1.2.2.1ApproachandcontributionsGivenasetofNsensornodes,weposetheconnectivityproblemasfollows:²Objective:minfmaxidig²subjectto:Networkconnectivitywherediisthedegreeonnodei.Inthisthesisweassumethesensornodesareuniformlyrandomlydistributedinatwodimensionalunitsquareandeverynodecanadjustitstransmissionrange(CISCOIEEE802.11a/b/gwirelesscardscanvarytheirtransmitpowerbetween1mWto100mW)toaccommodateonlytherequireddegree(see¯gure1.5).Weshowthatifwecantoleratesomenodesbeingdisconnected,itispossibletogetverye±cientboundsonthedegreesofthenodes. 16Thatis,everynodeisrequiredtocommunicatewithjust¯veclosestsensorstoobtainagiantconnectedcomponentintheWSN.BysolvingtheoptimizationproblemwecontributetotheliteratureonWSNsinparticularandtoNetworkScienceingeneral.Ourcontributionsareasfollows,1.Thevalueoftheoptimaldegree(=5)hassigni¯cantimplicationsinthedesignoftheWSNnetworktopologyandprotocols.Unlikepreviousresultswhichinsistedthattheoptimaldegreeisafunctionofthenumberofnodes(N)andincreaseswithN[52,53,54,55,56,57],ourresultshowsthatwecaneasilyboundthedegreetoascalarvalue5whichisindependentofN.2.Weachievethisoptimalboundeddegreebyweakeningtheconnectivityre-quirement.Thatis,weconstructnetworksthathavegiantconnectedcom-ponentsandarenotrequiredtobeentirelyconnected.3.Thisimpliesthattheinterferenceatanynodeinthenetworkisboundedanddoesnotgrowwithincreasingnetworksizes[58,38,6].4.Oursisthe¯rstanalyticalproofontheexistenceofaboundednodedegreetomaintainconnectivityinWSNs.5.Further,protocolsdesignedforWSNmaintenanceandcommunicationscanbestandardizedtoapplicationsofvaryingsizes.1.3ThesisorganizationTherestofthethesisisorganizedasfollows.Chapter2broadlydiscussestheconceptofnetworks,networkpropertiesandnetworkmodels.Webeginthischap-terwithade¯nitionofnetworksandtheircomponents.Thisisfollowedbyareviewofpropertiesofnaturalcomplexnetworksinsection2.2,modelsofnaturalnetworksinsection2.3andabriefreviewofvariousdynamicalprocessestakingplaceonthesenetworksinsection2.4.Intheendofthisdiscussionwereiteratethesigni¯canceof¯ndingclusteredstructuresinnaturalcomplexnetworks.Inthesecondhalfofchapter2wefocusspeci¯callyonWSNs.Insection2.6weintroducethecomponentsofsensornodesandhowWSNsareformed.Insection2.6.1we 17elaborateonpowere±ciencyandinterferencesinWSNsandhowthisa®ectstheproblemofconnectivity.Wefollowthiswithadetailedlookatsensornetworkmodelsinsections2.6.2and2.6.3andidentifywhichamongthesenetworkmodelswewillusetosolveourproblemofconnectivityinWSNs.Chapter3isdedicatedtoanin-depthanalysisof¯ndingclusteredstructuresinnaturalcomplexnetworks.Webegin(section3.1)withacomprehensivere-viewofpriorworkrelatedto¯ndingclusteredstructures.Insection3.2wegivedetailsoftheproposedlabelpropagationalgorithmandanalyzethequalityofresultsobtainedfromtestnetworks.Insection3.3wevalidatethelabelpropaga-tionalgorithmusingnetworkswheretheclustersarealreadyknown.Insection3.4weevaluatethealgorithm'stimecomplexity.Insection3.5wecomparetheperformanceandqualityofresultswithalgorithmsalreadyexistinginliterature.Chapter4isdedicatedtoanin-depthanalysisoftheconnectivityprobleminWSNs.Hereagainwebeginthechapter(section4.1)withacomprehensivereviewofpriorworkonnetworkconnectivityinWSNs.Insection4.2wereviewsomeoftheprotocolsusedinsensornetworkstomaintainitstopology/connectivity.Insection4.3wederivetheconditionsforoptimalconnectivityandsupportitwithsimulationresults.Wealsoevaluatethepowere±ciencyofoptimalnetworkanddiscusshowtheoptimalparameterschangeforstrongconnectivity.We¯nallyconcludeinchapter5withasummaryofresults,contributionsanddetailsofalistofproblemsidenti¯edforfutureresearch. Chapter2Propertiesandmodelsofcomplexnetworks-AnoverviewIwanttogoonlivingevenaftermydeath!AndthereforeIamgratefultoGodforgivingmethisgift,thispossibilityofdevelopingmyselfandofwriting,ofexpressingallthatisinme.Icanshakeo®everythingifIwrite;mysorrowsdisappear,mycourageisreborn."|AnneFrankManynaturalnetworksarealreadyorganizedeveniftheirorganizationisnotaprioriknownorspeci¯ed.Becauseoftheexistingorganization,thesenetworksdis-playspeci¯cproperties.Whilewecanobservethesepropertiesinnaturalnetworks,thescienti¯cinterestisinidentifyingtheprinciplesbehindsuchanorganization.Forthisidenti¯cation,weconsidervariousclassesofnetworkmodelsinwhichwealreadyknowtheprinciplesoforganizationandstudyhowwelltheirpropertiesmatchwiththoseofnaturalnetworks.Aswewilldiscussinthischapter,theorganizationoflinksbetweennodesinnaturalnetworkswasoriginallyconsideredtoberandom[8,4].However,recentempirical¯ndingsshownetworkfeatures(suchasaright-skewedheterogeneousdegreedistribution,small-worldness,highdegreeoflocalorder)thatdeviatefromrandomness[9,11,47].Thischapterbeginswithareviewofmanystatisticalpropertiesusedtoidentifyordersandcharacterizenetworks[8,4].Wewillthenreviewsomeofthenetworkmodelsandevaluatethembasedonhowwelltheir 19propertiesmatchwiththoseofnaturalnetworks.Thiswillbefollowedbyabriefoverviewofnetworkdynamicsandprocessesthatarestudiedonthesenetworkmodels.Intheendofthisdiscussionwewillclarifytheimportanceof¯ndingclusteredstructuresinnetworksandhowthey¯tintothescienti¯cstudyofnaturalcomplexsystems.Inthesecondpartofthischapter,wewillnarrowdownourfocustoWSNs.Here,unlikenaturalnetworks,theorganizationoflinkshastobeengineered.Thatis,ourprimarilygoalistohelpsensornodestoidentifytheircommunicationsinordertoachievecertainfundamentaltopologicalproperties,namelyconnectivity.Webeginthispartofthechapterwithabriefintroductiontosensornodesandtheircomponents.Wewillthenreviewtwofactors,namelypowerandinterferencethata®ectourchoiceofnetworkmodels.ThiswillbefollowedbyareviewofcurrentlyusedWSNnetworkmodelsandinspeci¯c,thenearestk-neighborsnetwork.Wewillfurtherdiscusshowweachieveourobjectivebyoptimizingtheparameterkinthismodel.Beforewebeginwiththedetailswewillbrie°yintroducethede¯nitionofanetworkanditscomponents.2.1Networks:De¯nitionAnetworkconsistsofasetofnodesVandasetofedgesE.Anedgee2Econnectsexactlytwonodesve;ue2V.ueisthensaidtobeaneighborofveandvice-versa.Ingeneralitisnotrequiredforve6=ueandinthecasewhenve=ue,theedgeeiscalledaloop.Also,therecanbetwoedgese1;e22E(ormore)thatconnectthesamepairsofnodesinV.Inthiscasethenetworkissaidtocontainmultipleedges(see¯gure2.1).Ifedgeshavedirectionsassociatedwiththem,thenthenetworkiscalledadirectednetwork.LetDbethesetofedgesinadirectednetwork,thenad2D,connectingud;vd2V,issaidtobeoriginatingfromudanddirectedtowardsvd(see¯gure2.1).Anetworkingeneralcanhavebothundirectedanddirectededgesalongwithmultipleedgesandloops.Inthisthesis,wewillonlyconsidernetworksthatdonotcontainmultipleedgesorloops.Inadditionallnetworksweconsiderwillhaveonlyundirected 20Figure2.1.Anillustrationofnetworkswithdi®erentkindsofedges.(a)representsanetworkthatcontainsdirected,undirectedandmultipleedgesandloops.Inthisthesisweassumeallnetworkstobeundirectedasdepictedin(b)unlessotherwisementioned.Theonlyotherkindofnetworksthatweconsiderisadirectednetworkasshownin(c).edgesunlessotherwisementioned.InafewcasessuchastheWWWonecanconsiderdirectionsassociatedwithedges,originatingfromawebpageanddirectedtowardsanotherwebpagethatisbeinghyper-referenced.Aswewillsee,directededgesformanintegralpartofWSNnetworkmodelsandwewillconsideradirectednetworkmodeltosolvetheconnectivityproblemonWSNs.2.2PropertiesofnaturalcomplexnetworksErd}osandR¶enyiproposedarandomgraphmodeltorepresentnetworksthathavenoapparentstructureorpatternintheirorganization(E-Rrandomgraphs)[8,1].Thatis,givenasetofNnodesandaparameterplyingbetween0and1,everypairofnodesinthenetworkisconnectedwithaprobabilityp(see¯gure2.2).Thismodel,proposedinthe1950swasconsideredagoodrepresentationofnaturalcomplexnetworksandmanyresultsexistthatcancapturethecharacteristicsandpropertiesofthismodelfordi®erentvaluesofp[1].However,withanincreasingavailabilityofdataonlarge-scalenetworkssuchasactorcollaborations,scienti¯cco-authorship,WWWandidenti¯edinteractionsbetweenbio-moleculesinvariousorganisms,empiricalevidenceshowordersinnet-worksthatdeviatefromrandomness[8,51].Inspeci¯c,themacroscopicpropertiesofnaturalnetworksshowsigni¯cantdeviationsfromthepropertiesofE-Rrandomgraphs. 21Figure2.2.Evolutionofrandomgraphsastheconnectionprobabilitypincreasesfrom0.Notethataspincreasesthenumberofedgesinthenetworkalsoincreases.Inthelastfewyearsmanystatisticalpropertieshavebeenusedtoidentifyordersandcharacterizecomplexnetworks.Thefollowingareafewsuchpropertiesthatareprominentlyusedintheliterature.2.2.1AverageshortestpathlengthGivenapairofnodesu;vinanetwork,apathexistsbetweenthem,ifwecan¯ndnodesu=x0;x1;x2;:::;xn¡1;xn=vsuchthatthereisanedgebetweenxiandxi+1,andxi6=xj8i6=j.Thelengthofsuchapathisn.Ashortestpathbetweenuandvisanypathwiththesmallestnamongallsuchpossiblepaths.Forexample,v3;v5;v4;v7isapathoflength3betweenv3andv7inthenetworkin¯gure2.1(b)andv3;v4;v7isthepathofshortestlength2betweenv3andv7.Theaverageshortestpathlengthofanetworkisde¯nedastheaverageofallsuchshortestpathlengthsbetweeneverypairnodesinthenetwork.Letd(u;v)denotethelengthoftheshortestpathbetweennodesuandv.Thentheaverageshortestpathlengthloftheentirenetworkisde¯nedas2Xl=d(u;v)N(N¡1)u6=v2VInthecasewhenthereisnopathbetweentwonodes(forexample,betweenv1andv3in¯gure2.1(b))theshortestpathlengthisconsideredtobe1.Anetworkissaidtobesmall-worldif,despiteitslargesize,theaverageshortestpathlengthisrelativelysmall[51].Thepopularnotionofsixdegreesofseparationinsocialacquaintancenetworksisaparticularinstanceofthesmall-worldconcept. 22Table2.1.ComparisonofaveragepathlengthslrealinnaturalnetworkswithlrandofE-Rrandomgraphsofthesamesizes.NetworkSizelreallrandReferenceMovieactors225,226613.652.99[11]MEDLINEcoauthorship1,520,25118.14.64.91[14,15,16]WWW153,12735.213.13.35[60]Internet,routerlevel228,2982.801112.8[21]MetabolicNetwork,E.Coli7787.43.23.32[5]NeuralnetworkofC.Elegans282142.652.25[11]InaletterpassingexperimentconductedbysocialpsychologistStanleyMilgram[59],itwasfoundthatanytwopeopleintheUnitedStatesareconnectedonanaveragebyonlyachainofsixacquantances.InthisexperimentapersonischosenrandomlyfromanywhereintheUnitedStatesandisgivenaletterthathastoreachatargetpersonwhoagaincouldbelocatedanywherewithintheUnitedStates.Everyonewhoreceivesthelettercanonlysendittooneoftheiracquaintances(i.e.viaanedgetoanothernodeintheirsocialnetwork)whotheythinkwillknowthetargetperson.InthisexperimentMilgramfoundthatinmostcasestheletterreachedthetargetpersoninsixsteps[59].Quantitativelyspeaking,anetworkonNnodesissaidtobesmall-worldiftheaverageshortestpathlengthlscalesasO(logN)[8,11].ThepresenceofsuchsmallshortestpathsbetweennodesariseseveninE-Rrandomgraphs[8]implyingthatthereisnospecialorganizingprinciplethatleadstosmall-worldness.Aswecanseefromtable2.1theaveragepathlengthsinE-Rrandomgraphsareingoodagreementwiththoseofnaturalnetworks.2.2.1.1ConnectedcomponentsAconnectedcomponentinanetworkisamaximalsetofnodesthathavepathsof¯nitelengthsbetweeneverypairofnodeswithintheset.Nodesv1andv2formoneconnectedcomponentwhilev3;:::;v8formanotherconnectedcomponentin¯gure2.1(b).Inallnaturalnetworksthelargestconnectedcomponentusuallyconsistsofallbutasmallfractionofnodesinthenetwork.Hencetheaverageshortestpathlengthiscalculatedonthislargestcomponentandistakentobeanindicationof 23Table2.2.Comparisonoflocalordercoe±cientLrealinnaturalnetworkswithLrandofE-Rrandomgraphsofthesamesizes.NetworkSizeLrealLrandReferenceMovieactors225,226610.790.00027[11]MEDLINEcoauthorship1,520,25118.10.0661:1£10¡5[14,15,16]WWW153,12735.210.10780.00023[60]Internet,domainlevel11,1744.180.223:7£10¡4[61]Internet,routerlevel228,2982.800.031:2£10¡5[61]NeuralnetworkofC.Elegans282140.280.05[11]theaverageshortestpathlengthoftheentirenetwork.Theaverageshortestpathlengthinthelargestcomponentformedbynodesv;:::;vin¯gure2.1(b)is25.38152.2.2LocalorderInE-Rrandomgraphsanytwonodesinthenetworkhasthesameprobabilitypofbeingconnectedindependentofthepresence/absenceofedgesbetweenotherpairs.WattsandStrogatz[51]foundthatthisisnotthecasewithnaturalnetworks.Inparticularapairofnodesthathasoneormorecommonneighborshasahigherprobabilityofbeingconnected.Inotherwords,givenanodeuthathaskneighbors,pairsofneighborswhoareconnectedissigni¯cantlyhigherthanwhatisexpectedbyarandomchance(seetable2.2).k(k¡1)IfK=andEisthenumberofedgesbetweenneighborsthatactually2existinagivennetwork,thenthelocalordercoe±cientLuatnodeuistheratioE.Nodevinthenetworkin¯gure2.1(b)has4neighborsandthereforeK=6.K4Therehoweverexistsconnectionsonlybetweenv3andv4andv6andv7makingE=2.HenceL=2=1.Nodevthathasonlyoneneighborisconsideredv4638tohavealocalordercoe±cientof0.Thelocalordercoe±cientLoftheentirenetworkisde¯nedastheaverageofthelocalordercoe±cientsatindividualnodes,1XL=LuNu2VAlso,observationsshowthatthedistributionoflocalorderatnodesinmany 24Figure2.3.TheobservedprobabilitydistributionP(k)inanE-Rrandomgraphofsize10000andconnectionprobabilityp=0:002.ThesolidlineisthePoissondistributionwithparameter¸=20andwecanseeagoodagreementbetweenobservedandtheo-reticalprobabilities.Mostnodeshaveadegreeequaltothemean=20andthenumberofnodeswithotherdegreesfallexponentiallyoneithersideofthemean.naturalnetworksisheterogeneousandisproportionaltotheinverseofthedegreesatthenodes.Inspeci¯c,L(k)»k¡1,whereL(k)isthelocalordercoe±cientonanodewithdegreek[62].2.2.3DegreedistributionThedegreeofanodeisthenumberofedgesincidentonthatnode.ThedegreedistributionistheprobabilitydistributionP(k)foragivennodeinanetworktohaveadegreek.Givenanetwork,saythenetworkin¯gure2.1(b),wecanempiricallydetermineitsdegreedistribution.Amongthe8nodesinthenetworkv1;v2andv8havedegree1each,whilev3;v5andv7havedegree2each.v6hasdegree3andv4hasdegree4.Therefore,theprobabilitythatanygivennodewillhavedegree1is3,degree2is3,degree3is1anddegree4is1.Theprobability8888foranodetohaveanyotherdegreeis0.P(k)forE-RrandomgraphsisaPoissondistributionwiththehighestproba-bilityatthemean(see¯gure2.3)andtheprobabilitiesfallingo®exponentiallyat 25Figure2.4.TheobservedcumulativeprobabilitydistributionP(k)on(a)aco-authorshipnetworkofscientistsinthe¯eldofcondensedmatterphysics,afterNewman[14]and(b)WWWnetworkofwebpageswithinthend.edudomain,afterAlbertetal.[9]respectively.ThedegreesonthenodesinnaturalnetworksarehighlyheterogeneousunlikeE-Rrandomgraphsinwhichnodesarehomogeneousindegree.eithersideofthemean.Thisimpliesthatmostnodesinthenetworkhaveadegreeclosertothemean.Ontheotherhand,innaturalnetworksitisnotpossibleto¯ndsuchacharacteristicdegreeorscaleonthenodes[9,36,8].Thereusuallyexistsnodeswhosedegreesaremuchhigherthanthemeanandthisheterogeneityinnodedegreecanbewellapproximatedbyapowerlawdegreedistribution(see¯gure2.4).Thatis,P(k)»k¡°where°isusuallybetween2and3inmanynaturalnetworks[8].Becauseofthelackofacharacteristicscalethesenetworkswithapower-lawdegreedistributionaretermedasscalefreenetworks[8].PPPWhenP(k)»k°themeanisk¡°+1andthevarianceisk¡°+2-(k¡°+1)2.PSincek¡®convergenceonlywhen®>1anddivergesotherwise[63],themeanis¯niteonlywhen°>2andthevarianceis¯niteonlywhen°>3.Hencemostnaturalnetworksthathave°between2and3haveameandegreethatis¯niteandanin¯nitevariance. 26Table2.3.Themixingpatternsinnaturalnetworks[64].r>0indicateanassortativemixingpatternandr<0indicateadis-assortativemixingpatterninthenetworks.NetworkSizerReferenceMovieactors449,9130.208[11]MEDLINEcoauthorship1,520,2510.127[15,16]Physicscoauthorship52,9090.363[15,16]WWW269,504-0.067[9]Internet10,697-0.189[64]NeuralnetworkofC.Elegans307-0.226[11]MetabolicNetwork,E.Coli765-0.240[5]2.2.4MixingpatternsAssortativeanddis-assortativemixingpatternsinnetworksisthetendencyofnodestoassociatethemselveswithothernodesthatarelikeorunlikethemrespec-tively.Newman[64]studiedthemixingpatternsinvarioussocialnetworksbasedoncharacteristicsofnodes/peoplesuchasrace,sex,ageandtheirdegrees.Whenconsideringthemixingpatterninnetworkswithrespecttonodedegrees,Newman[64]showedthatinnaturalnetworksthepossibilityoftwonodesbeingconnectedisalsodependentonthedegreesonthesenodes.Inspeci¯c,socialnetworkstendtohaveassortativemixingpatternswherepeopleofsamedegree(ormaybepopularity)aremorelikelytorelatetoeachother.Whileintechnologicalandbiologicalnetworks,anodeofhighdegreeshowsapreferenceinattachingtonodesoflowdegreeandviceversaformingadis-assortativemixingpattern(seetable2.3).Tocalculatetheassortativeordisassortativenatureofagivennetwork,New-mansuggestedto¯ndthecorrelationbetweennodedegreesateitherendsoftheedgesinthenetwork[64].Givenarandomlychosenedge,letqkstandfortheprobabilitythattheremainingdegreeonthenodethisedgeisincidentuponisk.Letekjbethejointprobabilityfortheremainingdegreesateitherendsofanedgetobejandk.Then,wecancalculatethenatureofthemixingpatternby,1Xr=2jk(ejk¡qkqj)¾qjk 27whichisnothingbutthePearson'scorrelationcoe±cientforthedegreesateitherendsofedges[65].¾2isthevarianceofthedistributionqandisthenormalizingqkfactorintheaboveequation.rtakesvaluesbetween¡1and1wherer=¡1indi-catesperfectdis-assortativityandr=1indicatesperfectassortativity.r=0im-pliesthatthegivennetworkdoesnotshowsigni¯cantassortativeordis-assortativemixingpatterns.Newmanshowedthatformanysocialnetworks(includingscien-ti¯cco-authorshipsandactorcollaborations)r>0indicatingassortativemixingpatternsandr<0forawiderangeofbothtechnologicalandbiologicalnetworksindicatingdis-assortativemixingpatterns.Forthepracticalpurposeofcalculatingrinagivennetwork,theaboveequationcanbere-writtenas,PPM¡1jk¡(M¡1(1j+k))2Piii2iPiir=M¡1(1j2+k2)+(M¡1(1j+k))22iii2iiiwhereMisthenumberofedgesinthenetworkandjiandkiarethedegreesateitherendsofanedgei,i=1;:::;M.2.2.5ClustersGivenanode,notallnodesinanetworkarelikelycandidatestoestablishcon-nectionswith.Thesetoflikelycandidatesisdominatedbyasubsetoragroupofnodeswithinthenetworkcalledasacluster.Aclusterisusuallythoughtofasagroupwhichisdenselyinterconnectedwithinandhasarelativelysparseinteractionoutsideofthegroup.Bypartitioningnodesinagivennetworkintoclusters,wecanmeasurehowgoodsuchapartitionis.Forexample,Newman[47]de¯nedamodularitymeasurePQ=i(Di¡Ei)thatcalculates,givenapartitioningofnodesintogroups,thedi®erencebetweenthedensitywithinagroupi(Di)observedinthenetworkandthedensitywithinthesamegroupiexpectedbyarandomchance(Ei).Qisnormalizedtotakevaluesbetween¡1and1.ValuesofQgreaterthan0andcloserto1indicateshighermodularityorclusterednatureofthepartition.(ValuesofQlessthan0andcloserto¡1impliesthatthepartitionissuchthatmostoftheedgesarebetweengroupsandlittleornoedgeswithingroups).Table2.4shows 28Table2.4.ModularitymeasureQinnaturalnetworksobtainedusingourproposedclusterdetectionalgorithm(seechapter3).NetworkSizeQReferenceFriendshipnetwork350.355-0.399[67]Collegefootballnetwork1150.457-0.476[40]Protein-proteininteraction,S.Ceresiviae2,1170.738-0.745[29]Physicscoauthorship16,7260.720-0.722[15]WWW325,7290.857-0.864[9]Movieactors374,5110.437-0.528[36]thevaluesofQobtainedfrompartitioningnaturalnetworksusingourproposedclusteralgorithm(seechapter3).Also,whilethesearethemeasuredmodularityinthenetworksusingourclusterdetectionalgorithm,theremightexistapartitioninthesenetworksthatcanhaveahigherQ.Ingeneral,¯ndingapartitioninagivennetworkthatmaximizesQisNP-hard[66].Anotherwaytoidentifyclustersisbyde¯ningwhatkindofinterconnectionpatternswithinasubsetofnodesconstitutesaclusterand¯ndallsubsetsinthenetworkthatsatisfythede¯nition.Onesimplede¯nitionisthepresenceofanedgebetweeneverypairofnodeswithinthegroup(whichiscalledaclique).Forotherde¯nitionsofclusterssee[68,3],someofwhicharealsodetailedinchapter3.Byconsideringchainsofcliques(de¯nedasasequenceofcliquesinwhichadjacentcliquesonknodeshavek¡1commonnodes)asacluster,Pallaetal[2]haveshownthatclustersinsocialandbiologicalnetworksoverlap(orthereexistscommonnodesintwoormoreclusters).Further,theyalsoshowedthatifthereexiststwoclustersthatoverlapwithacommoncluster,thentheythemselvesarehighlylikelytooverlap.Clustersinascienti¯cco-authorshipnetworkshowgroupingofscientistsintotheirrespectivedisciplineorfocusarea[66].ItisalsopossibletocommonlyobservescientistsworkingwiththesameUniversityorInstitutetobegroupedtogetherintoacluster.Clustersinbiologicalnetworksre°ectfunctionalgroupings,andGuimeraandAmaral[41]showedthatnodesattheperipheryofaclustersharingedgeswithnodesfrommanyotherclustersarethemostbiologicallyconservedbio-molecules 29invariousorganisms.2.3ModelsofnaturalcomplexnetworksSmallaverageshortestpathlengthsorheterogeneousdegreedistributionsorclus-teredstructuresinnaturalcomplexnetworksariseduetotheinterconnectionpat-terns.Modelinge®ortsinthenetworkscienceliteraturemostlyfocusedoniden-tifyingtheseorganizingprinciplesofnaturalnetworks,andincorporatingtheminanetworkmodeltoobtainbetterinsights.Inthissectionwewillreviewsomeofthesemodels,namelyrandomgraphs,small-worldnetworksandscale-freenet-worksandidentifyhowtheirpropertiescomparewiththepropertiesofnaturalnetworks.2.3.1RandomgraphsThefollowingstepscharacterizetheconstructionofanE-Rrandomgraph.²StartwithasetofNisolatednodesand²ConnecteachpairofnodeswithaconnectionprobabilitypAstheprobabilitypincreasesfrom0,thenumberofedgesinthenetworkalsoincreases.Figure2.2showsthisevolutionforincreasingvaluesofpfrom0to0.2inanetworkof20nodes.Whenp=1itissimplyacompletegraphorclique.LetkbethedegreeonthenodesandP(k)betheprobability(ordegree)distribution.ThenP(k)=Ckpk(1¡p)N¡1¡k.GivenanodethereareN¡1N¡1othernodeswithwhichitcanpossibilityhaveedgesandamongthesewechooseknodesinCkways.TheprobabilitythatthenodehasedgeswithexactlytheseN¡1knodesispk(1¡p)N¡1¡k.¡kIntheasymptoticlimit(N!1),P(k)becomese,where=k!pN.Hencemostnodesinagivenrandomgraphhaveadegreeclosetothemean(),withsmallerorlargerdegreesbecomingexponentiallyrare(see¯gure2.3).Thelocalordercoe±cientofanE-Rrandomgraphissimplytheconnectionprobabilityp.Thisisbecause,theprobabilitythatanytwonodesareconnected 30isp,anditisindependentoftheexistenceofconnectionsbetweenanyotherpairsofnodesinthenetwork.AlsoE-Rrandomgraphsdonotshowanyspeci¯cmixingpatternsasthecorrelationcoe±cientr=0[64].Ontheotherhand,theaveragepathlengthlscalesaslogNandhavevaluesthatareingoodagreementwithnaturalnetworksofthesamesize[8].Thevaluelcanbecalculatedinthefollowingmanner.Thenumberofnodesatadistancedfromagivennode(nodeswithwhichtheshortestpathlengthisd)isd.Hencetocoverallthenodesl»NlogNandthereforel=.Foramorerigorouscalculationsee[1].logAnimportantadvantageofE-Rrandomgraphsisthattheyarebothintuitivelyandmathematicallytractableandarehencetheyarestillextensivelyusedforanalysisofcomplexnetworks.Someoftheinterestingquestionsthatwerestudiedfromtheevolutionofrandomgraphsis,forwhatvaluesofpisthegraphconnected?Howdoesthecharacteristicsofthetopologychangeaspvariesandwhatkindofsubgraphsarepresent?2.3.1.1TransitionprobabilitiesandgiantconnectedcomponentsInfact,ErdÄosandR¶enyishowedthatforagivenprobabilitypandasetofNnodeseithereverygraphhasapropertyQoreverygraphdoesnothavethepropertyQ[1,8].Thatis,aspincreasesgradually,thetransitionfromapropertybeingveryunlikelytobecomingverylikelyisusuallyswift.Thereexistsacriticalthresholdpc(N)foranyQsuchthatforppc(N)everygraphbeginstodisplaythepropertyQ.Inparticular,oneofthe¯rstproblemsstudiedbyErdÄosandR¶enyiwastheappearanceofsubgraphsinE-Rrandomgraphsandtheircorrespondingtransitionprobabilities.GivenagraphG(V;E)onasetVofnodesandsetEofedgesthegraphH(U;D)isasubgraphofGifU½VandD½E.LetHbeanygraphonknodesandmedges,thenthereexistsarigorousproofthatshowsthecriticalthresholdpc(N),forE-RrandomgraphstohavesubgraphsoftheformH,is¡kpc(N)»Nm[1,8].Wecaninfactseethisfromthefollowingarguments.Supposethatwe¯rst¯ndhowmanysubgraphsX,oftheformHdoesE-RrandomgraphsonNnodesandaconnectionprobabilityp(denotedasER(N;p))have.Thenthecriticalthresholdpc(N)willbethesmallestprobabilityforwhichX¸1.knodescanbe 31chosenfromER(N;p)inCkwaysandtheywillhavemedgeswithaprobabilityNpm.Wecanalsopermutetheknodesink!di®erentwaystoobtaink!newgraphsofwhichsayagraphsareisomorphictoeachother.ThentheexpectednumberofsubgraphsE(X)onknodesandmedgesisk!NkpmkmE(X)=CNp'aaEventhoughtheactualnumberofsubgraphsXcouldbedi®erentitwillbeequaltoE(X)inmostcases[1].Whenp(N)isoftheformcNzwherez<¡kandmcisanappropriateconstant,wecan¯ndanN¤su±cientlylargesothatE(X)¼0forN¸N¤.Ontheotherhandwhenz=¡k,E(X)takesa¯nitevaluedenotedmcmby¸=,whichmarksthetransitionintoaregionwherealmosteverygrapha¡k¡kER(N;p>cNm)hasasubgraphoftheformH.Infact,whenpc(N)=cNm,itcanbeshownthattheprobabilityP(X¸1)!1ascincreasesinthelimitN!1[1,8].Indeed,givenasetofNnodes,thetopologyofE-Rrandomgraphsaspin-creasesfrom0canbecharacterizedbythesubgraphstheycontain.Therearethreesuchsubgraphs,namelycycles,treesandcompletegraphs,thatareusedtode¯nethecharacteristicsofthetopologyfordi®erentvaluesofp.Acycleisapathx0;x1;:::;xkinwhichx0=xkandissaidtobeofsizek.Agraphonknodesandk¡1edgesisatreeofsizekifithasnocycles.Andacompletegraphofsizekasde¯nedearlierisacliqueonknodes.Letussupposethattheconnectionprobabil-ityphastheformp=cNz.Whenzisverysmalland!¡1therandomgraphcontainsnoedgesandisjustacollectionofNnodes.Whenzincreasesgraduallyandcrosses¡3,treesofsize3begintoappearinthenetwork.Similarly,whenz2crossesthepoints¡4and¡5,treesofsizes4and5respectivelybegintoappear34inthenetwork.Thisphenomenacontinuesuntilzincreasesfurthertowards¡1.Exactlywhenzcrossesthepoint¡1theasymptoticprobabilityforappearanceofcyclesofallsizesjumpsfrom0to1.Andaszincreasesfurtherandcrossesthepoint¡4completegraphsofsize4begintoappearinthenetworkfollowedby6completegraphsofincreasingsizesaszincreasesfurthertowards0.Whenz=0therandomgraphbecomesacompletegraphofsizeNandhencehasallformsofsubgraphsinit. 32Figure2.5.ThesizeofthelargestconnectedcomponentinanE-Rrandomgraphof1000nodesisplottedagainsttheconnectionprobabilityp.Aspincreasesgraduallywecanseeasuddenincreaseinthesizeofthelargestconnectedcomponent.Further,ErdÄosandR¶enyishowedthatwhenzcrossesthepoint¡1,thetopol-ogyofE-Rrandomgraphsshowinterestingpropertieswithrespecttothesizeoftheconnectedcomponents.Thatis,untilzreaches¡1,therandomgraphsarealoosecollectionofsmallcomponents(alsosometimesreferredtoasclusters)whereeachcomponenthasatreelikestructure.InfactthenumberofnodesinthelargestconnectedcomponentisapproximatelylnNwhenzisjustlessthan¡1.Howeverwhenzcrosses¡1,thesizeoflargestcomponentincreasesabruptlyhavinga¯nitefractionofthetotalnumberofnodesN[1,8].Thereforez=¡1marksthetran-sitionofthelargestconnectedcomponentintoagiantcomponentinE-Rrandomgraphs(see¯gure2.5).Itisinterestingtonotethatwhenp(N)/N¡1,theaveragedegreeofthenetworkisaconstant.Thatis,=p(N¡1)¼pN/1.InfactasErdÄosandR¶enyishowc=1andthisisthecriticalaveragedegreeonthenodesatwhichE-RrandomgraphsofanysizeNtransitionsfromaloosecollectionofsmallcomponentsintoagraphthatisdominatedbyagiantconnectedcomponent[1,8].From¯gure2.5wecanseethatinanetworkof1000nodesthecriticalprobabilitypisapproximately0.001.Exceptforthegiantcomponent,theremainingconnectedcomponentsinthegrapharesmallwithmostofthemhaving 33atreelikestructure.Andaszincreasesfrom¡1thesizeofthegiantcomponent(S)increasesproportionaltothedi®erenceofpfrompc,i.e.,S/(p¡pc)[8].Itisimportanttonotethatthephenomenonoftheoccurrenceofgiantcomponentsinlatticesandnetworksiswidelystudiedinmathematicsandinthestatisticalmechanicsliteratureunderthenamepercolationtheory[8,1,69].2.3.1.2Non-uniformrandomgraphsTherealsoexistsclassesofrandomgraphmodelsthatmimicpropertiesofthepower-lawdegreedistributionsofnaturalnetworks.GivenasetofNnodes,thesemodelsrequireasinputeitheradegreesequence,whichisanN-tupleofdegrees(k1;:::;kN)oraprobabilitydistributionP(k).IfwearegivenaP(k),thedegreesequenceisgeneratedfromthisdistribution.Oncewehaveadegreesequence,eachnodeinthenetworkisassignedexactlyonesuchdegreekifromthesequence.WecanimaginethisassignmentasasetofNnodeswitheachnodeihavingkihalf-edgesorstubsassociatedwithit.Then,pairsofhalf-edgesareuniformlyrandomlychosenandjoinedtogethertoformcompleteedges[70,71].Insuchnetworks,givenaP(k),MolloyandReed[70]showedthatagiantcomponentexistsalmostsurelyP1ifk¸1k(k¡2)P(k)>0,providedthemaximumdegreeislessthanN4.ThecasewhenP(k)»K¡°,theconditionreducesto°<3:47[8,37],whichisindeedtrueinmostnaturalnetworks[8,10].Newman,WattsandStrogatzhandlethelimitingcaseofgeneralizedrandomgraphsbasedongeneratingfunctionswhichisalsoextendedtodirectedgraphsandbi-partitenetworks[71].Newman[64]alsoproposedrandomgraphmodelsforagivendistributioninwhichthemixingpatternscanbevaried.At¯rst,givenadegreedistribution,adegreesequenceiscreatedforNnodesandagraphisformedasdescribedabove.Then,ateverystep,twopairsofedges,(u1;w1)and(u2;w2),arechosenuniformlyrandomly.Basedontheremainingdegreesatthesenodes,say(j1;k1)and(j2;k2)respectively,aprobabilityp(j1;k1;j2;k2)ischosen,whichisafunctionoftheremainingdegrees,withwhichtheedgesareswapped.Thatis,(u1;u2)and(w1;w2)willbethetwonewedgesreplacingtheoldonesinthenetwork.SuchamethodwillmaintainthedegreeatthenodesandNewmanshowedthatwecanchoosetheprobabilitypappropriatelytoobtainacorrelationrrangingbetween¡1and1[64]. 34ExponentialRandomGraphModels(ERGM),anotherclassofgraphmodels,areacollectionofnetworksonNnodeseach[72,73,74,75,76,77].HereanetworkGappearswithaprobabilityP(G)/e¡¸,where¸isaweightedsumofasetofobservablepropertiesf²ig.Elementsofthissetf²igcanbe,forexample,thenumberofnodeswithcertaindegree,numberoftrianglesetc.Givenasetofweightscorrespondingtothepropertiesf²ig,thenetworksaregeneratedusingGibbsorMetropolis-Hastingssamplingmethods[76].Thisclassofnetworksismainlyusedinthemodelingandanalysisofsocialnetworks[77].2.3.2Small-worldnetworksAsmentionedearlier,WattsandStrogatzobservedthatthelocalordercoe±cientatindividualnodesandintheoverallnetworkwassigni¯cantlyhigherinnaturalnetworks[51].Thatis,thelocalordercoe±cientinacorrespondingE-Rrandomgraphwiththesamenumberofnodesandedgesisverypoor.However,WattsandStrogatzalsoobservedthatnaturalnetworksarenotcompletelyordered.InfactE-Rrandomgraphsdohavethesmall-worldbehaviorwhichisingoodagreementwithnaturalnetworks[8].Hencetheysuggestedthatnaturalnetworksliesomewherebetweenorderandrandomness.Tocapturetheappropriateregionbetweenorderandrandomnesstheysuggestedthefollowingsmall-worldnetworkmodel.²Beginwithahighlyorderedringlatticeinwhicheachnodehasconnectionswiththeclosestknodes.²Rewireeveryedgeinthenetwork,eachwithaprobabilityp,suchthatoneendremainsthesameandtheotherendischosenuniformlyrandomlyfromtherestofthenodes.Caremustbetakentoavoidmultipleedgesandloops.Whenp=0thenetworkisaregularlatticeandwhenp=1itbecomesarandomgraph(see¯gure2.6).However,WattsandStrogatzshowedthatthereexistsarangeofvalues0NobservedinrandomNgraphs[80].Followingtheproposalofthisevolvingscale-freenetworkmodel,morere¯nedmodelshavebeenproposed,leadingtoawelldevelopedtheoryofevolvingnetworks[8,10,81,4,36,82,83].2.4DynamicalprocessesonnaturalnetworksOneoftheprimaryreasonstounderstandandmodelcomplexsystemsistoeven-tuallycontroltheprocessestakingplaceonthem.Forexample,wewanttounder-standthemechanismsbywhichvirusesordiseasesspread.WestrivetooptimizeinformationretrievalandresourcesharingovertheWWWandtheInternet.Inthissectionwebrie°ydiscusssomeimportantresultsofdynamicalprocessesandtheirbehaviorsinthemodelsofnaturalcomplexnetworks.2.4.1NetworkresilienceManynaturalcomplexsystemsarehighlyrobustandtolerantofperturbations.IntheInternetforexample,despitefrequentrouterproblems,theoverallabilityofthe 37networkincarryingdatapacketsremainse®ective.Also,functionsoforganismsandtheirabilitytopersistandreproducedespiteenvironmentalinterventionsisattributedtotherobustnessoftheunderlyingmetabolicandgeneticnetworks[8,29].Functionalitiesofthenodesandnetworkdynamicsareonesetoffactorsresponsiblefortheresilienceofcomplexsystems.Thisbeingthecase,ithasalsobeenshownthatdegreeofredundancyininterconnectionsandpropertiesofthenetworktopologiescanalsothrowlightontherobustnessofcomplexsystems[8,84].Noderemovalisacommonwaybywhichnetworktopologiesaretestedforresilience[8,84].Inparticular,wecanconsideranodechosenuniformlyrandomlyfromthenetworktohavefailedcalledasrandomfailureorspeci¯callytargetnodesofhighestdegreecalledastargetedattacks.Ineithercasethenodealongwithitsedgesareremovedfromthenetwork.Removalofanodecanbreakexistingpathsbetweenvarioussetsofnodesandpotentiallyleadtoanincreaseintheaveragepathlengthoradecreaseinsizeofthelargestconnectedcomponent.Figure2.7showstheresponseofanE-Rrandomgraphandapower-lawnetworkgeneratedusingtheBarabasi-Albertmodeltonodefailures.Wecanseethatdi®erenttopologieshavedi®erentkindsofresponsetorandomfailuresandtargetedattacks.Inbothnetworksthereisacriticalfractionfcofnodesatwhichthesizeofthelargestconnectedcomponentfallsquicklyto0.Inthecaseofrandomfailures,thisfractionfc=1¡1=pNforanE-RrandomgraphofsizeNandconnectionprobabilityp[8].Whenthemeandegree=pN=1,fc=0,andthereforefurtherremovalofanynon-zerofractionofnodeswillleadtoadisintegrationofthenetworkintosmallerclustersorcomponents.(Comparethiswithc=1fortheappearanceofagiantconnectedcomponentinE-Rrandomgraphs;ingeneralthesetwoprocessesaretheinverseofeachother).In¯gure2.7(a)pN==4fortheE-Rrandomgraphandwhenthefractionofnodesremovedisapproximatelyfc=0:75thesizeofthelargestcomponentbecomesnegligible.Ontheotherhandforapower-lawnetworkfc!0inthelimitingcaseofN!1and°<3[8,84].Thuspower-lawnetworksareextremelyresilienttorandomfailures.Thedropinthesizeofthelargestcomponentweseeinthe¯gure2.7(b)atavaluebefore1isthee®ectof¯nitesizescaling.Inthecaseoftargetedattacks,power-lawnetworksduetotheirrelianceon 38Figure2.7.Thesizeofthelargestconnectedcomponentinresponsetorandomfailures(denotedinsquares)andtargetedattacks(denotedincircles)areplottedforan(a)E-Rrandomgraphanda(b)power-lawnetworkgeneratedusingtheBarabasi-Albertmethod.Boththesenetworkshave10000nodeseachandanapproximatemeandegree=4.highdegreenodesbreakatamuchsmallerthresholdincomparisontorandomgraphs[8,84].Inpower-lawnetworks,Newman[64]furtherdi®erentiatedfcfortargetedattacks.Inparticularheshowedthatthecriticalfractionfc,fortargetedattacks,ismuchsmallerinadis-assortativenetworkthananassortativenetworkofthesamesize.Noderemovalcanalsoa®ectthefunctionalityofanetwork.Inapowergridforexample,whichisanetworkofsubstations,ifasubstationfailstowork,thenthegeneratedpower,sinceitcannotbedestroyed,isre-routedviaothernodesinthenetwork[85].Asaresult,loadsonothernodesincreasesandresultincascadingfailures,ashappenedonAugust10th1996in11USstatesandtwoCanadianprovinces[86].Undersinglenoderemoval,Kinneyetal.[87]showedthat40percentoftransmissionsubstationsleadtocascadingfailuresintheNorthAmericanpowergrid.In[88],Motterproposedadefensestrategyinwhichafterthe¯rstfailure,byselectivelyremovingmorenodesandedgesonecanreducethe 39sizeofcascade.Forotherworkoncascadingfailuresreferto[85,89,90,91,92].2.4.2Spreadingprocessanddi®usionThespreadofdiseasesinsexualcontactnetworksanddi®usionofinformationintheInternetareproblemsofimmenseinterest.Theprocessofadiseasespreadinginapopulationhasbeenwidelyresearchedandmanymodelsofthespreadingmechanismhavebeenproposedandanalyzed[4].Initially,thepopulationonwhichdiseasedynamicswasstudiedwasassumedtobefullymixed,orinotherwords,anyindividualcanpotentiallya®ectanyotherindividualwithinthepopulation.Inreality,adiseasecanspreadfromoneindividualtoanotheronlyifthereisacontactofsomesort.Hence,alongwithanincreasinginterestinnetworkmodeling,therehasbeena°urryofactivitiestounderstandthedynamicsofspreadingprocessesinnetworks,yieldingradicallydi®erentresults[4,93,94,95,96,97].Inspeci¯c,forpower-lawnetworksitwasshownthatanynon-zerorateofdiseasetransmissionfromaninfectednodewillcauseanepidemic(alargefractionofnodesinthenetworkwillbea®ected)[94].Referto[95,98,99,100]forrevisionsofthisresultthatshowstheexistenceofnon-zerothresholdsfortransmissionratesinspeci¯ckindsofnetworks,namelythosewithhightransitivity[98]orcertaintypesofcorrelationbetweenconnectednodes[99,100].Withtheknowledgeondiseasespreadingdynamicsandnetworkresiliencetotargetedattacks,itwasproposedthatpeoplewithalargenumberofcontacts(orhighdegreenodes)shouldbevaccinatedtopreventadiseasefromquicklyspreadingtootherpartsofanetwork[101,96].Whilethisisnotasurprisingsuggestion,theproblemliesinactually¯ndingthesehighdegreenodes.Theonlywaywecanknowthenumberofsexualcontactsapersonhasisbyaskinghim/herdirectly.Cohenetal.[102]laterobservedthatinsteadoftryingto¯ndhighdegreenodes,onecantrytoreachanodethrougharandomlychosenedge(vaccinateafriendofarandomlychosenperson).Inthiswaytheprobabilityof¯ndinganodeofdegreekisproportionaltok.Thatis,ifpkistheprobabilitythatarandomlychosennodehasdegreek,thentheprobabilitythatanodereachedthrougharandomlychosenedgehasdegreekisproportionaltokpk[4,102].Wethereforehavehigherprobabilitiesofreachingnodesofhigherdegrees. 402.4.3SearchandinformationretrievalInformationorresourcesthatwerequiremayresideatspeci¯cnodesinanetwork.Theprocessesbywhichwehopfromonenodetoanotherviatheedgeslookingforspeci¯cinformationiscalledasearchprocess.Adamicetal.[23]andThadaka-mallaetal.[24,103]havestudieddecentralizedsearchprocessesinawiderangeofpower-law,weightedpower-lawandspatialscale-freenetworks.Adamicetal.[23]¯rstshowedthatspeci¯callysearchingthroughhighdegreenodesinpower-lawnetworksismoree±cientthanarandomwalksearch.Thistheyshowedanalyti-callyinnetworkswherethepower-lawexponent°liesbetween2and3.Laterin[24],Thadakamallaetal.proposedane±cientmethodtosearchnetworksthathaveheterogeneousdegreedistributionsandaheterogenousdistributionofweightsontheedges.Theyproposedalocalizedcentralitymeasurethatevaluatestheim-portanceofanodeusingbothitsdegreeandweightsontheedgesincidentonthenode.Bynavigatingthroughnodeswithhighcentralityvaluesthesearchprocessbecomesmoree±cient.Inanotherwork,Thadakamallaetal.[103]studiedsearchprocessesinspatialpower-lawnetworks.Theyshowedthattwoindicators,namelydegreeanddistanceofthenodefromthetarget,aresu±cienttoguidethesearchprocess.Inthiscase,theyshowedthatbycombiningthetwoindicatorsappropriatelyadecentralizedsearchmechanismcanbeformulatedthatwill¯ndthetarget,onanaverage,inthesmallestnumberofstepspossible.Thisresultaddsfurtherevidencetotheconjecturethatorganizationofnaturalcomplexnetworksencompassese±cientsearchandinformationretrieval[104,105].SearchenginesareusefultoolsthathelpininformationretrievalfromtheWWW.AlgorithmssuchasPageRankareusedtoretrievethewebpagesintheorderthatisexpectedtobeofrelevancetouserrequests.Thisalgorithmusesboththeindividualwebpage'svalueandthecumulativevalueattachedtothewebpagebyitsneighborsasanindicatoroftheoverallvalueofagivenwebpage[27].Klein-bergetal[28],proposedasimilarlinkbasedmechanismforretrievingwebpageswithrelevantinformation,butdosousingtwodi®erentsetsofvalues.Theyasso-ciatevaluestowebpagesthatdeterminesiftheyaregoodauthoritiesand/orgoodhubs.Agoodhubisawebpagethathashyperlinkstomanygoodauthoritiesandagoodauthoritarianwebpageisonethatisreferencedbymanygoodhubs.The 41bestsetofhubsandauthoritiesthencontaininformationthatisofmostrelevancetotheuser.Suchanapproach,accordingtoKleinberg,wasmotivatedbyalargepresenceofbi-partitesub-structuresobservedintheWWWnetwork.2.5ClusteredstructuresFindingandanalyzingclusteredstructuresinnaturalnetworkswillhelpustounderstandtheirstructuralorganizationbetter.Itisnowbecomingclearthatthereexistsmultipleandoverlappingclusteredstructuresinnaturalnetworksandestablishinghowtheyariseisaninterestingandunsolvedproblem[2].Further,developingnetworkmodelsthatcanmimicthispropertyofnaturalnetworkswillenableustostudytheprocessdynamicssuchasdiseasespreading,informationretrievalandstructuralresiliencebetter[106].Itiswiththismotivationthatwewillproceedtodiscussinchapter3ourproposedmethodforclusterdetectioninnaturalnetworks.2.6WirelesssensornetworksAdesiredpropertyofWSNsisconnectivity.Thatis,weideallywantanysen-sornodetobeabletocommunicatewithanyothersensornodeeitherdirectlyorthroughothernodesusingtheedges[7,6,35,34,107].Thisisourprimarygoal.However,therearetwoadditionalnecessities,namelypowerconservationandreducedinterferencethatshouldalsobetakencareofsimultaneously[6,35].Wethereforewantto¯ndthatspeci¯corganizationofcommunicationlinksbe-tweensensornodesthatwillensureconnectivityalongwithconservedpowerandreducedinterferences.InthefollowingdiscussionswewillmakeclearwhatthesetermsmeanandhowwewillachievealltherequirementsofaWSNtopologythroughstructuralorganization.Beforegettingintothedetails,wewillbeginwithabriefsummaryofwirelesssensornodesandtheircapabilities.Wewillthende¯nepowerconservationandinterferenceinWSNfollowedbyareviewofwirelesssensornetworkmodelsthatwillhelpusachieveanappropriatestructuralorganization.Figure2.8showsthebasiccomponentsofaminiaturizedsensornode.Itconsists 42Figure2.8.Thebasiccomponentsofsensornodeareasensingunit,processingunitandawirelesstransceiver.Thesethreeunitsrequirepowertoenabletheirtasksandthatisprovidedbythepowerunit.ofasensingunit(whichcanbe¯ttedwithavibrationsensororatemperaturesen-sororothers),aprocessingunitthatcanperformcertainlimitedtasks,awirelesstransceiverthatestablishescommunicationwithothersensornodes(totransmitandreceivedatapackets)andapowerunitthatisresponsibleforsupplyingpowertotheotherthreeunits[34].Advancesinmechanicalsystemsandelectronicshaveenabledthemanufacturingofminiaturizedsensorsthatcanbecomparedtothesizeofaquarter[35].Inadditionsensorscanbemadeavailableatcheappriceswhichisexpectedtoreducewellbelowonedollarpersensor[6,34].Beforeminiaturizedwirelesssensorswereavailable,traditionalsensorsthatwerelargerinsizewereusedtomonitorasensingregion.Asmallnumberofsuchsensorswerecarefullyplacedandtheircommunicationspre-engineeredtocollectdataonthephenomenonofinterest.Incaseswheninvasivemethodswerenotpossible(suchasmanningdangerousterrainsorlargechemicalplants)thesesensorswereplacedawayfromthesensingregionandsophisticatedmethodswereusedtodi®erentiatebetweenrandomnoiseandthesignalofinterest[34].Someofthetheadvantagesofminiaturizedsensorsovertraditionalsensingmethodsare²Numeroussmallsensorscanbeusedredundantlyinasensingregiontocon-tinuouslycollectdataat¯nerscalesandresolution[6,35,108].²Redundantuseofsensornodesalsoallowslong-termdatacollection[6,34].²Duetotheirsmallsizestheydonotinvadeoralterthenatureoftheenviron-mentaroundthem.Hencetheyareplacedintheregionofinterestallowing 43localizedmeasurementsanddetailedinformationtobeavailable[34,108].Duetosuchadvantagestherehasbeenaconsiderableamountofresearchinthelastfewyearsondevelopingprotocolsforself-organization,routingandfordatapre-processingandaggregation[7,6,35,34,107,109].2.6.1Powere±ciency,reducedinterferenceandconnectiv-ityOurfocusinthisthesisisontheself-organizationofwirelesssensornodes.Thatis,afterthesensornodesaredeployedinasensingregiontheirpowersareturnedONandtheyautonomouslybegintoestablishtheirlinksinthenetwork[6,35].Self-organizationbetweennodesisenabledbythemeansofTopologyControl(TC)protocols.TCisaprocessbywhichsensornodesadjusttheirtransmissionrangestoconservepowerandreduceinterferenceinthewirelessnetwork,whilestillmain-tainingcertainfundamentalproperties(connectivity)ofthenetwork[6,38].Miniaturizedsensornodesareusuallybatterypowered[6,34].Sinceprolongedlife-timesareimportant,poweratthesensornodesisrationedtoperformalltherequiredtasksoptimally.Transmissionofdatapacketfromonenodetoanotheristhemostenergyconsumingtaskofasensornode.Inspeci¯c,ifthetransmissionradiusisr,thentheenergyrequiredtotransmitmessageswiththisradiusisproportionaltor2[6].ThereforekeepingthetransmissionrangesatthenodessmallisoneoftheprimarygoalsofTC.Notethatanodecancommunicate(havelinks)withonlythoseothernodeswithinitstransmissionrange.SensornodesinaWSNuseasharedwirelesschanneltocommunicatewiththeirneighbors[6,38].Hence,ifanodextransmitsamessagetoanothernodeyatadistancedapart,itinterfereswithalltheothernodesthatarelessthanadistancedfromx(see¯gure2.9).Andbecausethenodessharethewirelesschannel,twoconcurrenttransmissions(sayfromxandytoz)willmostlikelycorrupteachother[6].From¯gure2.9wecanobservethefollowing.1.Supposexhastosendadatapackettoy.Thenforadirecttransmissiontheenergyrequiredisproportionaltod2.However,ifxtransmitstozandthen 44Figure2.9.Thecaseofsmallmultihopcommunicationsrequiredtoreducepowerconsumptionandinterferences.HeretheEuclidiandistancebetweenxandyisd,whilethedistancebetweenxandzandzandyared1andd2respectively.Sincethepowerrequiredtotransmittoanodeatadistancedisd2andbecauseofthetriangleinequalityd21+d22·d2.Thereforeitismorepowere±cientforxtotransmittoyviazinsmallerstepsthanonelongrangetransmission.Also,thetransmissionfromxdirectlytoyinterfereswithallthenodesinthecircleofradiusdfromx.Andhencehavingsmallnodedegreewillreducethisinterference.toy,whichareatdistancesd1andd2apartrespectively,theoverallenergyconsumedforthistransmissionisd2+d2·d2.Hencekeepingthetransmis-12sionrangeslowandusingmultiplesmallhopstotransmitdatapacketsleadstoabetterconservationofenergy.2.Againunderthesamescenario,whennodextransmitsdirectlytonodey,thistransmissionwillinterferewithalltheothernodesthatarewithinadistancedfromx.Hereagaintransmittingwithsmallrangesandinmultiplehopswillreducethedegreeandhenceinterferences.HencethegoalofTCismaintainmanyshortrangecommunicationsinsteadoflongrangedones.ButindoingsoaTCshouldalsoensuretheconnectivityofthenetwork.WewillevaluatetheWSNnetworkmodelsbasedontheabilitytoobtainopti-malenergye±cientandboundeddegreesonthenodes.Butbeforewebeginthisdiscussion,itisimportanttointroduceanotherfactor,namelythespatialdistri-butionofthesensornodes,thatmakethesenetworksdi®erentfromanyofthenetworksmodelsdiscussedinsection2.3. 452.6.2SpatialdistributionofsensornodesForsimplicitywewillconsiderthenodestobeembeddedinaregularregionSinthe2-dimensionalEuclidianspaceR2.GenerallyspeakingwewillassumethesensorsnodestobeuniformlyrandomlydistributedinS.MorerigorouslyweassumethesensornodesfollowaspatialPoissonpointprocess.LetAbeafamilyofsubsetsofS.ForA2A,letN(A)bethenumberofnodesinthesetAandjAjtheareaoftheregionA.ThenfN(A)gA2AisahomogeneousPoissonpointprocesswithintensity¸>0if,1.ForeachA2A,N(A)»Poisson(¸jAj).2.Andforany¯nitecollectionfA1;A2;:::;AngofdisjointsubsetsofS,N(A1);N(A2);:::;N(An)areindependent.assumingthatSisnormalizedtohaveanarea1[69].Itthenfollowsthat(¸jAj)k¡¸jAjP(N(A)=k)=ek!jBjFurther,ifB½A,thenP(N(B)=1=N(A)=1)=.Thatis,jAjTTN(B)=1P(N(B)=1;N(ABc)=1)¸jBje¡¸jBje¡¸jABcjjBjP()===N(A)=1P(N(A)=1)¸jAje¡¸jAjjAjThuswecanseethattheprobabilityforanodetolieinBgiventhatwealreadyknowthenodeisinAdependsonlyontheareajBjofB.Infact,itcanbeshownthatkjBjkjBjn¡kN(B)=N(A)=n»Cn()(1¡)jAjjAjandmoregenerallyforapartitionB1;B2;:::;BmofAandn=n1+n2+:::+nmn!jB1jn1jBmjnmP(N(B1)=n1;:::;N(Bm)=nm=N(A)=n)=():::()n1!n2!:::nm!jAjjAjTosimulateaspatialPoissonpatternwithintensity¸in,sayaunitsquare,wehavetodothefollowing,1.SimulateaPoisson(¸)numberofpoints 462.DistributethepointsuniformlyovertheunitsquareInallthenetworkmodelsofWNSsthatwewilldiscussbelowthenodesaredis-tributedaccordingtoaspatialPoissonprocessofintensity¸(alsocalledasthedensityofnodesinS)inasubsetSinR2.2.6.3ModelsofwirelesssensornetworksInlightoftherequirementsandconstraintsdescribedpreviously,wewillreviewmodelsforWSNs.Wewillspeci¯callyevaluatethefeasibilityof¯ndinganoptimalpowertransmissionrangeanddegreeonthenodesforthefollowingmodels.2.6.3.1PoissonBooleanmodelInthismodelthesensornodesareassumedtofollowaPoissonpointprocessXofintensity¸inthesensingregionSwhichisaregularandcontinuoussubsetofR2.EachpointofXisthecenterofaballofarandomradiussuchthattheradiicorrespondingtodi®erentpointsareindependentlyandidenticallydistributed.ThePoissonBooleanmodelisusuallydenotedas(X;½),where½istherandomvariablefortheradiionthepointsofX[69].Thismodelhasbeenwidelyusedinthemathematicsandphysicsliteraturetostudyvariouspropertiesincludingtheemergenceofgiantconnectedcomponents[69,110,111,112,113].Forthecasewhen½=ra.s(almostsurely),itwasshownthatthereexistsacriticalthreshold¸csuchthatthePoissonBooleanmodelhasagiantcomponentalmostsurelywhen¸¸¸c[69,111].Alternately,foragiven¸wecan¯ndarc(¸)suchthatforr¸rcthePoissonBooleanmodelalmostsurelyhasagiantcomponent[113,110,114].Whilethismodelwasinitiallyproposedtostudythespreadofforest¯res,itwaslateradoptedtodepictaWSN.InthecaseofWSNstheradiusonthenodescanbeassumedtodepictthetransmissionrangeofasensornode.Henceagivennodexwithradiusrxhasdirectededgespointingtowardsalltheothernodesthatarewithinadistancerxfromit.Whenradiiofallnodesareidentical(½=ra.s.),theneverypairofnodeseitherhasatwo-waycommunicationornocommunicationatall. 472.6.3.2PoissonrandomconnectionmodelSimilartothePoissonBooleanmodel,therandomconnectionmodelisalsodrivenbyaPoissonpointprocessX.However,unliketheBooleancase,here,theexistenceofedgesbetweennodesisdeterminedbyanon-increasingfunctiongfromthesetofpositiverealsto[0,1].Thusgivenanypairofpointsxandy,theexistenceofan(undirected)edgeisdeterminedwithprobabilityg(kx¡yk),independentofotherpairs.k¢kherestandsfortheEuclideanmetric.APoissonrandomconnectionmodelisusuallydenotedas(X;g).Ithasbeenshownthatthereexist¯nitecriticalthresholds¸c(g)thatdependong,fortheappearanceofgiantcomponentsinthenetworks[69].ThePoissonBooleanmodelwith¯xedradiusisaspecialcaseoftherandomconnectionmodelbychoosinggasfollows,8<1;8kxk·rg(x)=:0;8kxk>r2.6.3.3Nearestk-neighborsmodelOneofthemajordrawbacksofeitherthePoissonBooleanmodelorthePoissonrandomconnectionmodelisthatitisnotpossibletorestrictthedegreesonthenodes.Forexample,inaPoissonBooleanmodelwhen½=ra.s.forsome¯xedr,thedegreesonthenodesinthenetworkfollowaPoissondistributionwithparameter=r2¼¸[113].Therefore,whilemostnodesinthenetworkhaveadegreeclosetothemeantheremightexistnodeswhosedegreesaremuchhigherthan.Thereforewecannot¯ndanon-trivialupperboundonthenodedegreeinthenetwork.Ontheotherhandconsiderthefollowingmodel.Supposeagainthatthesen-sornodesaredistributedaccordingtoaPoissonpointprocessinaunitsquare.Then,fora¯xednon-negativeintegerk,supposethateverynodeadjustsitstrans-missionrangetoaccommodateexactlytheirkclosestneighbors[38,58].Wecallthisthenearestk-neighborsmodel.Hereagainwecanstudyhowtheconnectedcomponentsofthenetworkchangesforincreasingvaluesofkbutkeepastrictupper-boundonthenodedegrees.Infact,ifweknowtheupperboundkforthedegreeonthenodes,thenitispossibletoobtainupperboundsontheinterference 48intheoverallnetwork.FurtherifkisaconstantandindependentofN,thentheinterferencesinthenetworkisalsoboundedabovebyaconstantf(k)(afunctionofk)andisindependentofN[38].Inthek-neighborsmodel,weassumeeverynodetohaveedgesdirectedtowardsthekclosestneighbors.However,tostudytheconnectivityofthethisnetworkmodelwedothefollowing,²Replacetwowayconnectionsbetweennodesbyonesingleundirectededge.²Ifthereisonlyaonewayconnectionbetweentwonodes,thenwesimplyremovethislinkfromthenetwork.Wewillderivetheoptimalkforconnectivity(giantcomponent)onthisprunednetworkandshowthatitisindeedaconstantwhichisindependentofN.2.7SummaryInthischapterwehavediscussedthoroughlyontheclusteringandconnectivityproblemsincomplexnetworks.Inthe¯rsthalfofthischapterweshowedthroughourdiscussionsthatnaturalcomplexnetworkshavedistinctfeaturesandproperties.Wesawthattheseprop-ertiescanthrowlightonorganizingprinciplespresentintheunderlyingnetwork(forexample,weneedbothgrowthandapreferentialattachmentmechanismtoobtainpower-lawnetworksandpresenceoffewlongrange/randomconnectionsinhighlyorderedlatticescanyieldsmall-worldbehaviorandsoon).Moreimpor-tantlyperformanceofprocessessuchaserrorandattacktolerance,informationdi®usion,search,navigationandinformationretrievalarea®ectedbytheseprop-ertiesofcomplexnetworks.Clusteredstructureswhichisacommonlyobservedpropertyinmanynaturalcomplexnetworkshasreceivedwidespreadattentionintherecentyears.Inthisthesiswewillconcentrateontheproblemofclusterdetectionincomplexnetworksanditsimplicationsonnetworkorganization.InthesecondhalfofthischapterwediscussedtheproblemofconnectivityinWSNs.Whilecreatingmoreandmorelinksinanetworkcanyieldconnectivity,thiscreationoflinksislimited.Inspeci¯c,wesawthattwoconstraintslimitedpowerandreducedinterferencecurbthecreationoflinks.Thereforetheproblem 49ofconnectivityreducesto¯ndinganoptimalmid-waythatensurestheuseofaslesslinksaspossiblewhilestillmaintainingtheconnectivityoftheWSNs. Chapter3FindingclusteredstructuresinnaturalcomplexnetworksClusterdetectionissimilartothewellstudiednetworkpartitioningproblems[115,116,117].Thenetworkpartitioningproblemisingeneralde¯nedasthepartitioningofanetworkintoc(a¯xedconstant)groupsofapproximatelyequalsizes,minimizingthenumberofedgesbetweengroups.ThisproblemisNP-hardande±cientheuristicmethodshavebeendevelopedoveryearstosolvetheprob-lem[117,118,115,116,119].Muchofthisworkismotivatedbyengineeringapplicationsincludingverylargescaleintegrated(VLSI)circuitlayoutdesignandmappingofparallelcomputations.Thompson[120]showedthatoneoftheim-portantfactorsa®ectingtheminimumlayoutareaofagivencircuitinachipisitsbisectionwidth.Also,toenhancetheperformanceofacomputationalalgo-rithm,wherenodesrepresentcomputationsandedgesrepresentcommunications,thenodesaredividedequallyamongtheprocessorssothatthecommunicationsbetweenthemareminimized.Thegoalofanetworkpartitioningalgorithmistodivideanygivennetworkintoapproximatelyequalsizegroupsirrespectiveofnodesimilarities.Communitydetectionontheotherhand¯ndsgroupsthateitherhaveaninherentoranex-ternallyspeci¯ednotionofsimilarityamongnodeswithingroups.Furthermore,thenumberofclustersinanetworkandtheirsizesarenotknownbeforehandandtheyareestablishedbytheclusterdetectionalgorithm.Manyalgorithmshavebeenproposedto¯ndclusteredstructuresinnetworks. 51Hierarchicalmethodsdividenetworksintoclusters,successively,basedonadis-similaritymeasure,leadingtoaseriesofpartitionsfromtheentirenetworktosingletonclusters[40,48].Similarlyonecanalsosuccessivelygrouptogethersmallerclustersbasedonasimilaritymeasureleadingagaintoaseriesofpartitions[66,121].Duetothewiderangeofpartitions,structuralindicesthatmeasurethestrengthofclusteredstructuresareusedindeterminingthemostrelevantones.Simulationbasedmethodsarealsooftenusedto¯ndpartitionswithastrongclusteredstructure[122,41].Spectral[116,123]and°owmaximization(cutmini-mization)methods[44,124]havebeensuccessfullyusedindividingnetworksintotwoormoreclusters.Inthisthesis,weproposealocalizedclusterdetectionalgorithmbasedonlabelpropagation.Eachnodeisinitializedwithauniquelabelandateveryiterationofthealgorithm,eachnodeadoptsalabelthatamaximumnumberofitsneighborshave,withtiesbrokenuniformlyrandomly.Asthelabelspropagatethroughthenetworkinthismanner,denselyconnectedgroupsofnodesformaconsensusontheirlabels.Attheendofthealgorithm,nodeshavingthesamelabelsaregroupedtogetherasclusters.Aswewillshow,theadvantageofthisalgorithmovertheothermethodsisitssimplicityandtimee±ciency.Thealgorithmusesthenetworkstructuretoguideitsprogressanddoesnotoptimizeanyspeci¯cchosenmeasureofclusterstrengths.Furthermore,thenumberofclustersandtheirsizesarenotknownaprioriandaredeterminedattheendofthealgorithm.Wewillshowthattheclusteredstructuresobtainedbyapplyingthealgorithmonpreviouslyconsiderednetworks,suchasZachary'skarateclubfriendshipnetworkandtheUScollegefootballnetwork,areinagreementwiththeactualclusterspresentinthesenetworks.3.1De¯nitionsandpreviousworkAsmentionedearlier,thereisnouniquede¯nitionofacluster.Oneofthesimplestde¯nitionsofaclusterisaclique,thatis,agroupofnodeswherethereisanedgebetweeneverypairofnodes.Cliquescapturetheintuitivenotionofacluster[3]whereeverynodeisrelatedtoeveryothernodeandhencehavestrongsimilaritieswitheachother.Anextensionofthisde¯nitionwasusedbyPallaetalin[2],who 52de¯neaclusterasachainofadjacentcliques.Theyde¯netwok-cliques(cliquesonknodes)tobeadjacentiftheysharek¡1nodes.Thesede¯nitionsarestrictinthesensethattheabsenceofevenoneedgeimpliesthataclique(andhencethecluster)nolongerexists.k-clansandk-clubsareamorerelaxedde¯nitionswhilestillmaintainingahighdensityofedgeswithinclusters[2].Agroupofnodesissaidtoformak-claniftheshortestpathlengthbetweenanypairofnodes,orthediameterofthegroup,isatmostk.Heretheshortestpathonlyusesthenodeswithinthegroup.Ak-clubisde¯nedsimilarly,exceptthatthesubnetworkinducedbythegroupofnodesisamaximalsubgraphofdiameterkinthenetwork.De¯nitionsbasedondegrees(numberofedges)ofnodeswithinthegrouprel-ativetotheirdegreesoutsidethegroupweregivenbyRadicchietal[48].IfdinianddoutarethedegreesofnodeiwithinandoutsideofitsgroupU,thenUissaidiPPtoformastrongclusterifdin>dout;8i2U.Ifdin>dout,thenUiii2Uii2Uiisaclusterintheweaksense.Otherde¯nitionsbasedondegreesofnodescanbefoundin[3].Therecanexistmanydi®erentpartitionsofnodesinthenetworkthatsatisfyagivende¯nitionofcluster.Inmostcases[125,126,4,66,124],thegroupsofnodesfoundbyaclusterdetectionalgorithmareassumedtobeclustersirrespectiveofwhethertheysatisfyaspeci¯cde¯nitionornot.To¯ndthebestclusteredstructuresamongthemweneedameasurethatcanquantifythestrengthofaclusterobtained.Oneofthewaystomeasurethestrengthofaclusterisbycomparingthedensityofedgesobservedwithintheclusterwiththedensityofedgesinthenetworkasawhole[3].IfthenumberofedgesobservedwithinaclusterUiseU,thenundertheassumptionthattheedgesinthenetworkareuniformlydistributedamongpairsofnodes,wecancalculatetheprobabilityPthattheexpectednumberofedgeswithinUislargerthaneU.IfPissmall,thentheobserveddensityintheclusterisgreaterthantheexpectedvalue.Asimilarde¯nitionwasrecentlyadoptedbyNewman[47],wherethecomparisonisbetweentheobserveddensityofedgeswithinclustersandtheexpecteddensityofedgeswithinthesameclustersinrandomizednetworksthatneverthelessmaintaineverynode'sdegree.ThiswastermedthemodularitymeasureQ,whereQ=P(e¡a2);8i.eistheobservedfractionofedgeswithingroupianda2istheiiiiiiiexpectedfractionofedgeswithinthesamegroupi.Notethatifeijisthefraction 53Figure3.1.Anillustrationofadendrogramwhichisatreerepresentationoftheorderinwhichnodesaresegregatedintodi®erentgroupsorclusters.Pofedgesinthenetworkthatrunbetweengroupiandgroupj,thenai=jeij.Q=0impliesthatthedensityofedgeswithingroupsinagivenpartitionisnomorethanwhatwouldbeexpectedbyarandomchance.Qcloserto1indicatesstrongerclusteredstructures.GivenanetworkwithNnodesandMedgesG(N;M),anyclusterdetectionalgorithm¯ndssubgroupsofnodes.LetC1;C2;:::;Cpbetheclustersfound.Inmostalgorithms,theclustersfoundsatisfythefollowingconstraints1.CiCj=;fori6=jandS2.iCispansthenodesetinGAnotableexceptionisPallaetal[2]whode¯neclustersasachainofadjacentk-cliquesandallowclusteroverlaps.Ittakesexponentialtimeto¯ndallsuchclustersinthenetwork.Theyusethesesetstostudytheoverlappingstructureofclustersinsocialandbiologicalnetworks.Byforminganothernetworkwhereaclusterisrepresentedbyanodeandedgesbetweennodesindicatethepresenceofoverlap,theyshowthatsuchnetworksarealsoheterogeneous(fat-tailed)intheirnodedegreedistributions.Furthermore,ifaclusterhasoverlappingregionswithtwootherclusters,thentheneighboringclustersarealsohighlylikelytooverlap.Thenumberofdi®erentpartitionsofanetworkG(N;M)intojusttwodisjointsubsetsis2NandincreasesexponentiallywithN.Henceweneedaquickwayto¯ndonlyrelevantpartitions.GirvanandNewman[40]proposedadivisivealgo-rithmbasedontheconceptofedgebetweennesscentrality,thatis,thenumber 54ofshortestpathsamongallpairsofnodesinthenetworkpassingthroughthatedge.Themainideahereisthatedgesthatrunbetweenclustershavehighbe-tweennessvaluesthanthosethatliewithinclusters.Bysuccessivelyrecalculatingandremovingedgeswithhighestbetweennessvalues,thenetworkbreaksdownintodisjointconnectedcomponents.Thealgorithmcontinuesuntilalledgesareremovedfromthenetwork.EachstepofthealgorithmtakesO(mn)timeandsincethereareMedgestoberemoved,theworstcaserunningtimeisO(M2N).Asthealgorithmproceedsonecanconstructadendrogram(see¯gure3.1)depictingthebreakingdownofthenetworkintodisjointconnectedcomponents.Henceforanygivenhsuchthat1·h·N,atmostonepartitionofthenetworkintohdisjointsubgroupsisfound.Allsuchpartitionsinthedendrogramaredepicted,irrespectiveofwhetherornotthesubgroupsineachpartitionrepresentacluster.Radicchietal[48]proposeanotherdivisivealgorithmwherethedendrogramsaremodi¯edtore°ectonlythosegroupsthatsatisfyaspeci¯cde¯nitionofacluster.Further,insteadofedgebetweennesscentrality,theyusealocalmeasurecallededgelocalordercoe±cientasacriterionforremovingedges.Theedgelocalordercoe±cientisde¯nedasthefractionofnumberoftrianglesagivenedgeparticipatesin,tothetotalnumberofpossiblesuchtriangles.Thelocalordercoe±cientofanedgeisexpectedtobetheleastforthoserunningbetweenclustersandhencethealgorithmproceedsbyremovingedgeswithlowlocalordercoe±cients.ThetotalM4runningtimeofthisdivisivealgorithmisO(2).NSimilarlyonecanalsode¯neatopologicalsimilaritybetweennodesandper-formagglomerativehierarchicalclustering[68,121].Inthiscase,webeginwithnodesinNdi®erentclustersandgrouptogetherclustersthatarethemostsim-ilar.Newman[66]proposedanamalgamationmethod(similartoagglomerativemethods)usingthemodularitymeasureQ,whereateachstepthosetwoclustersaregroupedtogetherthatgiverisetothemaximumincreaseorsmallestdecreaseinQ.Thisprocesscanalsoberepresentedasadendrogramandonecancutacrossthedendrogramto¯ndthepartitioncorrespondingtothemaximumvalueofQ(see¯gure3.1).AteachstepofthealgorithmonecomparesatmostMpairsofgroupsandrequiresatmostO(N)timetoupdatetheQvalue.ThealgorithmcontinuesuntilalltheNnodesareinonegroupandhencetheworstcaserunningtimeofthealgorithmisO(N(M+N)).ThealgorithmofClausetetal[49]isan 55adaptationofthisagglomerativehierarchicalmethod,butusesacleverdatastruc-turetostoreandretrieveinformationrequiredtoupdateQ.Ine®ect,theyreducethetimecomplexityofthealgorithmtoO(mdlogN),wheredisthedepthofthedendrogramobtained.Innetworksthathaveahierarchicalstructurewithclustersatmanyscales,d»logN.Therehavealsobeenotherheuristicandsimulationbasedmethodsthat¯ndpartitionsofagivennetworkmaximizingthemodularitymeasureQ[122,41].Label°oodingalgorithmshavealsobeenusedindetectingclustersinnetworks[125,126].In[125],theauthorsproposealocalclusterdetectionmethodwhereanodeisinitializedwithalabelwhichthenpropagatesstepbystepviatheneighborsuntilitreachestheendofthecluster,wherethenumberofedgesproceedingoutwardfromtheclusterdropsbelowathresholdvalue.After¯ndingthelocalclustersatallnodesinthenetwork,anN£Nmatrixisformed,wheretheijthentryis1ifnodejbelongstotheclusterstartedfromiand0otherwise.Therowsofthematrixarethenrearrangedsuchthatthesimilaronesareclosertoeachother.Then,startingfromthe¯rstrowtheysuccessivelyincludealltherowsintoaclusteruntilthedistancebetweentwosuccessiverowsislargeandaboveathresholdvalue.Afterthisanewclusterisformedandtheprocessiscontinued.FormingtherowsofthematrixandrearrangingthemrequiresO(N3)timeandhencethealgorithmistime-consuming.WuandHuberman[124]proposealineartime(O(M+N))algorithmthatcandivideagivennetworkintotwoclusters.Supposethatonecan¯ndtwonodes(xandy)thatbelongtotwodi®erentclusters,thentheyareinitializedwithvalues1and0respectively.Allothernodesareinitializedwithvalue0.Thenateachstepofthealgorithm,allnodes(exceptxandy)updatetheirvaluesasfollows.Ifz1;z2;:::;zkareneighborsofanodez,thenitsvalueVzisupdatedVz+Vz+:::+Vzas12k.Thisprocesscontinuesuntilconvergence.Theauthorsshowkthattheiterativeprocedureconvergestoauniquevalue,andtheconvergenceofthealgorithmdoesnotdependonthesizeNofthenetwork.Oncetherequiredconvergenceisobtained,thevaluesaresortedbetween0and1.Goingthroughthespectrumofvaluesindescendingorder,therewillbeasuddendropattheborderoftwoclusters.Thisgapisusedinidentifyingthetwoclustersinthenetwork.AsimilarapproachwasusedbyFlakeetal[44]to¯ndtheclustersin 56theWWWnetwork.Here,givenasmallsetofnodes(sourcenodes),theyformanetworkofwebpagesthatarewithinaboundeddistancefromthesources.Thenbydesignating(orarti¯ciallyintroducing)sinknodes,theysolveforthemaximum°owfromthesourcestothesinks.Indoingsoonecanthen¯ndtheminimumcutcorrespondingtothemaximum°ow.Theconnectedcomponentofthenetworkcontainingthesourcenodesaftertheremovalofthecutsetisthentherequiredcluster.Spectralbisectionmethods[123]havebeenusedextensivelytodivideanetworkintotwogroupssothatthenumberofedgesbetweengroupsisminimized.Eigen-vectorsoftheLaplacianmatrix(L)ofagivennetworkareusedinthebisectionprocess.LisanN£Nmatrixwhereanijthentryiseither¡1or0dependingonwhetherornotthereexistsanedgebetweennodeiandnodejrespectivelyfori6=jandwheni=jtheentryisthedegreeofnodei.ItcanbeshownthatLhasonlyrealnon-negativeeigenvalues(0·¸1·¸2·:::·¸N)andminimiz-ingthenumberofedgesbetweengroupsisthesameasminimizingthepositivePlinearcombinationM=s2¸,wheres=uTzanduistheeigenvectorofLiiiiiicorrespondingto¸.zisthedecisionvectorwhoseithentrycanbeeither1or-1idenotingwhichofthetwogroupsnodeibelongsto.TominimizeM,zischosenasparallelaspossibletotheeigenvectorcorrespondingtothesecondsmallesteigen-value(Thesmallesteigenvalueis0andchoosingzparalleltothecorrespondingeigenvectorgivesatrivialsolution).Thisbisectionmethodhasbeenextendedto¯ndingclustersinnetworksthatmaximizethemodularitymeasureQ[123].QcanbewrittenasapositivelinearcombinationofeigenvaluesofthematrixB,whereBisde¯nedasthedi®erenceoftwomatricesAandP.AijistheobservednumberofedgesbetweennodesiandjandPijistheexpectednumberofedgesbetweeniandjiftheedgesfallrandomlybetweennodes,whilemaintainingthedegreeofeachnode.SinceQhastobemaximized,zischosenasparallelaspossibletotheeigenvectorcorrespondingtothelargesteigenvalue.Sincemanynaturalcomplexnetworksarelargeinsize,thetimee±ciencyoftheclusterdetectionalgorithmisanimportantconsideration.Whennoaprioriinfor-mationisavailableaboutthelikelyclustersinagivennetworktheaimnormallyisto¯ndpartitionsthatoptimizeachosenmeasureofclusterstrength.Ourgoalistodevelopasimpletime-e±cientalgorithmthatrequiresnopriorinformation 57Figure3.2.Nodesareupdatedonebyoneaswemovefromlefttoright.Duetoahighdensityofedges(highestpossibleinthiscase),allnodesacquirethesamelabel.(suchasnumber,sizesorcentralnodesoftheclusters)andusesonlythenetworkstructuretoguidetheclusterdetection.Theproposedmechanismforsuchanalgorithmwhichdoesnotoptimizeanyspeci¯cmeasureorfunctionisdetailedinthefollowingsection.3.2Communitydetectionusinglabelpropaga-tionThemainideabehindourlabelpropagationalgorithmisthefollowing.Supposethatanodexhasneighborsx1;x2;:::;xkandthateachneighborcarriesalabeldenotingtheclustertowhichtheybelongto.Thenxdeterminesitsclusterbasedonthelabelsofitsneighbors.Weassumethateachnodeinthenetworkchoosestojointheclustertowhichthemaximumnumberofitsneighborsbelongto,withtiesbrokenuniformlyrandomly.Weinitializeeverynodewithuniquelabelsandletthelabelspropagatethroughthenetwork.Asthelabelspropagate,denselyconnectedgroupsofnodesquicklyreachaconsensusonauniquelabel(see¯gure3.2).Whenmanysuchdense(consensus)groupsarecreatedthroughoutthenetwork,theycontinuetoexpandoutwardsaslongasitispossibletodoso.Attheendofthepropagationprocess,nodeshavingthesamelabelsaregroupedtogetherasonecluster.Weperformthisprocessiteratively,whereateverystep,eachnodeupdatesitslabelbasedonthelabelsofitsneighbors.Theupdatingprocesscaneitherbesynchronousorasynchronous.Insynchronousupdating,nodexatthetthiterationupdatesitslabelbasedonthelabelsofitsneighborsatiterationt¡1.Hence,Cx(t)=f(Cx1(t¡1);:::;Cxk(t¡1)),wherecx(t)isthelabelofnodexattimet. 58Figure3.3.Anexampleofabi-partitenetworkinwhichthelabelsetsofthetwopartsaredisjoint.Inthiscase,duetothechoicesmadebythenodesatstept,thelabelsonthenodesoscillatebetweenaandb.Theproblemhoweveristhatsubgraphsinthenetworkthatarebi-partiteornearlybi-partiteinstructureleadtooscillationsoflabels(see¯gure3.3).Thisisespe-ciallytrueincaseswhereclusterstaketheformofastargraph.Henceweuseasyn-chronousupdatingwhereCx(t)=f(Cxi1(t);:::;Cxiq(t);Cxi(q+1)(t¡1);:::;Cxik(t¡1))andxi1;:::;xiqareneighborsofxthathavealreadybeenupdatedinthecurrentiterationwhilexi(q+1);:::;xikareneighborsthatarenotyetupdatedinthecurrentiteration.TheorderinwhichalltheNnodesinthenetworkareupdatedateachiterationischosenrandomly.NotethatwhilewehaveNdi®erentlabelsatthebeginningofthealgorithm,thenumberoflabelsreducesoveriterations,resultinginonlyasmanyuniquelabelsasthereareclusters.Ideallytheiterativeprocessshouldcontinueuntilnonodeinthenetworkchangesitslabel.However,therecouldbenodesinthenetworkthathaveanequalmaximumnumberofneighborsintwoormoreclusters.Sincewebreaktiesrandomlyamongthepossiblecandidates,thelabelsonsuchnodescouldchangeoveriterationsevenifthelabelsoftheirneighborsremainconstant.Henceweper-formtheiterativeprocessuntileverynodeinthenetworkhasalabeltowhichthemaximumnumberofitsneighborsbelongto.Bydoingsoweobtainapartitionofthenetworkintodisjointclusters,whereeverynodehasatleastasmanyneighborswithinitsclusterasithaswithanyothercluster.IfC1;:::;CparethelabelsthatCjarecurrentlyactiveinthenetworkanddiisthenumberofneighborsnodeihaswithnodesoflabelCj,thenthealgorithmisstoppedwhenforeverynodei,CqCjIfihaslabelCqthendi¸di8jAttheendoftheiterativeprocessnodeswiththesamelabelaregroupedtogether 59asclusters.Ourstoppingcriterioncharacterizingtheclustersobtainedissimilar(butnotidentical)tothede¯nitionofstrongclustersproposedbyRadicchietal[48].Whilestrongclustersrequireeachnodetohavestrictlymoreneighborswithinitsclusterthanoutside,theclustersobtainedbythelabelpropagationprocessrequireeachnodetohaveatleastasmanyneighborswithinitsclusterasithaswitheachoftheotherclusters.Wecandescribeourproposedlabelpropagationalgorithminthefollowingsteps.1.Initializethelabelsatallnodesinthenetwork.Foragivennodex,Cx(0)=x.2.Sett=1.3.ArrangethenodesinthenetworkinarandomorderandsetittoX.4.Foreachx2Xchoseninthatspeci¯corder,letCx(t)=f(Cxi1(t);:::;Cxiq(t);Cxi(q+1)(t¡1);:::;Cxik(t¡1))fherereturnsthelabeloccurringwiththehighestfrequencyamongneigh-borsandtiesarebrokenuniformlyrandomly.5.Ifeverynodehasalabelthatthemaximumnumberoftheirneighborshave,thenstopthealgorithm.Else,sett=t+1andgoto(3).Sincewebeginthealgorithmwitheachnodecarryingauniquelabel,the¯rstfewiterationsresultinvarioussmallpockets(denseregions)ofnodesformingaconsen-sus(acquiringthesamelabel).Theseconsensusgroupsthengainmomentumandtrytoacquiremorenodestostrengthenthegroup.However,whenaconsensusgroupreachestheborderofanotherconsensusgroup,theystarttocompeteformembers.Thewithin-groupinteractionsofthenodescancounteractthepressuresfromoutsideiftherearelessbetween-groupedgesthanwithin-groupedges.Thealgorithmconverges,andthe¯nalclustersareidenti¯ed,whenaglobalconsensusamonggroupsisreached.Notethateventhoughthenetworkasonesingleclustersatis¯esthestopcriterion,thisprocessofgroupformationandcompetitiondis-couragesallnodesfromacquiringthesamelabelincaseofheterogeneousnetworks 60Figure3.4.(a);(b)and(c)arethreedi®erentclusteredstructuresidenti¯edbythealgorithmonZachary'skarateclubnetwork.Theclusterscanbeidenti¯edbytheirshadesofgreycolors.withanunderlyingclusteredstructure.IncaseofhomogeneousnetworkssuchasErd}os-R¶enyirandomgraphs[1]thatdonothaveclusteredstructures,thelabelpropagationalgorithmidenti¯esthegiantconnectedcomponentofthesegraphsasasinglecluster.Ourstopcriterionisonlyaconditionandnotameasurethatisbeingmaximizedorminimized.Consequentlythereisnouniquesolutionandmorethanonedistinctpartitionofanetworkintogroupssatis¯esthestopcriterion(see¯gures3.4and 61Figure3.5.ThegroupingofUScollegefootballteamsintoconferencesareshownin(a)and(b).Eachsolution((a)and(b))isanaggregateof¯vedi®erentsolutionsobtainedbyapplyingthealgorithmonthecollegefootballnetwork.3.5).Sincethealgorithmbreakstiesuniformlyrandomly,earlyonintheiterativeprocesswhenpossibilitiesoftiesarehigh,anodemayvoteinfavorofarandomlychosencluster.Asaresult,multipleclusteredstructuresarereachablefromthesameinitialcondition.Ifweknowthesetofnodesinthenetworkthatarelikelytoactascentersofattractionfortheirrespectiveclusters,thenitwouldbesu±cienttoinitializesuchnodeswithuniquelabels,leavingtheremainingnodesunlabeled.Inthiscasewhenweapplytheproposedalgorithmtheunlabelednodeswillhaveatendencytoacquirelabelsfromtheirclosestattractorandjointhatcluster.Also,restrictingthesetofnodesinitializedwithlabelswillreducetherangeofpossiblesolutionsthatthealgorithmcanproduce.Sinceitisgenerallydi±culttoidentifynodesthatarecentraltoaclusterbeforeidentifyingtheclusteritself,herewegiveallnodesequalimportanceatthebeginningofthealgorithmandprovidethemeachwithuniquelabels.Weapplyouralgorithmtothefollowingnetworks.The¯rstoneisZachary'skarateclubnetworkwhichisanetworkoffriendshipamong34membersofakarate 62club[67].Overaperiodoftimetheclubsplitintotwofactionsduetoleadershipissuesandeachmemberjoinedoneofthetwofactions.ThesecondnetworkthatweconsideristheUScollegefootballnetworkthatconsistsof115collegeteamsrepresentedasnodesandhasedgesbetweenteamsthatplayedeachotherduringtheregularseasonintheyear2000[40].Theteamsaredividedintoconferences(clusters)andeachteamplaysmoregameswithinitsownconferencethaninter-conferencegames.Nextistheco-authorshipnetworkof16726scientistswhohavepostedpreprintsonthecondensedmatterarchiveatwww.arxiv.org;theedgesconnectscientistswhoco-authoredapaper[14].Ithasbeenshownthatclustersinco-authorshipnetworksaremadeupbyresearchersworkinginthesame¯eldorareresearchgroups[66].Alongsimilarlinesonecanexpectanactorcollaborationnetworktohaveclusterscontainingactorsofasimilargenre.Hereweconsideranactorcollaborationnetworkof374511nodesandedgesrunningbetweenactorswhohaveactedinatleastonemovietogether[79].Wealsoconsideraprotein-proteininteractionnetwork[29]consistingof2115nodes.Theclustersarelikelytore°ectfunctionalgroupingsofthisnetwork.And¯nallyweconsiderasubsetoftheworldwideweb(WWW)consistingof325729webpageswithinthend.edudomainandhyperlinksinterconnectingthem[9].Communitieshereareexpectedtobegroupsofpagesonsimilartopics.3.2.1MultipleclusteredstructuresFigure3.4showsthreedi®erentsolutionsobtainedfortheZachary'skarateclubnetworkand¯gure3.5showstwodi®erentsolutionsobtainedfortheUScollegefootballnetwork.Wewillshowthateventhoughweobtaindi®erentsolutions(clusteredstructure),theyaresimilartoeachother.To¯ndthepercentageofnodesclassi¯edinthesamegroupintwodi®erentsolutions,weformamatrixM,whereMijisthenumberofnodescommontoclusteriinonesolutionandPclusterjintheothersolution.Thenwecalculatef=1(maxfMg+same2ijijPmaxfMg)100.Givenanetworkwhoseclustersarealreadyknown,aclusterjiijNdetectionalgorithmiscommonlyevaluatedbasedonthepercentage(ornumber)ofnodesthataregroupedintothecorrectclusters[66,124].fsameissimilar,whereby¯xingonesolutionweevaluatehowclosetheothersolutionistothe¯xedone 63andviceversa.Whilefsamecanidentifyhowcloseonesolutionistoanother,itishowevernotsensitivetotheseriousnessoferrors.Forexample,whenfewnodesfromseveraldi®erentclustersinonesolutionarefusedtogetherasasingleclusterinanothersolution,thevalueoffsamedoesnotchangemuch.HencewealsouseJaccard'sindexwhichhasbeenshowntobemoresensitivetosuchdi®erencesbetweensolutions[127].Ifastandsforthepairsofnodesthatareclassi¯edinthesameclusterinbothsolutions,bforpairsofnodesthatareinthesameclusterinthe¯rstsolutionanddi®erentinthesecondandcvice-versa,thenJaccard'sindexisde¯nedasa.Ittakesvaluesbetween0and1,withhighervaluesindicatinga+b+cstrongersimilaritybetweenthetwosolutions.Figure3.6showsthesimilaritiesbetweensolutionsobtainedfromapplyingthealgorithm¯vedi®erenttimesonthesamenetwork.Foragivennetwork,theijthentryinthelowertriangleofthetableistheJaccardindexforsolutionsiandj,whiletheijthentryintheuppertriangleisthemeasurefsameforsolutionsiandj.Wecanseethatthesolutionsobtainedfromthe¯vedi®erentrunsaresimilar,implyingthattheproposedlabelpropagationalgorithmcane®ectivelyidentifytheclusteredstructureofanygivennetwork.Moreover,thetightrangeandhighvaluesofthemodularitymeasureQobtainedforthe¯vesolutions(¯gure3.6)suggestthatthepartitionsdenotesigni¯cantclusteredstructures.3.2.2RobustnessofthesolutionsAswecanseethelabelpropagationalgorithmidenti¯esmultipleclusteredstruc-turesinnetworks.Further,highvaluesofthemodularitymeasureQ,forallso-lutionsobtained,indicatesthatthealgorithmdoesindeed¯nddenselyconnectedgroupsofnodesinthenetwork.Ithashoweverbeenarguedthatthesigni¯canceofanyidenti¯edclusterisnotjustinthedensityofedgeswithinthecluster,butitsrobustnesstosmallperturbations[128].Inthissectionweshowhowtheclusteredstructureidenti¯edbythealgorithmweatherstheperturbationstonetworks.Givenaprobability®,weperturbanetworkasfollows.²Eachedgeinthenetworkisremovedwithaprobability®.²Ifremoved,theedgeisreplacedbackinthenetwork,butnowconnecting 64Figure3.6.Similaritiesbetween¯vedi®erentsolutionsobtainedforeachnetworkistabulated.AnentryintheithrowandjthcolumninthelowertriangleofeachofthetableistheJaccard'ssimilarityindexforsolutionsiandjofthecorrespondingnetwork.Entriesintheithrowandjthcolumnintheupper-triangleofthetablesarethevaluesofthemeasurefsameforsolutionsiandjintherespectivenetworks.TherangeofmodularityvaluesQobtainedforthe¯vedi®erentsolutionsisalsogivenforeachnetwork.tworandomlychosennodes.ThenumberofnodesNandthenumberofedgesMwillremainthesame,exceptthatsomeedgeswillberewired.Ifaclusteridenti¯edbythealgorithmisindeedsigni¯cantlydenselyconnected,thenitwillcontinuetoremainsoundersmallperturbations.Givenanetwork,we¯rstapplythelabelpropagationalgorithmandobtainasolution.Letuscallthisasthebasesolution.Wethenperturbthenetworkforsome®.Keepingthesamelabelsonthenodesasinthebasesolution,were-apply 65Figure3.7.Thegraphshowshowsimilartheperturbedsolutionsarewithrespecttothebasesolutionforprotein-proteininteractionnetwork(diamond),co-authorshipnetwork(square)andtheWWW(triangle).Eachdatapointistheaverageofsimilaritiesbetweenthe5perturbedsolutionsandtheirrespectivebasesolutions.thealgorithmtoobtainaperturbedsolutionfromtheperturbednetwork.Notethatwhenapplyingthealgorithmtotheperturbednetworkwedonotre-initializenodeswithuniquelabels,butinitializethemwiththelabelsfromthebasesolution.ThenweusetheJaccard'sindextocomparebasesolutionwiththeperturbedsolution.Figure3.7showshowsimilartheperturbedsolutionsaretothebasesolutionsas®variesfrom0to0.5,intheprotein-proteininteractionnetwork,co-authorshipnetworkandintheWWW.Weappliedthelabelpropagationalgorithm5di®erenttimesonthesenetworkstoobtain5di®erentbasesolutions.Andforeachofthesebasesolutionswefoundthecorrespondingperturbedsolution.Eachpointinthegraphforaparticularnetworkin¯gure3.7istheaverageofthese5runs.Wecanseethattheperturbedsolutionsarehighlysimilar(Jaccard'sindex>0.8)tothebasesolutionsevenafter10percentoftheedgesarerewired.Thesimilaritiesarestillgood(>0.6)evenwhen20percentofedgesarerewired. 66Figure3.8.Anexampleofaggregatingtwoclusteredstructuresolutions.t1;t2;t3andt4arelabelsonthenodesinanetworkobtainedfromsolution1anddenotedasC1.Thenetworkispartitionedintogroupsofnodeshavingthesamelabels.s1;s2ands3arelabelsonthenodesinthesamenetworkobtainedfromsolution2anddenotedasC2.Allnodesthathadlabelt1insolution1aresplitintotwogroupswitheachgrouphavinglabelss1ands2respectively.Whileallnodeswithlabelst3ort4ort5insolution1havelabelss3insolution2.Crepresentsthenewlabelsde¯nedfromC1andC2.3.2.3AggregateItisdi±culttopickonesolutionasthebestamongseveraldi®erentones.Fur-thermore,onesolutionmaybeabletoidentifyaclusterthatwasnotdiscoveredintheotherandvice-versa.Henceanaggregateofallthedi®erentsolutionscanprovideaclusteredstructurecontainingthemostusefulinformation.Inourcaseasolutionisasetoflabelsonthenodesinthenetworkandallnodeshavingthesamelabelformacluster.Giventwodi®erentsolutions,wecombinethemasfollows;letC1denotethelabelsonthenodesinsolution1andC2denotethelabelsonthenodesinsolution2.Then,foragivennodex,wede¯neanewlabelasC=(C1;C2)(see¯gure3.8).StartingwithanetworkinitializedwithlabelsxxxCweperformtheiterativeprocessoflabelpropagationuntileverynodeinthenetworkisinaclustertowhichthemaximumnumberofitsneighborsbelongto.Asandwhennewsolutionsareavailabletheyarecombinedonebyonewiththeaggregatesolutiontoformanewaggregatesolution.Notethatwhenweaggregatetwosolutions,ifaclusterTinonesolutionisbrokenintotwo(ormore)di®erentclustersS1andS2intheother,thenbyde¯ningthenewlabelsasdescribedaboveweareshowingpreferencestothesmallerclustersS1andS2overT.Thisisonlyoneofthemanywaysinwhichdi®erentsolutionscanbeaggregated.Forothermethodsofaggregationusedinclusterdetectionreferto[124,129,130].Figure3.9showsthesimilaritiesbetweenaggregatesolutions.Thealgorithmwasappliedoneachnetwork30timesandthesolutionswererecorded.Anijth 67Figure3.9.Similaritiesbetweenaggregatesolutionsobtainedforeachnetwork.AnentryintheithrowandjthcolumninthetablesisJaccard'ssimilarityindexbetweentheaggregateofthe¯rst5iandthe¯rst5jsolutions.Whilesimilaritiesbetweensolutionsforthekarateclubfriendshipnetworkandtheprotein-proteininteractionnetworkarerepresentedinthelowertrianglesofthe¯rsttwotables,theentriesintheuppertriangleofthesetwotablesarefortheUScollegefootballnetworkandtheco-authorshipnetworkrespectively.ThesimilaritiesbetweenaggregatesolutionsfortheWWWisgiveninthelowertriangleofthethirdtable.entryistheJaccardindexfortheaggregateofthe¯rst5isolutionswiththeaggregateofthe¯rst5jsolutions.Weobservethattheaggregatesolutionsareverysimilarinnatureandhenceasmallsetofsolutions(5inthiscase)cano®erasmuchinsightabouttheclusteredstructureofanetworkascanalargersolutionset.Inparticular,theWWWnetworkwhichhadlowsimilaritiesbetweenindividualsolutions(Jaccardindexrange0.4883-0.5931),showsconsiderablyimprovedsimilarities(Jaccardindexrange0.6604-0.7196)betweenaggregatesolutions. 683.3ValidationoftheclusterdetectionalgorithmSinceweknowtheclusterspresentinZachary'skarateclubandtheUSfootballnetwork,weexplicitlyverifytheaccuracyofthealgorithmbyapplyingitonthesenetworks.We¯ndthatthealgorithmcane®ectivelyunearththeunderlyingclus-teredstructuresintherespectivenetworks.TheclusteredstructuresobtainedbyusingouralgorithmonZachary'skarateclubnetworkisshownin¯gure3.4.Whileallthethreesolutionsareoutcomesofthealgorithmappliedtothenetwork,¯gure3.4(b)re°ectsthetruesolution[67].Figure3.5givestwosolutionsfortheUScollegefootballnetwork.Thealgo-rithmwasappliedtothisnetwork10di®erenttimesandthetwosolutionsaretheaggregateofthe¯rst¯veandremaining¯vesolutions.Inboth¯gures3.5(a)and3.5(b),wecanseethatthealgorithmcane®ectivelyidentifyalltheconfer-enceswiththeexceptionofSunbelt.Thereasonforthediscrepancyisthefol-lowing:amongtheseventeamsintheSunbeltconference,fourteams(Sunbelt4=fNorth-Texas,ArkansasState,Idaho,NewMexicoStateg)haveallplayedeachotherandthreeteams(Sunbelt3=fLouisiana-Monroe,Middle-TennesseeState,Louisiana-Lafayetteg)haveagainplayedoneanother.ThereisonlyonegameconnectingSunbelt4andSunbelt3,namelythegamebetweenNorth-TexasandLouisiana-Lafayette.However,fourteamsfromtheSunbeltconference(twoeachfromSunbelt4andSunbelt3)havetogetherplayedwithsevendi®erentteamsintheSoutheasternconference.HencewehavetheSunbeltconferencegroupedtogetherwiththeSoutheasternconferencein¯gure3.5(a).In¯gure3.5(b),theSunbeltconferencebreaksintotwo,withSunbelt3groupedtogetherwithSoutheasternandSunbelt4groupedwithanindependentteam(UtahState),ateamfromWesternAtlantic(BoiseState),andtheMountainWestconference.ThelattergroupingisduetothefactthateverymemberofSunbelt4hasplayedwithUtahStateandwithBoiseState,whohavetogetherplayed¯vegameswithfourdi®erentteamsinMountainWest.Therearealso¯veindependentteamswhichdonotbelongtoanyspeci¯cconferenceandarehenceassignedbythealgorithmtoaconferencewheretheyhaveplayedthemaximumnumberoftheirgames. 693.4TimecomplexityIttakesanear-lineartimeforthealgorithmtoruntoitscompletion.InitializingeverynodewithuniquelabelsrequiresO(N)time.Eachiterationofthelabelpropagationalgorithmtakeslineartimeinthenumberofedges(O(M)).Ateachnodex,we¯rstgrouptheneighborsaccordingtotheirlabels(O(dx)).Wethenpickthegroupofmaximumsizeandassignitslabeltox,requiringaworst-casetimeofO(dx).ThisprocessisrepeatedatallnodesandhenceanoveralltimeisO(M)foreachiteration.Asthenumberofiterationsincreases,thenumberofnodesthatareclassi¯edcorrectlyincreases.Hereweassumethatanodeisclassi¯edcorrectlyifithasalabelthatthemaximumnumberofitsneighborshave.Fromourexperiments,wefoundthatirrespectiveofN,95%ofthenodesormoreareclassi¯edcorrectlybytheendofiteration5.EveninthecaseofErd}os-R¶enyirandomgraphs[1]withNbetween100and10000andaveragedegree4,whichdonothaveclusteredstructures,byiteration5,95%ofthenodesormoreareclassi¯edcorrectly.Inthiscase,thealgorithmidenti¯edallnodesinthegiantconnectedcomponentasbelongingtoonecluster.Whenthealgorithmterminatesitispossiblethattwoormoredisconnectedgroupsofnodeshavethesamelabel(thegroupsareconnectedinthenetworkviaothernodesofdi®erentlabels).Thishappenswhentwoormoreneighborsofanodereceiveitslabelandpassthelabelsindi®erentdirections,whichultimatelyleadstodi®erentclustersadoptingthesamelabel.Insuchcases,afterthealgo-rithmterminatesonecanrunasimplebreadth-¯rstsearchonthesub-networksofeachindividualgroupstoseparatethedisconnectedclusters.ThisrequiresanoveralltimeofO(M+N).Whenaggregatingsolutionshowever,werarely¯nddisconnectedgroupswithinclusters.3.5SummaryanddiscussionTheproposedlabelpropagationprocessusesonlythenetworkstructuretoguideitsprogressandrequiresnoexternalparametersettings.Eachnodemakesitsowndecisionregardingtheclustertowhichitbelongstobasedontheclusters 70ofitsimmediateneighbors.Theselocalizeddecisionsleadtotheemergenceofclusteredstructuresinagivennetwork.Weveri¯edtheaccuracyofclusteredstructuresfoundbythealgorithmusingZachary'skarateclubandtheUScollegefootballnetworks.Furthermore,themodularitymeasureQwassigni¯cantforallthesolutionsobtained,indicatingthee®ectivenessofthealgorithm.EachiterationtakesalineartimeO(M),andalthoughonecanobservethealgorithmbeginningtoconvergesigni¯cantlyafterabout5iterations,themathematicalconvergenceishardtoprove.Otheralgorithmsthatruninasimilartime-scaleincludethealgorithmofWuandHuberman[124](withtimecomplexityO(M+N))andthat2ofClausetetal[49]whichhasarunningtimeofO(NlogN).ThealgorithmofWuandHubermanisusedtobreakagivennetworkintoonlytwoclusters.Inthisiterativeprocesstwochosennodesareinitializedwithscalarvalues1and0andeverynodeupdatesitsvalueastheaverageofthevaluesofitsneighbors.Atconvergence,ifamaximumnumberofanode'sneighborshavevaluesaboveagiventhresholdthensowillthenode.Henceanodetendstobeclassi¯edtoaclustertowhichthemaximumnumberofitsneighborsbelong.Similarlyifinouralgorithmwechoosethesametwonodesandprovidethemwithtwodistinctlabels(leavingtheothersunlabeled),thelabelpropagationprocesswillyieldsimilarclustersastheWuandHubermanalgorithm.Howeverto¯ndmorethantwoclustersinthenetwork,theWuandHubermanalgorithmneedstoknowapriorihowmanyclustersthereareinthenetwork.Furthermore,ifoneknowsthattherearecclustersinthenetwork,thealgorithmproposedbyWuandHubermancanonly¯ndclustersthatareapproximatelyofthesamesize,thatisN,anditisnotpossibleto¯ndclusterswithheterogeneoussizes.ThemaincadvantageofourproposedlabelpropagationalgorithmovertheWuandHubermanalgorithmisthatwedonotneedaprioriinformationonthenumberandsizesoftheclustersinagivennetwork;indeedsuchinformationusuallyisnotavailablefornaturalnetworks.Also,ouralgorithmdoesnotimposeanyrestrictionsontheclustersizes.Itdeterminessuchinformationabouttheclustersbyusingthenetworkstructurealone.Inourtestnetworks,thelabelpropagationalgorithmfoundclusterswhosesizesfollowapproximatelyapower-lawdistributionP(S>s)»s¡ºwiththeexponentºrangingbetween0.5and2(¯gure3.10).Thisimpliesthatthereisnocharacteristic 71Figure3.10.Thecumulativeprobabilitydistributionsofclustersizes(s)areshownfortheWWW,co-authorshipandactorcollaborationnetworks.Theyapproximatelyfollowpower-lawswiththeexponentsasshown.clustersizeinthenetworksanditisconsistentwithpreviousobservations[50,49,66].WhiletheclustersizedistributionsfortheWWWandco-authorshipnetworksapproximatelyfollowpower-lawswithacut-o®,withexponents1.15and1.98respectively,thereisaclearcrossoverfromonescalingrelationtoanotherfortheactorcollaborationnetwork.Theclustersizedistributionfortheactorcollaborationnetworkhasapower-lawexponentof2forsizesupto164nodesand0.5between164and7425nodes(see¯gure3.10).InthehierarchicalagglomerativealgorithmofClausetetal[49],theparti-tionthatcorrespondstothemaximumQistakentobethemostindicativeoftheclusteredstructureinthenetwork.OtherpartitionswithhighQvalueswillhaveastructuresimilartothatofthemaximumQpartition,asthesesolutionsareobtainedbyprogressivelyaggregatingtwogroupsatatime.Ourproposedlabelpropagationalgorithmontheotherhand¯ndsmultiplesigni¯cantlymodu-larsolutionsthathavesomeamountofdissimilarity.FortheWWWnetworkinparticular,thesimilaritybetween¯vedi®erentsolutionsislow,withtheJaccardindexrangingbetween0.4883to0.5921,yetall¯vearesigni¯cantlymodularwithQbetween0.857to0.864.Thisimpliesthattheproposedalgorithmcan¯ndnotjustonebutmultiplesigni¯cantclusteredstructures,supportingtheexistenceof 72overlappingclustersinmanynaturalnetworks[2].Inthischapterweproposedanddiscussedaconsensusformationmechanismtoidentifyandextractclustersfromnaturalnetworks.Inthenextchapterwewilldiscussthesolutiontooursecondproblemofinterestinthisthesis,namelyconnectivityofnetworks. Chapter4ConnectivityofWSNsInthischapterwederivetheoptimaldegreekcforthenearestk-neighborsnetworktohaveagiantconnectedcomponent.Inspeci¯cwewillshowthatkc=5.Wealsolookatthecharacteristicsofthetopologywhenk=4anddiscussitsimplicationontherequirementsofWSNs.Beforewebeginwiththederivationofkcwewillreviewsomethepriorresultsonoptimaltransmissionrangesandnodedegreefromtheliterature.FollowingthiswewillreviewTopologyControl(TC)protocols.EventhoughwedonotdevelopaprotocolbywhichnodescoordinatetheirTCinthisthesis,itisinstructivetounderstandtheirdesignsandjudgetheimportanceoftheresultkc=5.Morespeci¯callywewillshowfromourdiscussionsthatitisrelativelyeasytodevelopprotocolsformaintaininga¯xeddegreekatthenodes[6,58,38].Thatis,theprotocolwillful¯llsomeofthefundamentalrequirementsforittobeimplementableinpractice[38].4.1BackgroundontheconnectivityprobleminWSNsFixedradiusmodels(PoissonBooleanmodelsinwhich½=ra.s.)arethemostwidelyusedgraphstorepresentWSNs.Here,thereisanedge(undirected)betweentwonodesifandonlyiftheyarenomorethanadistancerapart.Inmostcasesthedistancemetricisthe`2normandsometimesothernormssuchas 74`p;1·p·1arealsoconsidered[111].Furthermore,inthesensornetworksliteratureaconnectednetworkisalwaysassumedtobeanetworkinwhicheverynodecancommunicatewitheveryothernodeviathelinksinthenetwork.4.1.1CriticaltransmissionradiusTheproblemofconnectivityonsuchnetworksiswellstudiedandoneoftheearliestresultswasprovedbyPhilips,PanwarandTantawi[52].TheyassumedthesensingregiontobeasquareofareaAwithaconstantdensity¸.HenceasA!1,thenumberofnodesalsoincreases.Theyshowedthatforanygiven²>0,if,pr·(1¡²)lnA=¼¸,thenundertheassumptionofaconstantdensitythegraphisalmostsurelydisconnectedasA!1.Thisimpliesthatforanygivenrand¸,wecanalways¯ndanAlargeenoughsuchthatthegraphisalmostsurelydisconnected.AsimilaranalysiswasdonebyGuptaandKumar[56]onaunitdiskandtheyfoundthatforthenetworktobeconnectedwithprobability1,pr=(lnN+c(N))=¼N,wherec(N)!1asN!1.Nherestandsforthenumberofnodesinthesensingregion.Penrosein[53]studiedingeneraltheproblemofk-connectivityof¯xedradiusnetworksind-dimensionalunitcubes(d¸2).Heshowedthatthegraphbecomesk-connectedalmostsurelywheneverallnodeshavedegreegreaterthanorequaltok.Thatis,asN!1,Pfsmallestratwhichthenetworkisk-connected=smallestratwhichminimumdegree¸kg!1.Thusfortheproblemofsimpleconnectivityitisonlyrequiredtoadjustthetransmissionradiussuchthateachnodehasatleastoneneighbor.Theseresultsholdingeneralforanylpdistancemetricsuchthat15:1774log(N).Whileif'N<0:074log(N),thenetworkisalmostsurelydisconnectedasN!1.Thisimpliesthattomaintaintheconnectivityofanetworkthenumberofneighborscannotbeboundedasthenumberofnodesincreases.4.1.3GiantcomponentsandconnectivityTheproblemofconnectivityhasalsobeenwellresearchedfromthepointofviewofgiantcomponents[133,134,112,135,69,111,110,114,136].Thisisunlikealltheworksdescribedabovewhichrequireeverynodetobepresentinonecom-ponent,thatis,anentirelyconnectednetwork.TheworksbyMeesterandRoy[69],Penrose[111],Quantanilla[110,114]andothersisconcernedwiththekind 76ofgiantcomponentthatarisesbykeepingtheradiusr¯xedandvaryingtheden-sityofnodes¸(InallthesecasesthenodedistributionfollowsaPoissonpointprocessX).Theyshowthatasthedensityofthenodesincreases,foragivenr,thereexistsa¯nitethreshold¸cbeyondwhichauniquegiantcomponentalwaysexist.Similarly,inad-dimensionalunitcube,giventhenumberofnodesN,itispossibleto¯ndcriticalthresholdsNc(r)fortheappearanceofgiantcomponents[113].Furtherthecriticalexpectednumberofneighbors®ccanalsobecalculated[110,114,113]fortheappearanceofgiantconnectedcomponents.Inthiscasehow-ever,thenumberofnodesNis¯xedandtheaveragedegree®=r2NÁincreasesuntilagiantcomponentemerges.Theresultssofarsuggestthat®c¼4:51whend=2and®c¼2:7whend=3[113,110]inthe¯xedradiusmodels.Also,given1®cd+21N,thecriticaltransmissionradiusrc(N)=pf¡()gdfortheappearanceof¼N2pauniquegiantcomponent.Whend=2,r(N)issimply®c[113,136].c¼NItwasalsoshownthatthereexistsimilarcriticaldensitythresholds(¸c(g))fortherandomconnectionmodelswithconnectionfunctiong[69].Further,Franceschettietal[112]showedthatsquish-squashingaconnectionfunctiongintopanotherconnectionfunctionh=p:g(px)forsome0k®thereexistsagiantcomponentalmostsurelyinthenearestk-neighborsmodel.Thenifkcexistsitmustbe·k®.Letrc(¸)bethecriticalradiusforconnectivityofa¯xedradiusnetworkwhosenodesaredistributedaccordingtoaPoissonpointprocessXofintensity¸inR2[113,136].Supposeeachnodeadjustsitstransmissionradiustoaccommodateadesirednumberofneighborsk.Thenadirectededgefromanodetowardsitskneighborsisformed.Letk®=inffkjinfi2Xfrijoutdegreeatallnodesinthenetwork=kg¸rc(¸)gk®isthenthesmallestksuchthatthesmallesttransmissionradiusrequiredatanynodetohavekoutgoingneighbors,isatleastrc(¸).Notethateventhoughkisindependentof¸,k®mightnotbe.Ifeachnodeadjustsitstransmissionradiustobeabletosendmessagestoatleastk®neighbors,therewillbeedgesinbothdirectionsbetweennodesthatarenomorethanadistancerc(¸)apart.Hencetherandomconnectionmodelwithaconnectionfunctiongde¯nedas8<1;8kxk·rc(¸)g(x)=:0;8kxk>rc(¸)becomesasubgraphofthenearestk®-neighborsnetwork.Thisisbecauseinnearestk®-neighborsnetworkeachnodehasatransmissionradiusofatleastrc(¸).Also,sincethe¯xedradiusnetworkhasagiantcomponent(bythede¯nitionofrc(¸))sodoesthenearestk®-neighborsnetwork.Therefore,foragivenX,and8k¸k®,thenearestk-neighborsmodelhasagiantconnectedcomponent.Todeterminethevalueofk®,weknowfrom[140]thatifWkistherandomvariableforthedistanceofthekthnearest-neighbor(k¸1)fromapointinX,thenk2k¡1¡¼¸w2theprobabilitydensityfunctionofWkisgivenby,f(wk)=2(¼¸)wkek=(k¡k211)!.ItimmediatelyfollowsthatE(Wk)=k(2k)!=(2k!)¸2.Inordertoobtaink®, 80letus¯rstcalculatetheP(Wk¸rc(¸)).Z122k¡¼¸w2dwkP(Wk¸rc(¸))=(¼¸wk)ek(4.1)rc(¸)(k¡1)!wkBychangingthevariableasx=¼¸w2,wegetkZ1xk¡1e¡xy=Xk¡1(¸¼r2(¸))ye¡¸¼rc2(¸)cP(Wk¸rc(¸))=dx=(4.2)¼¸rc2(¸)(k¡1)!y=0y!(Referto[65]fortherighthandsideequation.)Butwealsoknowthat,thecriticalaveragedegreeinthenetworkfora¯xedradiusmodeltopercolateisapproximately4.51[113,110].Whichmeansthatinordertoobtainanaveragedegreeof4.51weqqmustsetr(¸)=4:51.Notethatifwe¯xr=dinthe¯xedradiusnetworkc¼¸¼¸model,thentheexpecteddegreeonanodeinthenetworkisd.Substitutingforrc(¸)inequation(4.2),weget,y=Xk¡1y¡4:51(4:51)P(Wk¸rc(¸))=e(4.3)y!y=0andthisprobabilityisindependentof¸.Thusk®whichisnowthesmallestksuchthattheprobabilityinequation(4.3)is1isinfactindependentof¸.However,onlyask!1theaboveprobabilitytendsto1.Butweseethatevenforkaround10,thisprobabilityismorethan0.99andforkabout15itisarbitrarilycloseto1.Hencewecansafelyassumethatk=15yieldsanetworkinwhicheachnodehasatransmissionradiusofatleastrc(¸).Thusbyde¯nitionofrc(¸)thisnetworkwillhaveagiantconnectedcomponent.Requiringeverynodetohaveatleastatransmissionradiusofrc(¸)givesapessimisticestimateofkc.Ifontheotherhandwe¯ndthesmallestvalueforksuchthattheexpectedtransmissionradiionthenodesinthenetworkisatleastrc(¸),thenweneed,rk(2k)!4:51E(Wk)=1¸=rc(¸)(4.4)(2kk!)2¸2¼¸ 81andthisimpliesrk(2k)!4:51¸(4.5)(2kk!)2¼andweseethatk=5isthesmallestvalueforwhichtheaboveinequalityissatis¯ed(see¯gure4.1).Thisalsoimpliesthatk=4isthelargestvalueforwhichtheaboveinequalityisnotsatis¯ed.Henceforvaluesofkupto4,thenearestk-neighborsmodeldoesnothaveagiantcomponent(bythede¯nitionofrc(¸)).Furtherthisistrueirrespectiveofthedensityofnodesinthenetwork.Simulationresultsalsoagreethatfork=5andabovethenearestk-neighborsmodelofanydensity¸hasanunboundedconnectedcomponent.Whilefork<5thereexistsnogiantcomponents(see¯gure4.1).4.3.2SimulationresultsToverifytheaboveanalysisusingsimulation,we¯xedthesizeofthesensingregiontobeaunitsquare.We¯xedthesizeofthenetworktobeNandthenumberofneighborsaskineachsimulation.WevariedNfrom50to5000andkfrom3to6.Weran10experimentseachfora¯xedNandk.Theresultsfromtheseexperimentsareplottedasgraphsin¯gure4.1.Notethatfork=5approximately95%ofthenodesareinthegiantcomponent.Fork=4thesizeofthelargestcomponentscalessub-linearlywithN.Itwouldnotbepossibletoobtainboundednodedegreesifwechangetherequirementsforconnectivity.Thatis,insteadofgiantcomponentswelookforafullyconnectednetworkthenkshouldbeatleast5:1774log(N)[38,?].4.3.3EnergyconsumptioninthenearestneighborsmodelThesumoftransmissionradiusatallthenodesinaWSNisameasureoftheenergyconsumedinthenetwork.Inthissectionwewillshowthatforthesamenumberofneighbors,boththe¯xedradiusmodelandthenearestneighborsmodelconsumesapproximatelythesameamountofenergy.Toshowthis,weneedthefollowing.SupposewerestrictthePoissonpointprocessXofintensity¸inR2toa¯niteregion,sayaunitsquare.Then,letthenumberofnodesinthis¯niteregionbe 82Figure4.1.Foreach¯xedk,thegraphsshowhowthesizeofthelargestconnectedcomponentgrowsasthenumberofnodesNincreases.Notethatwhilethereexistsnogiantcomponentfork=3;4itappearssuddenlyfork=5.N.Thelengthofagraphisthesumofthelengthofitsedges.Henceforthekthnearestneighborgraphinwhicheachnodeisadjacenttoitskthclosestneighbor,thelengthLk;Nisgivenby[133],Xj=k1Lk;N1¡(j¡2)limN!1E(1)=1(4.6)N22¼2(j¡1)!j=1Thereforetheexpectedsumofthetransmissionradiionthesensornodesinthenearestk-neighborsmodelisthesameastheexpectedlengthofthekthnearestneighborgraph.Also,thesumofthetransmissionradii(qLr;N)ina¯xedradiusmodelisdNwheredisthedesiredconnectivity.Takingk=5andNsu±ciently¼N1largeinequation(4.6),weget,E(Lk;N)¼2:1809()2.Alsoforthesameconnec-¼N1tivity,thatistakingd=5,wehaveE(Lr;N)¼2:2361()2.Oncomparisonwe¼seethatfora¯xedNandk,Lr;N¼Lk;N. 83Figure4.2.Foreach¯xedk,thegraphsshowhowthesizeofthelargeststronglyconnectedcomponentgrowsasthenumberofnodesNincreases.Notethatwhilethereexistsnogiantcomponentforkupto3itsuddenlyappearsfork=4.4.3.4StronglyconnectedcomponentsInthenearestk-neighborsmodelweonlyconsideredthebi-directionaledgesandignoredthepresenceofunidirectionalones.Henceifwestudythenetworkfortheappearanceofgiantstronglyconnectedcomponents,thenthecriticalvalueforkis4(see¯gure4.2).Byastronglyconnectednetworkwemeanthatforanypairofnodesxandy,thereexistsadirectedpathbothfromxtoyandfromytox.4.4SummaryanddiscussionInthischapterweconsiderede±cientmaintenanceofconnectivityofawirelesssen-sornetwork.Inadditiontoenergye±cientvaluesforcriticaldegreeonthenodes,wealsoconsideredtheconstraintsandrequirementsfromtheviewoftopologycontrolprotocols.Wehaveshownthatwhennodesadjusttheirtransmissionradiustomaintaina¯xedout-degreek,then5isthecriticalthresholdbeyondwhichagiantcomponent 84existsalmostsurelyinthenetwork.Further,thisistrueirrespectiveofthenumberofnodesN.ThisimpliesthatthedegreesonthenodescanbeboundednomatterhowlargeNmaybe,enablingtheuseofalargenumberofwirelesssensornodestoformaWSNwithboundedinterferences.Wewillnowproceedtosummarizetheresultsandcontributionsofouroverallwork(clusteringandconnectivity)inthenextchapter. Chapter5ConclusionsandfutureworkWhenwetrytopickoutanythingbyitself,we¯ndithitchedtoeverythingelseintheuniverse."|JohnMuirInthisthesiswehavesolvedtwoproblemsonlarge-scalenetworks,clusteringandconnectivity.Inclusterdetection,givenasetofnodesandtheirinterconnections,theobjectivewastominethroughthenetworktoextractdenselyconnectedsub-groups.Inchapter3wehaveproposed,discussed,analyzedandveri¯edourclusterdetectionmethodonexamplesofnaturalnetworks.Fortheproblemofconnectivity,givenasetofnodes,wecreatedinterconnec-tionsbetweennodessothattheresultingnetworkisconnected,subjecttocertainconstraints.Inchapter4wherewediscussedtheproblemofconnectivity,withafocusonWSNs,weweakentheconnectivityrequirementtoobtaindesirablepa-rameters.Inspeci¯c,aboundednodedegreewasarequirementinWSNsandweshowedthatsuchaboundeddegreeinindeedobtainableforagiantconnectedcomponentinthenetwork.Inthischapterwehighlightsomeofthekeyresultsandcontributionsfromourresearchandalsodiscussdirectionsforfuturework. 865.1ProblemI:FindingclusteredstructuresinnaturalnetworksTheproposedmethodisaniterativelabelpropagationprocess.Hereeverynodeisinitializedwithauniquelabel.Ateachiteration,nodes,byobservingtheirneigh-borsadoptlabelsthatamaximumnumberofthemhave.Asaresultconsensusonauniquelabelemergesbetweendenselyconnectedgroupsofnodes.5.1.1Resultsandcontributions²Inthisthesiswehaveinvestigatedanewwayofidentifyingandde¯ningclustersasconsensusgroupsinnetworks.²Thetimecomplexityoftheproposedalgorithmisnearlinear(withrespecttothenumberofedgesM)andhenceitsapplicabilitytolargenetworks.Weshowedthatwecan¯ndclusteredstructuresfromverylargenetworkssuchasthemovieactorcollaborations(with374,511nodesand15,014,850edges)withamodularityindexQ¼0:5.Inaddition,wewillshowinsection5.1.2.3thatwewereabletosuccessfullyapplyouralgorithmto¯ndclusteredstructuresinalargeonlinesocialnetworkYoutube(1,157,827nodesand2,990,443edges)withthemodularityindexQ¼0:66.Furtherweshowhowonecanusetheseidenti¯edclustersinYoutubeandcomparethemwithUserGroupspresentinYoutube.Toourknowledge¯ndingandanalyzingclustersinsuchlargegraphswasnotpossiblebefore.²Thelabelpropagationprocessfallsundertheclassofrandomizedalgorithms.Thisisbecause,ifanode,whenobservingthelabelsonitsneighbors,¯ndsnoclearmajority(or¯ndsequalnumberofneighborsineachlabel),adoptsarandomlychosenlabel.²Consequently,di®erentrunsofthealgorithmonthesamenetworkyieldsdi®erentsolutions.²Inourtestnetworks(Friendshipnetwork,collegefootballnetwork,protein-proteininteraction,co-authorshipnetwork,WWWandmovieactorcollabo-rations),thealgorithmfoundmultiplepartitionsthatareallsimilarinnature. 87Inspeci¯c,weusedtheJaccard'sindextotestthesimilaritybetweentwosolutions/partitionsinanetworkandshowedthattheyhaveahighdegreeofsimilarity.²Inaddition,themodularitymeasureQwassigni¯cantlyhighwithatightrangeindicatingthesigni¯canceofthemultiplesolutionsfoundbythealgo-rithmonthesamenetwork.²Wefurthershowedthat,inourtestnetworks,thesolutionsfoundbythealgorithmremainsstrongtosmallperturbations.Thisimpliesthatthesesolutionsarenotanartifactofthealgorithm,butre°ectthenatureofthetrueclusterspresentinthesenetworks.²Multiplesolutionsinnaturalnetworksalsosupportsthepresenceofover-lappingclusters[2].Whilemostclusteringmethodsfocusonasinglebestsolution,wehaveshownthatinnaturalnetworksthereexistsmultiplesolu-tionsthataresigni¯cantlymodularandstrongagainstsmallperturbations.5.1.2Futurework5.1.2.1NetworkmodelingAsdiscussedinChapter2,naturalnetworksarealreadyorganized.Themannerofself-organizationinsocialorbiologicalnetworksortheWWWgivesrisetoaclusteredstructure.Understandingtheprinciplesbehindsuchanorganizationanditse®ectsondynamicalprocesssuchasdi®usion,searchandnavigation,functionalrequirementsetcisanunsolvedproblem[47].Theproblemliesintheinabilitytocharacterizeaself-organizationmechanismthatwillgiverisetoaclusteredstructureinlarge-scalenetworks.Forexample,wedonotyetknowwhycertainnetworkshaveamodularityindexQintherangeof0.4to0.5,whilesomehaveQintherangeof0.5to0.6andsoon.Researchinthisareaisstillinitsinfancyanditwillbeworthwhiletoidentifyhowaconsensusformationmechanismcancontributetonetworkmodelingprinciples. 885.1.2.2OpinionformationinnetworksOpinionformationisadynamicalprocesstakingplaceonanetworkandmorespeci¯callystudiedinsocialnetworks.Thegeneralideaofopiniondynamicsisthateachindividualcanhaveopinionsthatwillform/changebasedontheirinteractions[10].Inthesimplestform,anodecanhaveoneofthetwoopinions0or1andineachstepanodeadoptsanopinionofanyoneofitsneighbor.ThisiscalledastheVoter'smodel[10,141].Hencegivenanetworkandarandominitializationofopinions,theideaistostudyhowandwhenthe°uctuationsleadtoaconsensusofaopinionintheentirenetwork[141].Whileinitiallyopiniondynamicswasstudiedonregularnetworksorlattices,recentlythefocushasshiftedtowardsothernetworkmodelssuchassmall-worldandpower-lawnetworks.MorerecentlyWuandHuberman[141]studiedthevoter'smodelongeneralizedrandomgraphsofagivendegreedistribution[71].Theyshowedthatonecanobserveasocalledlocalitye®ectorane®ectinwhichopinionsareorganizedintosmallergroupswithouta®ectingthewholesocietyornetwork.Thelabelpropagationprocessandconsensusformationthatwehaveusedforourclusteringmethodissimilarinnature(thoughnotthesame)tothestudyofvoter'smodeldynamicsandopinionformationinnetworks.Unlikethecasewherethereareonlytwopossibleopinions,webeginwithacasewhereeverynodecanhaveitsownuniqueopinion.Alsounlikethevoter'smodel,weforceeachnodetoadopttheopinion(label)foundmostcommonlyamongitsneighbors.Wemakethefollowingobservations.²Opiniondynamicshasbeenwidelystudiedinvariouskindsofnetworkmod-els,includinginrandomizedpower-lawnetworks[141].However,noworksofarhaveaddressedopinionformationinnetworksthathasclusteredstruc-tures.Whilewedonotyethavenetworkmodelsthatcanmimicthecharac-teristicsofclustersinsocialnetworks,wecanneverthelessformtoymodels.Forexample,onecanconsideranetworkonNnodesandkclusters,witheachclustercontainingNnodes.IfwehaveMedges,thentheycanbekequallyandrandomlydistributedwithinthesekgroupsandaverysmallfractionoftheseMedgesinterconnectingnodesbetweengroups[47,66].²Conversely,opiniondynamicscanalsobeusedtoidentifyclustersinnet- 89works.Wehaveshownthroughourlabelpropagationprocessthatconsensus(oropinionformation)occursamongdenselyconnectedgroupsofnodesandhencee®ectivelyextractstheclusterspresentinnetworks.5.1.2.3ClustersandusergroupsinonlinesocialnetworksOnlinesocialnetworkingsitessuchasYoutube,Orkut,Flickr,FacebookandLive-JournalareamongthemostpopularsitesontheInternet.Thesesitesarearepositoryofsomeofthelargestdatasetsonsocialnetworks[142].IfweconsiderYoutubeforexample,anodeinthenetworkisaregistereduserofYoutubeandagivenusercanhaveregisteredlinks(friendships)withotheruserswithinYoutube.Oneofthemostinterestingfeatureofthesesocialnetworkingsitesisthattheyprovideadditionalinformationonauser'sinterest.Thatis,eachusercanasso-ciatethemselveswithwhatistermedasusergroupswithinonlinesocialnetworks[142].AgainletusconsiderYoutubeasanexample.Youtubeprimarilypromotesthebroadcastingofvideosandeachusercancreateandbroadcastvideosoftheirchoice.Alsoanyusercancreateand/orbelongtospecialinterestvideogroups(calledusergroups).Supposethatuserxhasspecialinterestinthetopicglobalwarming",thenxcancreateand/orjointheusergrouponglobalwarmingvideos.Afterjoiningthegroup,xcanaddhis/hercollectionofglobalwarmingvideostothegroupandholddiscussionswithothermemberswithinthegroup.AlsoanyuserofYoutubeirrespectiveofwhetherarenottheyarefriendsofxcanjointhisspecialinterestusergroup.ThevideosbroadcastedandtheusergroupsagivenuserisassociatedwithcanbeseenbyanyotheruserwithintheYoutubenetwork.AsimilarmechanismtakesplaceinallotheronlinesocialnetworksitessuchasOrkut,Flickr,FaceBookandLiveJournal[142].Asmentionedaboveoneoftheuniquefeatureofthedataononlinesocialnet-worksistheavailabilityofinformationonagivenuser'sinterests.Ourinterestinthisdatasetistoseeifthereareanysimilaritiesbetweenclustersandusergroups?Canwesaythatdenselyinterlinkedclustersofusershavesimilarinterests?Toanswerthesequestionswe¯rstappliedourproposedclusteringalgorithmontheYoutubedatasetconsistingof1,157,827usersand2,990,443links.WeobtainedclusteredstructuresfromtheYoutubenetworkwithamodularityindexQ¼0:66.ThishighvalueofQindicatesthatthepartitionofthenetworkobtainedbyour 90clusteralgorithmissigni¯cantandithasindeedfounddenselyinterlinkedgroups.Withtheinformationonclustersinthenetworkandusergroupswedidthefollowing,1.Withineachclusterweidenti¯edthesizeofthelargestusergroup.Thatis,amongthevarioususergroupsthateachusercanbelongto,weidenti¯edthesizeofthelargestusergroupwithinagivencluster.LetCU(i)bethefractionofnodesinclusterithatbelongtothelargestusergroup.(Notethatoneusercanbelongtomultipleusergroups).2.Withineachusergroupweidenti¯edthesizeofthelargestcluster.Thatis,wepartitionedthemembersofausergroupintotheirrespectiveclustersandidenti¯edthesizeofthelargestclusteramongthem.LetUC(j)bethefractionofnodesinusergroupjthatbelongthelargestcluster.InYoutubethereareabout30,087di®erentusergroupswithnumberofusersineachusergroupvaryingbetween1and7591.Thenumberofclustersidenti¯edbythealgorithmwasapproximatelyaround61,000andtheclustersizesvaryiedbetween3and250,428.Asmentionedaboveagivenusercanbelongtomultipleusergroupsornone.Therefore,tocalculateCU(i)inaclusteri,we¯rst¯lteredoutthoseusersintheclusterwhodonotbelongtoanyusergroup.WethencalculateCU(i)onthisreducedclusterthatonlycontainsuserswhobelongtoatleastoneusergroup.InYoutube,amongthe61,000clustersonlyabout11,177clusterscontainanon-zeronumberofuserswhobelongtousergroups.Theremaining49,823clustershadnomemberwhobelongedtousergroupsandarehencediscardedfromthecalculationofCU(i).Figure5.1showstherelationshipbetweenusergroupsandclusters.Atthispointwecannotconclusivelysayiftheyareoneandthesameortheyaretwodi®erentconcepts.Wecanseethatthereexistssomeclusterswithinwhichallusershaveatleastonecommoninterest(usergroup)whiletherearealsosomeclustersinwhichCU(i)isverysmallindicatingthediversityofinterestwithinthecluster.Similarlyifwelookatusergroups,therearesomeinwhichallmembersarefromthesamecluster,whiletherealsoexistsusergroupsinwhichmembersarefrommanydi®erentclusters.Howeverwewouldliketopointoutthatfromvisual 91Figure5.1.ThegraphsshowthefractionUC(j)andCU(i)intheYoutubenetworkacrossvarioususergroupsandclustersrespectively.inspectionwefoundalargenumberofusergroupshavingmembersfromthesamecluster,whiletheconverseisnottrue.Establishingtherelationshipbetweenclustersandusergroupsisoneoftheinterestingproblemsforfutureresearch.Itcanhelpusunderstandifclusters(communities)ofpeopleinsocialnetworksaresimilar?Itcanhelpustostudyifpeoplewithinclustershavesimilarinterests?Ifnot,howcanweidentifygroupsofpeoplewhowillhavesimilarinterests?5.1.2.4CitationnetworksandimpactfactorsAcitationnetworkisanetworkofpapers/articlesrepresentedasnodesanddi-rectededgesconnectingcitingpapersdirectedtowardsthecitedpapers[143,17].Citationshavebeenusedasatooltoidentifyresearchpapersandtoevaluatetheirintellectualmerit.TheScienceCitationIndex(SCI)usesthenumberofcitations 92apaperreceivesasameasureofitsintellectualmerit[143].Morerecently[144]aComprehensiveCitationIndex(CCI)hasbeenproposedthatmeasurestheimpactofapapernotjustbyitsimmediatecitationsbutasacumulativeimpactthroughpathwaysofcitations.Authorsin[144]assumethateverypaperequallydistributesaportionofitsin°uencetothepapersthatarebeingcited.Andbyaniterativeprocesstheseweightsaredistributedtoallnodesinthenetworkthroughdirectedpathways.In[144],theSCIandCCIconceptswereappliedtoacitationnetworkconsistingofpapersmostlyfromManagementSciencecollectedfromhttp://scholar.google.com.Thenetworkconsistedof288,404papersandtheircitationinterconnections.LetuscallthisnetworkGMS.InGMSamongthetop10papersrankedbyManagementScienceexpertsCCIperformedsuperiortoSCI.EvenwithabetterperformancefromCCIthereisstillroomforimprovement.OneoftheassumptionsofCCIistheequaldistributionofapaper'sin°uencetoallitsreferences.Itmaybeahardtaskjustifyingsuchadistributionandmaynotbetrueinreality.WeperformedasimpleexperimentinwhichwereplacedallthedirectededgesinGMSbyundirectedones.InthisversionofGMSweappliedthelabelpropagationalgorithmandfoundthatthenetworkwassigni¯cantlymodularwithQ¼0:69.Wealsoobservedthatingeneralpapersonsimilartopicswereclusteredtogether.Thiscouldimplythatsomeofthein°uencesapaperdistributestoitsreferencescanbebiasedtowardswithinclusterreferencesasopposedtoreferencesoutsideoftheclusterorvice-versa.Howtheseweightsshoulddi®er,byhowmuchandhowitwillimpacttheintellectualmeritofpapersisatopicforfutureresearch.5.1.2.5ClustersinCallgraphsDuringtheauthor'sinternshipatIBM-IndiaResearchLab(summer2007),thefocuswason¯ndingclustersparticularlyincallgraphs.Acallgraphisanetworkofphonenumbersrepresentedasnodesandinterconnectedbycompletedcallsbetweentwophonenumbers[82,145].Callgraphsaretakenoverdi®erenttimeintervalsandhencewhenanalyzingsuchgraphsitisimportanttomentioniftheedges(calls)arerecordedwithinadayorweekormonthandsoon.Oneoftheobjectivesduringtheinternshipwastoidentifytargetsegments.Thatis,identify 93Figure5.2.Examplesofstar-likegraphsformedbythecentralnodesu;vandwandtheirneighbors.Thelocalordercoe±cientsLu=0=Lv,whileLw=0:044.HoweverL0u>L0vsincedegreeofvishigherthanthedegreeofu.Alsonotethatdespitefewedgesrunningbetweenneighborsofw,L0w1=L0.Thuslargerstars(centralnodeswithhigherdegrees)willukukvvhavesmallerL0sandcanbedi®erentiatedfromthetrivialcases.Inspeci¯c,wecanchooseathreshold®andidentifyonlythosewhoseL0valuesarelessthan®.Usingthisprocedurewemayalsochooseimperfectstar-likeclusters(see¯gure5.2)aslongastheirL0<®.Thisisreasonablebecausethequalityof`star'ishnessisstillmaintained.NotethatwhenL0isnormalizedtotakevaluesbetween0and1atallnodesitbecomesidenticaltothelocalordercoe±cientL.Figure5.3showssomeofthestar-likeclustersidenti¯edinGcallwhen®=0:05.Forthisthresholdthenumberofclustersidenti¯edwaswellbeyond500(overlapsallowed).Hencethereisasigni¯cantpresenceofstar-likestructuresinGcall.Fromthepointofviewofthetelecomcarrier,astar-likeclusterisasimportantasacliquecluster.Acliqueincallgraphsmaydenoteagroupoffriendsorfamily 95whereeverycustomerhascommunicationwitheveryothermember.Whereasastar-likeclustermaydenoteabusiness-clientgroupwiththecentralnodemakingbusinessrelatedcalls(orreceivecalls)fromhis/herclients.Furthermore,thisdi®erencewarrantsdi®erentincentiveplansforthesetwokindsofcustomergroups.Whenwelookattheorganizationofcallgraphsitishighlylikelythatwewill¯ndmanysuchstar-likeclusters(asinGcall)aswellassocialclusterslikecliques,densesubgraphsetc.Thisisbecausetherewillexistcustomerswhousephonesforbusinesspurposesandthosethatusephonestocallfamilyandfriends.Whenwelookatasocietythroughthemediumofphoneinteractionswecan¯ndasigni¯cantnumberofsparsestar-likeclustersde¯ningtheorganizationofthecorrespondingnetwork.Thiskindofclusterisdi®erentfromtheideaof¯ndingdensesubgroupsthatisbeingrigorouslypursuedinliterature,andweanticipatethatresearchonstar-likeclusterswillbringinterestingnewinsights.5.2ProblemII:ConnectivityofWSNsTheproblemofconnectivityisaclassicalonewhereononehandwewouldliketocreatemoreandmorelinkstoformaconnectednetwork,andontheotherhand,designconstraintsrestricttheformationoflinks.Inchapter4,wetriedto¯ndamiddlegroundwherebothconnectivityandconstraintsaresatis¯ed.Theconstraintsinthiscasewasreducedinterferenceandreducedpowerconsumption.Boththeserequirementssimpli¯esinto¯ndingthesmallestdegreeonthenodesthatwillleadtoconnectivity.5.2.1Resultsandcontributions²Weshowedthatthereexistsak®suchthatfork¸k®thenearestk-neighborsnetworkhasagiantcomponentalmostsurely.Thisk®isthesmallestkforwhichthe¯xedradiusmodelwithrc(¸)isasubgraph.Andbyde¯nitionofrc(¸)the¯xedradiusmodelhasagiantcomponentandthereforethenearestk-neighborsnetwork.²Weshowedthatk®isfunctionallyindependentof¸,whichisthedensityofnodesinaunitsquare,butisnumericallyarbitrarilylarge. 96²Wefurthershowedthatkc=5isthesmallestkforwhichthe¯xedradiusmodelwithrc(¸)isexpectedtobeasubgraphofnearestk-neighborsnetwork.²Weveri¯edusingsimulationsthatfork¸5,nearestk-neighborsnetworksalmostsurelyhavegiantcomponents.²Unlikepreviousresultswhichinsistedthatkisafunctionof¸andincreaseswith¸,wehaveshownthatitispossibletoputaboundonk.Thiswedobyweakeningtheconnectivityrequirement.Thatis,insteadofensuringeverysinglenodeisconnectedbypathswithothernodes,weonlyrequireagiantconnectedcomponentinthenetwork.²Sincewirelesssensornodesareredundantlyusedinasensingregion[7,6,38],theaboveassumptionofaweakconnectivityisreasonable.²The¸independentvalueofkc=5hassigni¯cantimplicationsonthedesignoftopologycontrolandprotocolsforWSNs[38].Thisimpliesthatitispossibletoachieveatopologythatmaintainsbothconnectivityandboundedinterferencesinthenetwork.5.2.2Futurework5.2.2.1WSNarchitectureandclusteringAsdiscussedinChapters2and4,themainobjectiveofatopologycontrol(TC)istomaintaincertainfundamentalpropertiesofthecommunicationnetwork.TCgivesstructuretoanotherwiseloosecollectionofwirelesssensornodes.However,therequirementsofacommunicationtopologygobeyondsimplecon-nectivity.ThemaingoalofaWSNistoaggregateandtransmitdataobservedattheindividualsensornodesandsendthesensedinformationtoanenduser[7,35].Butwemaintainanetworkthatisassparseaspossibleandjustman-agesanoverallconnectednetwork.Thismakesthetasksofrouting,navigation,dataaggregationetctedious.Tocircumventthisproblem,itwasproposedthataWSNshouldbehierarchicalinnatureinsteadofjustone°atarchitecture.Morespeci¯cally,supposewecanarrangesmallgroupsofnodesintoclusters.Thenwecanchoosealeaderforeachcluster,whowillallinturnformthenextlayerof 97hierarchy.Thatis,theseleadersformavirtualbackbonetransmittingdataandinformationfromoneclustertoanother.Therehasbeenmuchworkintheliteraturethataddressestheissueofformingclustersandleadersinanenergye±cientmanner[147,148,149,150,151].Thereisalsoworkthatgroupsnodesintoclustersandatthesametimereduceinterferenceswithinandacrossclusters[147].Theyallhoweverassumethatthereexistsabasiccommunicationstructure.Forexamplein[148],theybuildclustersinaWSNwhereeachnodehasthesame¯xedradiusr.Insomework,theyalsoassumethatthereareafewgatewaynodesthatareverypowerfulandcantransmittolongdistances.Thesegatewaysarechosenasleadersandothersensornodesclusteraroundtheseleaders[149].WecaneitherproposeorapplyvariousclusteringtechniquesbyassumingthatthebasiccommunicationstructureofaWSNislikethenearestk-neighborsnet-work.BydoingsowecanevaluateboththeclusteringalgorithmsandthenetworkmodelitselfasasensiblerepresentationforWSNs.5.3ClosingremarksStructuralorganizationofcomplexnetworkshasbeenabusyareaofresearchintherecentyears.Theideathatnetworktopologyplaysasigni¯cantroleinasystem'sbehaviorhaspermeatedtomanyapplicationareas.ThedesignofWSNtopologytosupportsensingtasksandidentifyingcustomergroupsusingcallingpatternsincallgraphsareonlyafewsuchexamples.Moreimportantlytheseexampleshavealsoraisedsomeissues/problemsthatareattheheartofnetworkscienceresearch.Forinstance,1)whatisthatidealnetworktopologyforWSNswhichcanwithstandnodefailuresaswellassupportvariousdynamicalprocessessuchascommunication,navigationandinformationdi®usion?and2)isitsu±cienttode¯neclustersasdenselyconnectedgroups?Dosparselyinterconnectedstar-likeclustersplayanequivalentroleasdenselyconnectedclustersintheorganizationofcallgraphs?Webelievethatfocusingontheseissueswillleadtoexcitingnewresultsinthefuture. Bibliography[1]Bollobas,B.¶(1985)RandomGraphs,AcademicPress,Orlando,FL.[2]Palla,G.,I.Derenyi¶,I.Farkas,andT.Vicsek(2005)Uncoveringtheoverlappingcommunitystructureofcomplexnetworksinnatureandsociety,"Nature,435,pp.814{818.[3]Wasserman,S.andK.Faust(1994)Socialnetworkanalysis:MethodsandApplications,CambridgeUniversityPress.[4]Newman,M.E.J.(2003)Thestructureandfunctionofcomplexnet-works,"SIAMReview,45,pp.167{256.[5]Jeong,H.,B.Tombor,R.Albert,Z.N.Oltvai,andA.L.Barabasi(2000)Thelarge-scaleorganizationofmetabolicnetworks,"NATUREv,407,p.651.[6]Santi,P.(2005)TopologyControlinWirelessAdHocandSensorNetworks,JohnWileyandSons,Chichester,UK.[7]Estrin,D.,R.Govindan,J.Heidmann,andS.Kumar(1999)NextCenturyChallenges:ScalableCoordinationinSensorNetworks,"inthePro-ceedingsofACMMobiCom,pp.263{270.[8]Albert,R.andA.-L.Barabasi¶(2002)Statisticalmechanicsofcomplexnetworks,"ReviewsofModernPhysics,74(1),pp.47{97.[9]Albert,R.,H.Jeong,andA.-L.Barabasi¶(1999)Diameteroftheworldwideweb,"Nature,401,pp.130{131.[10]Boccaletti,S.,V.Latora,Y.Moreno,M.Chavez,andD.-U.Hwang(2006)ComplexNetworks:StructureandDynamics,"PhysicsReports,424(4-5),pp.175{308. 99[11]Watts,D.andS.Strogatz(1998)Collectivedynamicsofsmallworldnetworks,"Nature,393,pp.440{442.[12]Carrino,C.(2006)Astudyofrepeatcollaborationinsociala±liationnet-works,Ph.D.thesis,ThePennsylvaniaStateUniversity.[13]Tjaden,B.andG.Wasson,TheOracleofBacon,"http://www.cs.virginia.edu/oracle/(lastaccessedApril2008).[14]Newman,M.E.J.(2001)Thestructureofscienti¯ccollaborationnet-works,"ProceedingsofNationalAcademyofSciences,98,pp.404{409.[15]|||(2001)Scienti¯ccollaborationnetworks.I.Networkconstructionandfundamentalresults,"PhysicalReviewE,64(1),p.016131.[16]|||(2001)Scienti¯ccollaborationnetworks.II.Shortestpaths,weightednetworks,andcentrality,"PhysicalReviewE,64(1),p.016132.[17]Hirsch,J.E.(2005)Anindextoquantifyanindividual'sscienti¯cre-searchoutput,"ProceedingsoftheNationalAcademyofSciences,102,p.16569.[18]Egghe,L.(2006)Theoryandpractiseoftheg-index,"Scientometrics,69(1),pp.131{152.[19]Grossman,J.,P.Ion,andR.Castro,Erd}osNumberProject,"http://www.oakland.edu/enp/(lastaccessedApril2008).[20]Faloutsos,M.,P.Faloutsos,andC.Faloutsos(1999)Onpower-lawrelationshipsoftheInternettopology,"inSIGCOMM'99:ProceedingsoftheconferenceonApplications,technologies,architectures,andprotocolsforcomputercommunication,ACM,pp.251{262.[21]Govindan,R.andH.Tangmunarunkit(2000)HeuristicsforInternetMapDiscovery,"inIEEEINFOCOM2000,TelAviv,Israel,pp.1371{1380.[22]Kan,G.(2001)Peer-to-PeerHarnessingthePowerofDisruptiveTechnolo-gies,chap.Gnutella,O'Reilly,Beijing.[23]Adamic,L.A.,R.M.Lukose,A.R.Puniyani,andB.A.Huberman(2001)SearchinPower-LawNetworks,"PhysicalReviewE,64,p.046135.[24]Thadakamalla,H.P.,R.Albert,andS.R.T.Kumara(2005)Searchinweightedcomplexnetworks,"PhysicalReviewE,72,p.066128.[25]Lawrence,S.andC.L.Giles(1999)Accessibilityofinformationontheweb,"Nature,400,pp.107{109. 100[26]Gulli,A.andA.Signorini(2005)Theindexablewebismorethan11.5billionpages,"inWWW'05:Specialinteresttracksandpostersofthe14thinternationalconferenceonWorldWideWeb,ACMPress,NewYork,USA,pp.902{903.[27]Page,L.,S.Brin,R.Motwani,andT.Winograd(1998)ThePageR-ankCitationRanking:BringingOrdertotheWeb,Tech.rep.,StanfordDig-italLibraryTechnologiesProject.URLciteseer.ist.psu.edu/page98pagerank.html[28]Kleinberg,J.M.(1999)Authoritativesourcesinahyperlinkedenviron-ment,"JournaloftheACM,46(5),pp.604{632.[29]Jeong,H.,S.Mason,A.-L.Barabasi¶,andZ.Oltvai(2001)Lethalityandcentralityofproteinnetworks,"Nature,411,pp.41{42.[30]Albert,I.andR.Albert(2004)Conservednetworkmotifsallowforprotein-proteininteractionprediction,"Bioinformatics,20(18).[31]Albert,R.(2007)NetworkInference,Analysis,andModelinginSystemsBiology,"ThePlantCell,19,pp.3327{3328.[32]Thadakamalla,H.P.,U.N.Raghavan,S.Kumara,andR.Albert(2004)SurvivabilityofMultiagent-BasedSupplyNetworks:ATopologicalPerspective,"IEEEIntelligentSystems,19(5),pp.24{31.[33]Kumara,S.(2005)PSU-IAI¯nalreportonDarpaUltra*Log,Tech.rep.,ThePennsylvaniaStateUniversity.[34]Akyildiz,I.F.,W.Su,Y.Sankarasubramaniam,andE.Cayirci(2002)Wirelesssensornetworks:Asurvey,"ComputerNetworks,38(4),pp.393{422.[35]Culler,D.(2001).URLhttp://webs.cs.berkeley.edu/800demo/eetimes.html;http://webs.cs.berkeley.edu/800demo/[36]Albert,R.andA.L.Barabasi¶(2000)TopologyofEvolvingNetworks:LocalEventsandUniversality,"Phys.Rev.Lett.,85(24),pp.5234{5237.[37]Thadakamalla,H.P.,R.Albert,andS.R.T.KumaraOperationsResearchandManagementScienceHandbook,chap.ComplexityandLarge-scaleNetworks,CRCpress,inprint. 101[38]Blough,D.M.,M.Leoncini,G.Resta,andP.Santi(2006)Thek-NeighborsApproachtoInterferenceBoundedandSymmetricTopologyControlinAdHocNetworks,"IEEETransactionsonMobileComputing(toappear).[39]Ottino,J.M.(2004)Engineeringcomplexsystems,"Nature,427(399).[40]Girvan,M.andM.Newman(2002)Communitystructureinsocialandbiologicalnetworks,"ProceedingsofNationalAcademyofSciences,99,pp.7821{7826.[41]Guimera,R.µandL.Amaral(2005)Functionalcartographyofcomplexmetabolicnetworks,"Nature,433,pp.895{900.[42]Danon,L.,A.D¶³az-Guilera,andA.Arenas(2006)Thee®ectofsizeheterogeneityoncommunicationidenti¯cationincomplexnetworks,"JournalofStatisticalMechanics:TheoryandExperiment,p.P11010.[43]Eckermann,J.andE.Moses(2002)Curvatureofco-linksuncovershiddenthematiclayersintheWorldWideWeb,"ProceedingsofNationalAcademySciences,99,pp.5825{5829.[44]Flake,G.,S.Lawrence,andC.Giles(2000)E±cientIdenti¯cationofWebCommunities,"Proceedingsofthe6thACMSIGKDD,pp.150{160.[45]Gustafsson,M.,M.Hornquist,andA.Lombardi(2006)Comparisonandvalidationofcommunitystructuresincomplexnetworks,"PhysicaA:StatisticalMechanicsanditsApplications,367,pp.559{576.[46]Hastings,M.(2006)CommunityDetectionasanInferenceProblem,"PhysicalReviewE,74,p.035102(R).[47]Newman,M.E.J.andM.Girvan(2004)Findingandevaluatingcom-munitystructureinnetworks,"PhysicalReviewE,69,p.026113.[48]Radicchi,F.,C.Castellano,F.Cecconi,V.Loreto,andD.Parisi(2004)De¯ningandidentifyingcommunitiesinnetworks,"ProceedingsofNationalAcademyofSciences,101,pp.2658{2663.[49]Clauset,A.,M.Newman,andC.Moore(2004)Findingcommunitystructuresinverylargenetworks,"PhysicalReviewE,70,p.066111.[50]Arenas,A.,L.Danon,A.D¶³az-Guilera,P.Gleiser,andR.Guimeraµ(2004)Communityanalysisinsocialnetworks,"EuropeanPhysicsJournalB,38,pp.373{380. 102[51]Watts,D.(1999)Small-worlds:ThedynamicsofNetworksbetweenorderandrandomness,PrincetonUniversityPress.[52]Philips,T.K.,S.S.Panwar,andA.N.Tantawi(1989)Connec-tivityPropertiesofPacketRadioNetworkModel,"IEEETransactionsonInformationTheory,35(5),pp.1044{1047.[53]Penrose,M.D.(1999)OnK-ConnectivityforaGeometricRandomGraph,"RandomStructuresandAlgorithms,15(2),pp.145{164.[54]Takagi,H.andL.Kleinrock(1984)OptimalTransmissionRangesforRandomlyDistributedPacketRadioTerminals,"IEEETransactionsonCommunications,32(3),pp.246{257.[55]Kleinrock,L.andJ.Silvester(1978)OptimumTransmissionRadiiforPacketRadioNetworksorWhySixisaMagicNumber,"intheProceedingsofIEEENationalTelecommunicationsConference,pp.4.3.1{4.3.5.[56]Gupta,P.andP.R.Kumar(1998)StochasticAnalysis,Control,Opti-mizationandApplications:AVolumeinHonorofW.H.Fleming,chap.Criticalpowerforasymptoticconnectivityinwirelessnetworks,Birkhauser,Boston,pp.547{566.[57]Xue,F.andP.R.Kumar(2004)TheNumberofNeighborsNeededforConnectivityofWirelessNetworks,"WirelessNetworks,10,pp.169{181.[58]Blough,D.,M.Leoncini,G.Resta,andP.Santi(2003)Thek-NeighProtocolforSymmetricTopologyControlinAdHocNetworks,"intheProceedingsofIEEEMobiHoc,pp.141{152.[59]Milgram,S.(1967)Thesmallworldproblem,"PsychologyToday,2,pp.60{67.[60]Adamic,L.A.(1999)TheSmallWorldWeb,"inProc.3rdEuropeanConf.ResearchandAdvancedTechnologyforDigitalLibraries,ECDL(S.AbiteboulandA.-M.Vercoustre,eds.),1696,Springer-Verlag,pp.443{452.[61]Vazquez,A.,R.Pastor-Satorras,andA.Vespignani(2002),Internettopologyattherouterandautonomoussystemlevel,".URLhttp://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/0206084[62]Ravasz,E.,A.L.Somera,D.A.Mongru,S.N.Oltvai,andA.-L.Barabasi(2002)HierarchicalOrganizationofModularityinMetabolicNetworks,"Science,297(5586),pp.1551{1555.[63]Rudin,W.(1986)RealandComplexAnalysis,3ed.,McGraw-HillSci-ence/Engineering/Math. 103[64]Newman,M.E.J.(2003)Mixingpatternsinnetworks,"PhysicalReviewE,67(2),p.026126.[65]Hogg,R.V.,J.W.McKean,andA.T.Craig(2005)IntroductiontoMathematicalStatistics,PearsonPrenticeHall,USA.[66]Newman,M.E.J.(2004)Fastalgorithmfordetectingcommunitystruc-tureinnetworks,"PhysicalReviewE,69,p.066133.[67]Zachary,W.(1977)Aninformation°owmodelforcon°ictand¯ssioninsmallgroups,"JournalofAnthropologicalResearch,33,pp.452{473.[68]Newman,M.E.J.(2004)Detectingcommunitystructureinnetworks,"EuropeanPhysicalJournalB,38,pp.321{330.[69]Meester,R.andR.Roy(1996)ContinuumPercolation,CambridgeUni-versityPress,Cambridge,UK.[70]Molloy,M.andB.Reed(1995)Acriticalpointforrandomgraphswithagivendegreesequence,"inRandomGraphs93:ProceedingsofthesixthinternationalseminaronRandomgraphsandprobabilisticmethodsincombinatoricsandcomputerscience,pp.161{179.[71]Newman,M.E.J.,S.H.Strogatz,andD.J.Watts(2001)Randomgraphswitharbitrarydegreedistributionsandtheirapplications,"PhysicalReviewE,64,p.026118.[72]Anderson,C.,S.Wasserman,andB.Crouch(1999)Ap¤primer:Logitmodelsforsocialnetworks,"SocialNetworks,21(1),pp.37{66.[73]Frank,O.andD.Strauss(1986)Markovgraphs,"J.AmericanStatis-ticalAssociation,81,pp.832{842.[74]Holland,P.W.andS.Leinhardt(1981)Anexponentialfamilyofprobabilitydistributionsfordirectedgraphs,"J.AmericanStatisticalAsso-ciation,76,pp.33{65.[75]Strauss,D.(1986)Onageneralclassofmodelsforinteraction,"SIAMReview,28,pp.513{527.[76]Snijders,T.A.B.(2002)MarkovchainMonteCarloestimationofex-ponentialrandomgraphmodels,"J.SocialStructure,3(2),pp.1{40.[77]Wasserman,S.andP.Pattison(1996)Logitmodelsandlogisticre-gressionsforsocialnetworks1:AnintroductiontoMarkovrandomgraphsandp¤,"Psychometrika,61,pp.401{426. 104[78]Newman,M.E.J.(2000)Modelsofsmallworld,"JournalStatisticalPhysics,101,pp.819{841.[79]Barabasi,A.-L.¶andR.Albert(1999)Emergenceofscalinginrandomnetworks,"Science,286(5439),pp.509{512.[80]Bollobas,B.andO.Riordan(2003)HandbookofGraphsandNetworks,chap.Mathematicalresultsonscale-freegraphs,Wiley-VCH,Berlin.[81]Dorogovtsev,S.N.andJ.F.F.Mendes(2002)Evolutionofnet-works,"Adv.Phys.,51,pp.1079{1187.[82]Aiello,W.,F.Chung,andL.Lu(2000)ARandomGraphModelforMassiveGraphs,"Proceedingsofthethirty-secondannualACMsymposiumonTheoryofcomputing,pp.171{180.[83]|||(2001)Arandomgraphmodelforpowerlawgraphs,"ExperimentalMathematics,10(1),pp.53{66.[84]Albert,R.,H.Jeong,andA.L.Barabasi¶(2000)Attackanderrortoleranceofcomplexnetworks,"Nature,406(6794),pp.378{382.[85]Carreras,B.A.,V.E.Lynch,I.Dobson,andD.E.Newman(2002)Criticalpointsandtransitionsinanelectricpowertransmissionmodelforcascadingfailureblackouts,"Chaos,12(4),pp.985{994.[86]Sachtjen,M.L.,B.A.Carreras,andV.E.Lynch(2000)Distur-bancesinapowertransmissionsystem,"Phys.Rev.E,61(5),pp.4877{4882.[87]Kinney,R.,P.Crucitti,R.Albert,andV.Latora(2005)Model-ingCascadingFailuresintheNorthAmericanPowerGrid,"TheEuropeanPhysicalJournalB,46,p.101.[88]Motter,A.E.(2004)CascadeControlandDefenseinComplexNet-works,"Phys.Rev.Lett.,93(9),p.098701.[89]Moreno,Y.,J.B.Gomez,andA.F.Pacheco(2002)Instabilityofscale-freenetworksundernode-breakingavalanches,"Europhys.Lett.,58(4),pp.630{636.[90]Moreno,Y.,R.Pastor-Satorras,A.Vazquez,andA.Vespignani(2003)Criticalloadandcongestioninstabilitiesinscale-freenetworks,"Eu-rophys.Lett.,62(2),pp.292{298.[91]Wang,X.F.andJ.Xu(2004)Cascadingfailuresincoupledmaplattices,"Phys.Rev.E,70(5),p.056113. 105[92]Watts,D.J.(2002)Asimplemodelofglobalcascadesonrandomnet-works,"Proc.Natl.Acad.Sci.,99(9),pp.5766{5771.[93]Pastor-Satorras,R.andA.Vespignani(2001)Epidemicdynamicsandendemicstatesincomplexnetworks,"PhysicalReviewE,63(6),p.066117.[94]|||(2001)EpidemicSpreadinginScale-FreeNetworks,"PhysicalRe-viewLetters,86,pp.3200{3203.[95]|||(2002)Epidemicdynamicsin¯nitesizescale-freenetworks,"Phys-icalReviewE,65(3),p.035108.[96]|||(2003)HandbookofGraphsandNetworks,chap.Epidemicsandim-munizationinscale-freenetworks,Wiley-VCH,Berlin.[97]Vogels,W.,R.vanRenesse,andK.Birman(2003)Thepowerofepidemics:robustcommunicationforlarge-scaledistributedsystems,"SIG-COMMComput.Commun.Rev.,33(1),pp.131{135.[98]Eguiluz,V.M.andK.Klemm(2002)Epidemicthresholdinstructuredscale-freenetworks,"PhysicalReviewLetters,89,p.108701.[99]Rozenfeld,A.F.,R.Cohen,D.Ben-Avraham,andS.Havlin(2002)Scale-freeNetworksonLattices,"PhysicalReviewLetters,89,p.218701.[100]Warren,C.P.,L.M.Sander,andI.M.Sokolov(2002)GeographyinaScale-FreeNetworkModel,"PhysicalReviewE,66,p.056105.[101]Pastor-Satorras,R.andA.Vespignani(2002)Immunizationofcom-plexnetworks,"PhysicalReviewE,65(3),p.036104.[102]Cohen,R.,S.Havlin,andD.Ben-Avraham(2003)E±cientImmu-nizationStrategiesforComputerNetworksandPopulations,"PhysicalRe-viewLetters,91,p.247901.[103]Thadakamalla,H.P.,R.Albert,andS.R.T.Kumara(2007)Searchinspatialscale-freenetworks,"NewJournalofPhysics,9,p.190.[104]Kleinberg,J.(2000)Navigationinasmallworld,"Nature,406,p.845.[105]|||(2006)ComplexNetworksandDecentralizedSearchAlgorithms,"ProceedingsoftheInternationalCongressofMathematicians,3,pp.1019{1044.[106]Danon,L.,A.Arenas,andA.D¶³az-Guilera(2008)Impactofcom-munitystructureoninformationtransfer,"PhysicalReviewE,77(036103). 106[107]Bharathidasan,A.andV.A.S.Ponduru(2005)SensorNetworks:AnOverview,"http://www.cs.binghamton.edu/»kliu/survey.pdf.[108]Szewczyk,R.,A.Mainwaring,J.Polastre,J.Anderson,andD.Culler(2004)Ananalysisofalargescalehabitatmonitoringap-plication,"inSenSys'04:Proceedingsofthe2ndinternationalconferenceonEmbeddednetworkedsensorsystems,ACM,NewYork,NY,USA,pp.214{226.[109]Krishnamachari,B.,S.B.Wicker,R.Bejar,andM.Pearlman(2002)Communications,InformationandNetworkSecurity,chap.CriticalDensityThresholdsinDistributedWirelessNetworks,Kluwerpublishers.[110]Quantanilla,J.,S.Torquato,andR.M.Ziff(2000)E±cientmeansurementofthepercolationthresholdforfullypenetrablediscs,"Jour-nalofPhysicsA:MathematicsandGeneral,33,pp.L399{L407.[111]Penrose,M.D.(2003)RandomGeometricGraphs,Oxfordstudiesinprob-ability,OxfordUniversitypress,Oxford.[112]Franceschetti,M.,L.Booth,M.Cook,R.Meester,andJ.Bruck(2003)Percolationinmulti-hopwirelessnet-works,"IEEETransactionsonInformationTheory,submitted(http://www.paradise.caltech.edu/papers/etr055.pdf).[113]Dall,J.andM.Christensen(2002)RandomGeometricGraphs,"Phys-icalReviewE,66(016121).[114]Quantanilla,J.(2001)Meansurementofpercolationthresholdforfullypenetrablediscsofdi®erentradii,"PhysicaReviewE,061108,pp.L399{L407.[115]Karger,D.(2000)Minimumcutsinnearlineartime,"JournaloftheACM,47(1),pp.46{76.[116]Kernighan,B.andS.Lin(1970)Ane®ectiveheuristicprocedureforpartitioninggraphs,"TheBellSystemTechnicalJournal,29,pp.291{307.[117]Fiduccia,C.andR.Mattheyses(1982)Alinear-timeheuristicforim-provingnetworkpartitions,"Proceedingsof19thAnnualACMIEEEDesignAutomationConference,pp.175{181.[118]Hendrickson,B.andR.Leland(1995)Animprovedspectralgraphpartitioningalgorithmformappingparallelcomputations,"SIAMJournalonScienti¯cComputing,16(2),pp.452{469. 107[119]Stoer,M.andF.Wagner(1997)Asimplemin-cutalgorithm,"JournaloftheACM,44(4),pp.585{591.[120]Thompson,C.(1979)Area-timecomplexityforVLSI,"Proceedingsof11thannualACMsymposiumonTheoryofComputing,pp.81{88.[121]Pons,P.andM.Latapy(2005)Computingcommunitiesinlargenet-worksusingrandomwalks,"E-printphysics/0512106.[122]Duch,J.andA.Arenas(2005)Communitydetectionincomplexnet-worksusingextremaloptimization,"PhysicalReviewE,72,p.027104.[123]Newman,M.E.J.(2006)Findingcommunitystructureinnetworksusingtheeigenvectorsofmatrices,"PhysicalReviewE,74,p.036104.[124]Wu,F.andB.Huberman(2004)Findingcommunitiesinlineartime:aphysicsapproach,"TheEuropeanPhysicalJournalB,38(2),pp.331{338.[125]Bagrow,J.andE.Bollt(2005)Localmethodfordetectingcommuni-ties,"PhysicalReviewE,72,p.046108.[126]Costa,L.(2004)Hubbasedcommunity¯nding,"E-printcond-mat/0405022.[127]Milligan,G.andD.Schilling(1985)AsymptoticandFiniteSampleCharacteristicsofFourExternalCriterionMeasures,"MultivariateBehav-ioralResearch,20(1),pp.97{109.[128]Hansen,P.andB.Jaumard(1997)Clusteranalysisandmathematicalprogramming,"Mathematicalprogramming,79,pp.191{215.[129]Gfeller,D.,J.Chappelier,andP.Rios(2005)Findinginstabilitiesinthecommunitystructureofcomplexnetworks,"PhysicalReviewE,72,p.056135.[130]Wilkinson,D.andB.Huberman(2004)Amethodfor¯ndingcommu-nitiesofrelatedgenes,"ProceedingsofNationalAcademyofSciences,101,pp.5241{5248.[131]Appel,M.andR.Russo(2002)Theconnectivityofagraphonuniformpointson[0;1]d,"ReviewsofModernPhysics,60,pp.351{357.[132]Hou,T.andV.O.K.Li(1986)TransmissionRangeControlinMultihopPacketRadioNetworks,"IEEETransactionsonCommunications,34(1),pp.38{44. 108[133]Avram,F.andD.Bertsimas(1993)OnCentralLimitTheoremsinGeometricalProbability,"TheAnnalsofAppliedProbability,3(4),pp.1033{1046.[134]Booth,L.,J.Bruck,M.Fransceschetti,andR.Meester(2003)Coveringalgorithms,continuumpercolationandthegeometryofwirelessnetworks,"TheAnnalsofAppliedProbability,13(2),pp.722{741.[135]Glauche,I.,W.Krause,R.Sollacher,andM.Greiner(2003)Con-tinuumpercolationofwirelessadhoccommunicationnetworks,"PhysicaA,325,pp.577{600.[136]Raghavan,U.,H.Thadakamalla,andS.Kumara(2005)PhaseTran-sitionsandConnectivityofDistributedWirelessSensorNetworks,"inPro-ceedingsofAdvancedcomputingandcommunications'05,Coimbatore,India,pp.10{15.[137]Rodoplu,V.andT.H.Meng(1999)Minimumenergymobilewirelessnetworks,"IEEEJournalonSelectedAreasinCommunications,17(8),pp.1333{1344.[138]Li,N.,J.C.Hou,andL.Sha(2003)DesignandanalysisofanMST-basedtopologycontrolalgorithm,"intheProceedingsofIEEEINFOCOM,3,pp.1702{1712.[139]Li,L.,J.Y.Halpern,P.Bahl,Y.M.Wang,andR.Wattenhofer(2001)Analysisofacone-baseddistributedtopologycontrolalgorithmforwirelessmulti-hopnetworks,"intheProceedingsoftheACMsymposiumonPrinciplesofdistributedcomputing,pp.264{273.[140]Cressie,A.C.N.(1991)Statisticsforspacialdata,Wileyseriesinprob-abilityandmathematicalstatistics,JohnWileyandSons,USA.[141]Wu,F.andB.Huberman(2004)SocialStructureandOpinionFormation,ComputationalEconomics0407002,EconWPA,availableathttp://ideas.repec.org/p/wpa/wuwpco/0407002.html.[142]Mislove,A.,M.Marcon,K.Gummadi,P.Druschel,andB.Bhat-tacharjee(2007)MeasurementandAnalysisofOnlineSocialNetworks,"inIMC'07:Proceedingsofthe7thACMSIGCOMMconferenceonInternetmeasurement,pp.29{42.[143]Garfield,E.(1970)Citationindexingforstudyingscience,"Nature,227(5259),pp.669{671. 109[144]Wang,J.,H.Bi,andD.Lin(2007)ComprehensiveCitationIndexforRe-searchNetworks,"IEEETransactionsonKnowledgeandDateEngineering(underreview).[145]Nanavati,A.,S.Gurumurthy,G.Das,D.Chakraborty,K.Das-gupta,S.Mukherjea,andA.Joshi(2006)Onthestructuralpropertiesofmassivetelecomcallgraphs:¯ndingsandimplications,"inCIKM'06:Proceedingsofthe15thACMinternationalconferenceonInformationandknowledgemanagement,ACM,NewYork,NY,USA,pp.435{444.[146]Harary,F.(1969)GraphTheory,Addison-Wesley,Reading,MA.[147]Wu,T.andS.Biswas(15April2005)Aself-reorganizingslotallocationprotocolformulti-clustersensornetworks,"InformationProcessinginSensorNetworks,2005.IPSN2005.FourthInternationalSymposiumon,pp.309{316.[148]Bandyopadhyay,S.andE.Coyle(2003)Anenergye±cienthierarchi-calclusteringalgorithmforwirelesssensornetworks,"inProceedingsofthe22ndAnnualJointConferenceoftheIEEEComputerandCommunicationsSocieties(Infocom2003).URLciteseer.ist.psu.edu/bandyopadhyay03energy.html[149]Gupta,G.andM.Younis(March2003)Fault-tolerantclusteringofwirelesssensornetworks,"WirelessCommunicationsandNetworking,2003.WCNC2003.2003IEEE,3,pp.1579{1584.[150]Lee,S.,J.Yoo,andT.Chung(2004)Distance-BasedEnergyE±cientClusteringforWirelessSensorNetworks,"inLCN'04:Proceedingsofthe29thAnnualIEEEInternationalConferenceonLocalComputerNetworks,IEEEComputerSociety,Washington,DC,USA,pp.567{568.[151]Younis,O.andS.Fahmy(2004)HEED:AHybrid,Energy-E±cient,Dis-tributedClusteringApproachforAdHocSensorNetworks,"IEEETransac-tionsonMobileComputing,3(4),pp.366{379. VitaUshanandiniRaghavanEducationThePennsylvaniaStateUniversity,UniversityPark,PA,USAPh.D.,IndustrialEngineeringandOperationsResearch,August2008(expected)M.S.,IndustrialEngineeringandOperationsResearch,December2005IndianInstituteofTechnologyMadras,Chennai,IndiaM.Sc.,Mathematics,July2002UniversityofMadras,Chennai,IndiaB.Sc.,Mathematics,July2000AcademicdistinctionsandHonors1.ReceivedafellowshipfromtheInstituteofMathematicalSciences,Taramani,IndiaforgraduatestudiesinMathematics(0.01%selectionrate)2.ReceivedtheGeneralPro¯ciencyawardsforthesecondandthirdyearsofmyundergraduatestudiesSelectedpublications1.U.N.Raghavan,R.AlbertandS.Kumara,Nearlineartimealgorithmtodetectcommunitystructuresfromlarge-scalenetworks",Phys.Rev.E,76(036106),2007.2.U.N.RaghavanandS.Kumara,Decentralizedtopologycontrolalgorithmsforconnectivityofdistributedwirelesssensornetworks",Int.J.ofSensorNetworks,2(3/4),pp.201-210,2007.3.U.N.Raghavan,H.P.ThadakamallaandS.Kumara,Phasetransitionsandcon-nectivityindistributedwirelesssensornetworks",inProceedingsofADCOM'05,pp.10-15,Coimbatore,India,2005.4.A.Surana,S.Kumara,M.GreavesandU.N.Raghavan,Supplychainnetworks:acomplexadaptivesystemsperspective",Int.J.ofProductionResearch,43(10),pp.4235-4265,2005.5.H.P.Thadakamalla,U.N.Raghavan,S.KumaraandR.Albert,SurvivabilityofMulti-AgentBasedSupplyNetworks:ATopologicalPerspective",IEEEIntelli-gentSystems,19(5),pp.24-31,2004.