DOC

Identifying Functional Modules in Complex Networks

By Jorge Diaz,2014-06-02 00:24
7 views 0
Identifying Functional Modules in Complex Networksin

    Identifying Functional Modules in Complex

    Networks

    Commun.Theor.Phys.(Beijing,China)48(2007)PP.957960

    ?InternationalAcademicPublishersVo1.48,No.5,November15,2007

    IdentifyingFunctionalModulesinComplexNetworks

    LIKePing

    StateKeyLaboratoryofRailTrafficControlandSafety,BeijingJiaotongUniversity,Beijing100044,China

    (ReceivedNovember1,2006)

    AbstractInthispaper.weproposeanewmethodthatenablesustodetectanddescribethenctionajmodulesin

    c0mplexnetworks.Usingtheproposedmethod,wecanclassifythenodesofnetworksintodifferentmodulesaccording

    t0theirpatternofintraandextra

    modulelinks.WeuseourmethodtoanalyzethemodularstructuresoftheER

    randomnetworks.Wefindthatdifferentmodulesofnetworkshavedifferentstructureproperties,suchastheclustering

    c0e

    cient.Moreover.atthesametime,manynodesofnetworksparticiF'atedifferentmodules.Remarkably,wefind

    thatintheERrandomnetworks,whentheprobabilityPissmall,differentmodulesordifferentrolesofnodescanbe

    identedbydifferentregionsinthec-pparameterspace.

    PACSnumbers:89.75.Fb,89.75.Da

    Keywords:complexnetworks,modularstructure,clusteringcoefficient 1Introduction

    Inthestudiesofcomplexnetworks,themodular

propertiesofnetworkshavebeenwidelyreportedinso

    cialnetworks[1,2]biochemicalnetworks, [3,foodwebs,

    [5]

    andtheInternet,【引etc.Recently,anumberofmethods wereproposedtounderstandthepropertiesofthemod

    ularstructure,suchasthestatistical,mathematicaland modelbasedanalysismethods.However,manyproperties ofthemodularnetworksremainunknown.Whatarethe mechanismsbywhichmodularityemergesincomplexnet

    works?Howtoidentifythemodulesofagivennetwork? AswritteninRef.7],"agenerallyaccepteddefinitionof amoduledoesnotexistanddifierentauthorsusethecon

    ceptinquitedifierentways".

    Themodulesofnetworksusuallyrepresentthefunc

    tionalunits,suchasthesocialgroupsandbiologicalmod

    ules.Inordertodetectanddescribethemodulesincom

    plexnetworksanumberofeffortshavebeenmadefFor areview,seeRef.8]).NewmanandGirvanproposedthe clusteringalgorithminRefs.2]and[9]jwherethequan

    titativedefinitionofmodularitywasfirstlyintroduced. RadicchiandCastellanoeta1.presentedanapproach. whichisbasedonthecomparisonbetweenthenumberof internallinksandthenumberofexternallinks.[10]Donetti andMufiozproposedanalgorithmthatcombinesspec

    tralmethodswithclusteringtechniques.l1JZiv.Midden

    dorf,andWigginsoutlinedaninformationtheoreticalal

    gorithmbyapplyingtheinformationbottleneckonprob

    abilitydistributions.[]Accordingtothesimilarproper

tiesofnodes,reference131usedtheparameterswithin

    moduledegreeandparticipationcoecienttodetectthe

    functionalmodulesinmetabolicnetworks.

    Inthispaper,adifferentmethodisproposed,which canbeusedtofindanddescribethefunctionalmodules incomplexnetworks.Here.weinvestigatethefunctional modulesaccordingtotherolesthatthenodesofnetworks fulfil.Tweparametersareintroducedtodescribetileroles ofnodes,i.e.,theparametersCsiand.Themodulesof networkscanbeidentifiedbydifferentparameters,such asthemoduleclusteringcoecientandmoduledegree

    etc.Thepaperisorganizedasfollows:weintroducethe proposedmethodinSec.2:thenumericalandanalyti

    calresultsarepresentedinSec.3:finally.conclusionsare presented.

    2PreposedMethod

    Inthefunctionalpropertiesofcomplexnetworks.mod

    ulesplayacentralrole.Ingenera1.theconceptofmod

    uleisbasedontheclassificati0nofobects.Morefunda- mentally,amodulemainlymeansthatthenodesconsti

    tutingthemodulefulfilthesamerole.Therearemainly twotypesofthedefinitionofmodule,i.e.,theself-referring andcomparativedefinitions.[2,10,14]Accordingtotheselh referringdefinition,amoduleisdefinedasasubgroupof agraphcontainingmorethantwonodeswhereallthe nodesarelinkedtoeachother.Thecomparativedefini

    tionmeansthatcomparingthenumberofinternallinksto thenumberofexternallinks.amodulewillbedenserthan itssurroundings.Infact,thesedefinitionsofthemodule ofnetworksareonlybasedonthenumberofthelinksof

thenodes.

    Inpracticalcases,thenodesplayingthesameroleor constitutingamodulearenotnecessarytohavehigher linksamongthem.Thismeansthatinmanycases.we cannotdetectthemodulesbycomparingthenumberof TheprojectsupportedbytheStateKeyBasicResearchProgramofChinaunderGrantNo.200

    6CB705500,NationalNaturalScience

    FoundationofChinaunderGrantNo.60634010,andtheScienceandTechnologyFoundation

    ofBeijingJiaotongUniversityunderGrant

    No.2006RC044andNewCenturyExcellentTalentsinUniversityunderGrantNo.NCEF

    060074

958LIKePingV01.48

    1inks.Moreover,aspointedinRef.13I,"twonodeswith

    thesamezscorewil1playdifierentroles"wherezscore measureshowwel1connectednodeistoothernodesin themodule.Figure1showsanexample.Hereweassume thattheroleofnodesistoconstitutethepolygon.In Fig.1,nodes1,2,and4constituteatriangle,andnodes 1,2,3,and4constituteaquadrangle.Thismeansthat thenetworkshowninFig.1containstwomodules.One ofthemisconstitutedbythenodes1,2,and3,andthe otherisconstitutedbythenodes1,2,3,and4.nom Fig.1,wecanfindthat(i)itisdimculttodetectamod ulebythenumberofthe1inksofnodes;fii1thesamenode possiblyparticipatesdifferentmodules,suchasthenode 1.ItshouldbeemphasizedthatinFig.1.whetherthe nodesconstituteamoduleis

    constituteapolygon,andis

    linksamongthem.

basedonwhetherthenodes

    notbasedonthenumberof

    Fig.1Anexampleofthepolygons

    Itiswidelybelievedthatincomplexnetworks.the linksofnodesarebasedontherolesthatthesenodes flxlfil.Whenweconsiderthemodulesofanetwork,the identificationofthemodulesshouldbeestablishedonthe linksofnodes.However,asmentionedabove,thenodes constitutingamoduledonothavetohavehigher1inks amongthem,andthesamenodespossiblyparticipatedif- ferentmodules.Here,weproposeanewmethodtodetect themodulesofnetworks.Theproposedmethodisdirectly basedontherolesthatthenodesofnetworksfulfil.Oor definitionofmoduleisasfollows.Thefirststepistode finetherolesofnodesinanetwork.Thenonthebasis oftherolesofthenodesweclassifythenodesinthenet. workintosomeportions.Theseportionsareregardedas themodulesofthenetwork.

    Inanetwork,therolesofnodescanbedefinedin advance.Forexampleinasocia1network,therolesof nodescanbedefinedasthepeople'sinterestorOCCU pation.Basedontherolesofnodes,wecandetermine whichmodulethenodesofthenetworkbelongto.Inour method,weintroducetwoparametersCsiand,and usthemtodescribethelinksofthenodesiinthemod ulesCsiisdefinedasCsi=osi|ostwhereosiisthe numberoflinkspresentamongtheneighborsofthenode iinthemodules,andosisthemaximumpossiblenumber oflinksamongtheneighborsofthenodeiinthemodule s.isdefinedas=ks/,whereks{isthenumber

    ofthe1inksofthenodesiinthemodulesandisthe numberofthe1inksofthenodesiinthetota1network. 3NumericalSimulations

    In1960s,ErdSsandRdnyiproposedanetworkmodel, whichiscalledERrandomgraph.[15]SinceERrandom graphcandescribethepracticalnetworks,ithasbeencon

    sideredasabasictheoryofthetopologyofcomplexnet

    works.Totesttheperformanceofthemethodproposedin thispaper,weestablishtheERrandomnetworks.Each networkiscomprisedof?nodes.whicharethepointsat

    randomlyselectedpositionsonaring.EachnodeiSlinked toothernodeswithprobabilityP.Figure2displaysanex

    ampleoftherandomnetworks.HeretheparameterNis settobeN=10.

    7

    Fig.2AnexampleoftheERrandomnetworksforP0.1 Accordingtothedefinitionofthemoduleproposedin thispaper,thesamenodecanfulfildifferentrolesina network.Thismeansthatatthesametime,onenode ispossibletobelongtodifferentmodules.Westartwith therandomnetworkshowninFig.2.Heretheroleof nodesistoconstitutethepolygons.FromFig.2,wecan findthatmanytypesofthepolygonOccur.Forexample, nodes6,8,and9constituteatriangle,andnodes1,6,7, and8constituteaquadrangle.Inaddition,wefindthat inFig.2,somenodesconstitutedifferentpolygonsatthe sametime,suchasthenodes6and8.

    Amoduleofnetworkcanbeconsideredasthepattern thatiscomprisedbythesametypesofthepolygoninthe randomnetwork,suchasthetriangleorquadrangleetc.

    Figure3showsthemodularstructure,whichoccursin Fig.2.InFig.3,themodulewhichiscomprisedbythe trianglesisshowninFig.3(a),andthemodulewhichis comprisedbythequadranglesisshowninFig.3(b).From Fig.3,wecanseethatthenodesconstitutingthemod

    ulesshowninFig.3arepartofthoseshowninFig.2. TherearetwotrianglesinFig.3(a),andtwoquadrangles inFig.3(b).Itshouldbepointedoutthatinamodule

    No.5IdentifyingFunctionalModulesinComplexNetworks959 ofnetworkjanynodehasatleastonelinktoothernodesj butitisnotnecessaryforthemtohavehigherlinksamong them.

    Fig.3ThenetworkmodulescontainedinFig.2

    Inourmethod,wegiveadirectmannertodetectthe modulesinnetworks.Sometechniqueswhichareusedin otherworksarenotconsidered,suchastheoptimization ofmodularityandtheremovalofedges.Here.weusetwo parameterstodescribethemodulesinnetworksji.e.,Csi andi.WedefinetheparameterCs(),whichistheav

    erageofCsioverthenodeswithdegreekinthemodule8. Cs()iscalledthemoduleclusteringcoefficient.Figure4 showshowthemoduleclusteringcoemcientC(k)varies withthedegreeforN=100andP=0.05.Herethe

    horizontalaxisisthenodedegreeinthemodule8andthe verticalaxisisthemoduleclusteringcoemcient.

    ,

    

    1.5

1()

    ().5

    ().()

    1.5

    1()

    ().5

    ().(

    0203040

    0203040

    Fig.4PlotofCs()vs..(a)Thetrianglemodule (b)Thequadranglemodule.

    TheparameterCs()describesthetrianglerelation- shipsofthenodesinthemodule8.InFig.4(a),weshow thedistributionofthemoduleclusteringcoemcientfor thetrianglemodulef8=11,andthedistributionofthe moduleclusteringcoemcientforthequadranglemoduleis showninFig.4(b)(8=2).FromFig.4(a),wecaninfer thatthedistributionofthemoduleclusteringcoemcient showsapowerlawbehaviorwithCsfk).(k.wemake

    10suchmeasurements,andthenaverageoverthem.The exponent8isabout8=Q.97.Thistopologicalproperty ofthemodulestructureisconcurrentlythesameseenin Refs.[16and[17_However,inFig.4(b),thedistribution ofthemoduleclusteringcoemcientshowsthatthereare onlysmalldeviationsfromtheaverageoftheirvalues.If weincreasetheprobabilityP,thedistributionofthemod

    uleclusteringcoefficientshouldshowthesimilarpropertyj whichisshowninFig.4(b1.

    1()

    ().8

().6

    ()4

    P

    ().2

    1.1

    1.()

    0f)

    ()_8

    02()4()6()

    Node

    (b)

    02()4()6(

    Node

    Fig.5Distributionofthemoduledegree.(a)Thetri- anglemodule;(b)Thequadranglemodule.

    Theparametermeasureshowthelinksofthenode

    iareamongdifierentmodules.Hereitiscalledthemod

    uledegree.Ingeneral,thevalueofis0i1.

    Ifthelinksofthenodeiareallwithinitsownmodule 8,thevalueofisl_Figure5plotsthedistribution ofthemoduledegreeforN=100andP0.05.Here

    thehorizontalaxisrepresentsthenodesinthemodule8. andtheverticalaxisrepresentsthemoduledegree.In Fig.5(a),weshowthedistributionofthemoduledegree forthetrianglemodulef8=11,andthedistributionof themoduledegreeforthequadranglemoduleisshownin Fig.5(b)(8=2).FromFig.5(a),wecanfindthatthere areanumberofthenodeswhosevaluesofParesmaller than1.Thisresultmeansthatatthesametime,anum- berofthenodesinthetrianglemoduleparticipateother

960LIKePingVo1.48

    modules.But,inFig.5(b),thereareonlyafewnodes whosevaluesofaresmallerthan1.

    1()

    ()8

    ()6

    P

    ()4

    ().2

    ()()

    ().()().2().4().6().81.()

    C

    Fig.6RolesandregionsofnodesforN=100and P=0.05.Thepointslabelledby×denotethenodesthat

    participatethetrianglemodule,andthepointslabelled byodenotethenodesthatparticipatethequadrangle module.

    Findingmodulesincomplexnetworksisanextremely importanttask.Asmentionedabove,inourmethod,each nodeinanetworkcanbecharacterizedbytheparameters Csand.Inthec-pparameterspace,wecaniden

    tifythefunctionalmodules.Figure6displaystheregions ofthenodesforasmallerprobabilityP.Herethehori

    zontalaxisrepresentstheparameterst,andthevertical

    axisrepresentstheparameter.FromFig.6,itisob

    viousthatinthec-pparameterspace,difierentrolesof nodescanbeidentifiedbydifferentregions.InFig.6,we usealinetodistinguishthedifierentregions.Numerous References

Report this document

For any questions or suggestions please email
cust-service@docsford.com