Algorithms for discovering communities in complex networks.pdf

《Algorithms for discovering communities in complex networks.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ALGORITHMSFORDISCOVERINGCOMMUNITIESINCOMPLEXNETWORKSbyHEMANTBALAKRISHNANB.E.BharathiarUniversity,2000M.S.UniversityofTexasatDallas,2002AdissertationsubmittedinpartialfulfillmentoftherequirementsforthedegreeofDoctorofPhilosophyintheSchoolofElectricalEngineeringandComputerScienceintheCollege

2、ofEngineeringandComputerScienceattheUniversityofCentralFloridaOrlando,FloridaFallTerm2006MajorProfessor:NarsinghDeoUMINumber:3242418UMIMicroform3242418Copyright2007byProQuestInformationandLearningCompany.Allrightsreserved.ThismicroformeditionisprotectedagainstunauthorizedcopyingunderTitle1

3、7,UnitedStatesCode.ProQuestInformationandLearningCompany300NorthZeebRoadP.O.Box1346AnnArbor,MI48106-1346ABSTRACTIthasbeenobservedthatreal-worldrandomnetworksliketheWWW,Internet,socialnetworks,citationnetworks,etc.,organizethemselvesintoclosely-knitgroupsthatarelocallydenseandgloballysparse

4、.Theseclosely-knitgroupsaretermedcommunities.Nodeswithinacommunityaresimilarinsomeaspect.ForexampleinaWWWnetwork,communitiesmightconsistofwebpagesthatsharesimilarcontents.Miningthesecommunitiesfacilitatesbetterunderstandingoftheirevolutionandtopology,andisofgreattheoreticalandcommercialsig

5、nificance.Communityrelatedresearchhasfocusedontwomainproblems:communitydiscoveryandcommunityidentification.Communitydiscoveryistheproblemofextractingallthecommunitiesinagivennetwork,whereascommunityidentificationistheproblemofidentifyingthecommunity,towhich,agivensetofnodesbelong.Wemakeaco

6、mparativestudyofvariousexistingcommunity-discoveryalgorithms.Wethenproposeanewalgorithmbasedonbibliographicmetrics,whichaddressesthedrawbacksinexistingapproaches.Bibliographicmetricsareusedtostudysimilaritiesbetweenpublicationsinacitationnetwork.Ouralgorithmclassifiesnodesinthenetworkbased

7、onthesimilarityoftheirneighborhoods.Oneofthedrawbacksofthecurrentcommunity-discoveryalgorithmsistheircomputationalcomplexity.Thesealgorithmsdonotscaleuptotheenormoussizeofthereal-worldnetworks.Weproposeahash-table-basedtechniquethathelpsuscomputethebibliometri