Module identification in bipartite and directed networks

RogerGuimer`a,1MartaSales-Pardo,1andLu´ısA.NunesAmaral1

1

NorthwesternInstituteonComplexSystems(NICO)andDepartmentofChemicalandBiologicalEngineering,NorthwesternUniversity,Evanston,IL60208,USA

(Dated:February2,2008)

arXiv:physics/0701151v2 [physics.data-an] 7 Sep 2007Modularityisoneofthemostprominentpropertiesofreal-worldcomplexnetworks.Here,weaddresstheissueofmoduleidentificationintwoimportantclassesofnetworks:bipartitenetworksanddirectedunipartitenetworks.Nodesinbipartitenetworksaredividedintotwonon-overlappingsets,andthelinksmusthaveoneendnodefromeachset.Directedunipartitenetworksonlyhaveonetypeofnodes,butlinkshaveanoriginandanend.Weshowthatdirectedunipartitenetworkscanbeconvinientlyrepresentedasbipartitenetworksformoduleidentificationpurposes.Wereportanovelapproachespeciallysuitedformoduledetectioninbipartitenetworks,anddefineasetofrandomnetworksthatenableustovalidatethenewapproach.

PACSnumbers:.75.Hc,.75.-k,.65.-s,05.50.+q

Unitsinphysical,chemical,biological,technological,andsocialsystemsinteractwitheachotherdefiningcomplexnet-worksthatareneitherfullyregularnorfullyrandom[1,2,3].Amongthemostprominentandubiquitouspropertiesofthesenetworksistheirmodularstructure[2,4],thatis,theexistenceofdistinctgroupsofnodeswithanexcessofconnectionstoeachotherandfewerconnectionstoothernodesinthenet-work.

Theexistenceofmodularstructureisimportantinseveralregards.First,modulescriticallyaffectthedynamicbehaviorofthesystem.Themodularstructureoftheairtransportationsystem[5],forexample,islikelytoslowdownthespreadofvirusesataninternationalscale[6]andthussomewhatmin-imizetheeffectsofhigh-connectivitynodesthatmayother-wisefunctionas“super-spreaders”[7,8].Second,differ-entmodulesinacomplexmodularnetworkcanhavedifferentstructuralproperties[9].Therefore,characterizingthenet-workusingonlyglobalaveragepropertiesmayresultinthemisrepresentationofthestructureofmany,ifnotall,ofthemodules.Finally,themodularstructureofnetworksislikelyresponsibleforatleastsomeofthecorrelations(e.g.degree-degreecorrelations[10,11,12,13,14]),thathaveattractedtheinterestofresearchersinrecentyears[9].

Fortheabovereasons,considerableattentionhasbeengiventothedevelopmentofalgorithmsandtheoreticalframe-workstoidentifyandquantifythemodularstructureofnet-works(see[15]andreferencestherein).However,currentre-searchactivityhaspaidlittleattention,exceptforafewstudiesinsociology[16,17],totheproblemofidentifyingmodulesinaspecialandimportantclassofnetworksknownasbipartitenetworks(orgraphs).Nodesinbipartitenetworksaredividedintotwonon-overlappingsets,andthelinksmusthaveoneendnodefromeachset.Examplesofsystemsthataremoresuitablyrepresentedasbipartitenetworksinclude:

•Protein-proteininteractionnetworks[12,18,19,20]obtainedfromyeasttwohybridscreening:onesetofnodesrepresentsthebaitproteinsandtheothersetrep-resentsthepreyorlibraryproteins.Twoproteins,abaitandalibraryprotein,areconnectedifthelibraryproteinbindstothebait.

•Plant-animalmutualisticnetworks[21,22]:onesetrep-

resentsanimalspeciesandtheothersetrepresentsplantspecies.Linksindicatemutualisticrelationshipsbe-tweenanimalsandplants(forexample,acertainbirdspeciesfeedingonaplantspeciesanddispersingitsseeds).

•Scientificpublicationnetworks[23,24,25]:onesetrepresentsscientistsandtheothersetrepresentspub-lications.Alinkbetweenascientistandapublicationindicatesthatthescientistisoneoftheauthorsofthepublication.

•Artisticcollaborationnetworks[25,26,27]:onesetrepresentsartistsandtheotherteams.Alinkindicatestheparticipationofanartistinateam.

Anotherimportantclassofnetworksforwhichnosoundmoduleidentificationmethodsareavailableareunipartitedi-rectednetworks.Examplesofdirectedunipartitenetworksin-clude:

•Foodwebs[28,29]:nodesrepresentspeciesandlinksindicatetrophicinteractionsinanecosystem.

•Generegulatorynetworks[30]:nodesaregenesandlinksindicateregulatoryinteractions.

Theusualapproachtoidentifymodulesindirectednet-worksistodisregardthedirectionalityoftheconnections,whichwillfailwhendifferentmodulesaredefinedbasedonincomingandoutgoinglinks.

Here,weaddresstheissueofmoduleidentificationincom-plexbipartitenetworks.Westartbyreviewingtheapproachesthatarecurrentlyusedheuristicallyandaprioristicallytosolvethisproblem.Wethensuggestanewapproachespeciallysuitedformoduledetectioninbipartitenetworks,anddefineasetofrandomnetworksthatpermittheevaluationoftheac-curacyofthedifferentapproaches.Wethendiscusshowitispossibletousethesameformalismtoidentifymodulesindirectedunipartitenetworks.Ourmethodenablesonetoin-dependentlyidentifygroupsofnodeswithsimilaroutgoingconnectionsandgroupsofnodeswithsimilarincomingcon-nections.

I.

BACKGROUND

Forsimplicity,fromnowonwedenotethetwosetsofnodesinthebipartitenetworkasthesetofactorsandthesetofteams,respectively.Givenabipartitenetwork,weareinterestedinidentifyinggroups(modules)ofactorsthatarecloselyconnectedtoeachotherthroughco-participationinmanyteams.Ofcourse,oneisfreetoselectwhichsetofnodesinagivennetworkisthe“actorset”andwhichoneisthe“teamset,”soonecanidentifymodulesineitherorbothsetofnodes.

Werequireanymodule-identificationalgorithmtofulfilltwoquitegeneralconditions:(i)thealgorithmneedstobenetworkindependent;and(ii)giventhelistoflinksinthenet-work,thealgorithmmustdeterminenotonlyagoodpartitionofthenodesintomodules,butalsothenumberofmodulesandtheirsizes.

Thefirstconditionissomewhattrivial.Wejustmakeitex-plicittoexcludealgorithmsthataredesignedtoworkwithaparticularnetworkorfamilyofnetworks,butthatwillother-wisefailwithbroadfamiliesofnetworks(forexample,largenetworksorsparse/densenetworks).

Thesecondconditionismuchmoresubstantial,asitmakesclearthedifferencebetweenthemodule-identificationprob-lemandthegraphpartitioningproblemincomputerscience,inwhichboththenumberofgroupsandthesizesofthegroupsarefixed.Touseaunipartitenetworkanalogy,givenasetof120peopleattendingaweddingandinformationaboutwhoknowswhom,thegraphpartitioningproblemisanalogoustooptimallysetting12tableswith10peopleineachtable.Incontrast,themodule-identificationproblemisanalogoustoidentifying“natural”groupsofpeople,forexamplethedif-ferentfamiliesordistinctgroupsoffriends.

Thesecondconditionalsoexcludesalgorithms(based,forexample,onhierarchicalclusteringorprincipalcom-ponentanalysis[31])thatprojectnetworkdataintosomelow-dimensionalspacewithoutspecifyingthelocationoftheboundariesseparatingthegroups.Forexample,givenaden-dogramgeneratedusinghierarchicalclustering,onestillneedstodecidewhereto“cutit”inordertoobtaintherelevantmod-ules.Tobesure,onecanproposeacombinationofalgorithmsthatfirstprojectthedataintosomelow-dimensionalspaceandthensettheboundaries,andassesstheaccuracyofthemethod.Ingeneral,however,onecannotevaluatetheperformanceofhierarchicalclustering,giventhathierarchicalclusteringdoesnotprovideasinglesolutiontomodule-identificationprob-lem.Neithercanonetesttheinfinitecombinationsofdimen-sionalityreductionalgorithmswithtechniquesfortheactualselectionofmodules.

Freeman[32]hasrecentlycompiledacollectionof21al-gorithmsthathavebeenusedinthesocialnetworksliteraturetoidentifymodulesinbipartitenetworks.Tothebestofourunderstandingnoneofthealgorithmsdescribedtheresatisfiesthetwoconditionsabove.Amongthestatisticalphysicscom-munity,ontheotherhand,thecommonpracticeistoprojectthebipartitenetworkontoaunipartiteactors’network,andthenidentifymodulesintheprojection.Inthescientists’pro-jectionofascientificpublicationnetwork,forexample,two

2

scientistsareconnectediftheyhavecoauthoredoneormorepapers.Thecaveatofthisapproachisthat,evenifthepro-jectionisweighted(byforexample,thenumberofpaperscoauthoredbyapairofscientists),someinformationoftheoriginalbipartitenetwork,likethesizesoftheteams,islostintheprojection.Here,wesuggestanalternativetoexistingapproachestoidentifymodulesincomplexbipartitenetworks.

II.MODULARITYFORBIPARTITENETWORKS

Awidelyusedandquitesuccessfulmethodfortheidentifi-cationofmodulesinunipartitenetworksisthemaximizationofamodularityfunction.Althoughthismethodhaslimita-tions[33,34,35],ityieldsthemostaccurateresultsreportedintheliteratureforawidefamilyofrandomnetworkswithprescribedmodularstructure[15,36,37].

Inthesamespirit,herewedefineamodularityfunctionthat,uponoptimization,yieldsapartitionoftheactorsinabipartitenetworkintomodules.Bydoingthis,themoduleidentifica-tionproblembecomesacombinatorialoptimizationproblemthatisanalogoustotheidentificationofthegroundstateofadisorderedmagneticsystem[38,39].

AubiquitousmodularityfunctionforunipartitenetworksistheNewman-Girvanmodularity[40].Therationalebehindthismodularityisthat,inamodularnetwork,linksarenothomogeneouslydistributed.Thus,apartitionwithhighmod-ularityissuchthatthedensityoflinksinsidemodulesissig-nificantlyhigherthantherandomexpectationforsuchdensity.Specifically,themodularityM(P)ofapartitionPofanet-workintomodulesis

NM

M(P)=󰀊󰀉ls

󰀆2󰀋,(1)

s=12LwhereNMisthenumberofmodules,Listhenumberoflinks

inthenetwork,lsisthenumberoflinksbetweennodesinmodules,anddsisthesumofthedegreesofthenodesinmodules.Thenls/Listhefractionoflinksinsidemodules,and(ds/2L)2isanapproximation(assumingthatself-linksandmultiplelinksbetweennodesareallowed)tothefrac-tionoflinksonewouldexpecttohaveinsidethemodulefromchancealone.

WedefineanewmodularityMB(P)thatcanbeappliedtoidentifymodulesinbipartitenetworks.Westartbyconsid-eringtheexpectednumberoftimesthatactoribelongstoateamcomprisedofmaactors:

mta

i

(

󰀂

2.(3)

ktk)

3

Therefore,theaveragenumberofteamsinwhichiandjareexpectedtobetogetheris

󰀂

ama(ma−1)

󰀂

−

=j∈stitj

a

ma(ma−1)

󰀂

iwalls

W

−

󰀄

whereW=we󰀂i≥jwij,wint

s

isthesumoftheweightsofthelinkswithinmodules,andwall

considerthebipartites=󰀂(B)i∈sapproach.󰀂jwij.

Finally,Withinthisapproach,weconsiderthewholebipartitenetworkandusethemodularityintroducedinEq.(5).

Inallcases,wemaximizethemodularityusingsimulatedannealing[41].Severalalternativeshavebeensuggestedtomaximizethemodularityincludinggreedysearch[42],ex-tremaloptimization[43],andspectralmethods[44,45].Ingeneral,thereisatrade-offbetweenaccuracyandexecu-tiontime,withsimulatedannealingbeingthemostaccuratemethod[15],butatpresenttooslowtodealproperlywithnet-workscomprisinghundredsofthousandsormillionsofnodes.

A.Modelbipartitenetworks

Weconsidertheperformanceofthedifferentmoduleiden-tificationapproacheswhenappliedtothemodelbipartitenet-worksdescribedabove.Weassesstheperformanceofanalgo-rithmbycomparingthepartitionsitreturnstothepredefinedgroupstructure.Specifically,weusethemutualinformationIAB[15]betweenpartitionsAandBtoquantifytheperfor-manceofthealgorithms

−2󰀂NAi=1M󰀂NBj=1nAB󰀄

nABMijS

ijlog

IAB=Here,Sisthe󰀂NAi=1MnAtotalnumber󰀁nAilogiS

ofnodesinthenetwork,N󰀃A

.(7)

numberofmodulesinpartitionA,A

Misthe

ABnmoduleiofpartitionA,andniisthenumberofnodesinareinmoduleiofpartitionAijisthenumberofnodesthatandinmodulejofpartitionB.ThemutualinformationbetweenpartitionsAandBis1ifbothpartitionsareidentical,and0iftheyareuncorrelated.Inthesimplestversionofthemodelallmoduleshavethesamenumberofnodes,allteamshavethesamesize,andthecolorofeachteamissetassumingequalprobabilityforeachcolor.Unlessotherwisestated,webuildnetworkswithNM=4modules,eachofthemcomprising32actors,andNT=128teamsofsizem=14.

1.Teamhomogeneity

Wefirstinvestigatehowteamhomogeneitypaffectsalgo-rithmperformance.Forp=1,alltheactorsinateambe-longtothesamemodule,andanyreasonablealgorithmmustperfectlyidentifythemodularstructureofthenetwork;thusI=1.Conversely,forp=0,actorsareperfectlymixedinteams,andallalgorithmswillreturnrandompartitionsduetosmallfluctuations[38];thusI=0.Anyp>0willprovideasignalthatanalgorithmcan,inprinciple,extract.

AsshowninFig.2(a),theUWPapproachperformssystem-aticallyandsignificantlyworsethantheweightedprojectionandthebipartitealgorithmsforallvaluesofp.Forthechoiceofparametersdescribedabove,thelasttwoalgorithmsstart

4

1.0(a)n0.8omia=14tah=1mr0.6NoT=128fni la0.4utuMBipartite0.2Weighted projectionUnweighted projection0.00.00.2Team homogeneity, 0.40.6 p0.81.01.0n0.8(b)op=0.5itama=14mr0.6h=1ofni la0.4utuM0.20.0101Number of teams, 102103N104T1.0n0.8(c)oitamr0.6ofni la0.4utp=0.5uMm0.2Na=14T=1280.00.4Module size homogeneity, 0.60.8h1.01.0(d)p=0.5no0.8h=1itaNmT=128rofn0.6i lautuM0.40.21Mean team size, µ10FIG.2:Algorithmperformanceasafunctionof:(a)teamhomogene-ityp(simulationparameters:NM=4,Ss=32forallmodules);(b)numberofteamsNT(simulationparameters:NM=4,Ss=32forallmodules);(c)modulesizehomogeneityh(simulationparam-etersNM=6,132nodes);and(d)meanteamsizeµ(simulationparameters:NM=4,Ss=32forallmodules).Errorbarsindicatethestandarderror.

tobeabletoidentifythemodularstructureofthenetworkforp≈0.35.Forp≥0.5,onealreadyfindsI>0.9.TheWP

5

andtheBapproachesyieldindistinguishableresults.

2.

Numberofteamsandaverageteamsize

Teamhomogeneityisnottheonlyparameteraffectingalgo-rithmperformance.Forexample,thenumberofteamsNTinthenetworkcriticallyaffectstheamountofinformationavail-abletoanalgorithm.Interestingly,thenumberofteamsaf-fectsindifferentwaystheUWPapproachontheonehand,andtheWPandBapproachesontheother;Fig.2(b).FortheWPandBalgorithms,thelargerNT,thelargertheamountofinformationandthereforetheeasiertheproblembecomes.Indeed,evenforverysmallvaluesofp,thesignaltonoiseratiocanbecomesignificantlygreaterthan1ifNTislargeenough.Onthecontrary,asthenumberofteamsincreasestheUWPbecomesdenseranddenserandeventuallybecomesafullyconnectedgraph,fromwhichthealgorithmcannotex-tractanyusefulinformation.Oncemore,theperformanceoftheWPandtheBapproachesareindistinguishable.

3.

Modulesizeheterogeneity

Inrealnetworks,moduleswillhave(sometimesdramati-cally)differentsizes[46].Giventhesizesofthemodulesinanetwork,andassumingthattheyareorderedsothatS1≥S2≥···≥SNM,wedefinehastheratioofsizesbetweenconsecutivemodules(withintegerrounding)

h=

Si+1

µ

󰀄

11−

A18(a)A17B11A11A16B10B13A14A8B9A12A15B12B14A3B2A10A13A1B8B6B7A7B4A9A6B5A2A4A5B3B1A18(b)A17B11A11A16B10B13A14A8B9A12A15B12B14A3B2A1B8A10A13B6B7A7B4A9A6B5A2A4A5B3B1FIG.3:ModularstructureoftheSouthernwomendataset[32,47].Circlesrepresentwomenanddiamondsrepresentsocialevents.Awomanandaneventareconnectedifthewomanattendedtheevent.(a)Modularstructureasobtainedfromtheunweightedpro-jection(UWP)approach.(b)Modularstructureasobtainedfromtheweightedprojection(WP)approachandthebipartite(B)approach.TheUWPapproachfailstocapturetherealmodularstructureofthenetwork.

networks,wenotethatdirectednetworkscanbeconvenientlyrepresentedasbipartitenetworkswhereeachnodeiisrepre-sentedbytwonodesAiandBi.Adirectedlinkfromitojwouldberepresentedinthebipartitenetworkasanedgecon-nectingAitoBj.

Consider,forexample,anetworkinwhichnodesarecom-paniesandlinksrepresentinvestmentsofonecompanyintoanother.Byconsideringeachcompanyastwodifferentob-jects,onethatmakesinvestmentsandonethatreceivesinvest-ments,thedirectednetworkcanberepresentedasanundi-rectedbipartitenetwork.Modulesinthesetofobjectsthatmakeinvestmentscorrespondtogroupsofcompaniesthatin-vestinthesamesetofcompanies,thatis,groupsofcompanieswithasimilarinvestingstrategy.6

In1−67−12(a)

Out13−1819−241−12pipo13−24popi(b)(c)(d)(e)FIG.4:Applicationofthebipartiteapproachtotheidentificationofmodulesindirectednetworks.(a,b)Adirectedmodelnetwork.Alinkfromnodeitonodejisestablishedaccordingtotheprob-abilitiesinthematrixin(a).Forexample,thereisaprobabilitypithatthereisalinkfromnode1tonode13.Inparticular,weusepi=0.45>po=0.05togeneratethedirectednetworkin(b).(c)Bipartiterepresentationofthenetworkin(b).Eachnodeiisin(b)isrepresentedbytwonodeshere,acircleAiandasquareBi.Alllinksinthebipartitenetworkrunbetweencirclesanddiamonds,andalinkbetweenAiandBjcorrespondstoalinkfromitojinthedirectednetwork.(d)Modulesidentifiedinthebipartitenetwork.(e)Mod-ulesidentifiedfromthedirectednetworkdisregardinglinkdirection.Here,weusethesamecolorforAiandBi,sincethisapproachdoesnotmakedistinctionsbetweenincomingandoutgoinglinks.

Themostwidelyusedapproachtoidentifycommunitiesindirectednetworksistosimplydisregardthedirectionalityofthelinksandidentifymodulesusingamethodsuitableforundirectedunipartitenetworks.Thismethodmightworkinsomesituations,butwillfailwhendifferentmodulesarede-finedbasedonincomingandoutgoinglinks.

Consider,forinstance,thesimplemodelnetworkdepictedinFigs.4(a,b).Accordingtotheoutgoinglinksofthenodesthisnetworkhastwomodules:nodes1-12andnodes13-24.Accordingtotheincominglinksofthenodesthenetworkhasalsotwomodules,buttheyaredifferent:nodes1-6and13-18ontheonehand,andnodes7-12and19-24ontheother.AsweshowinFig.4(c),alayoutofthecorrespondingbipar-titenetworkalreadymakesclearthemodularstructureofthe

network,andanyoftheapproachesdescribedabove(UWP,WP,andB)isabletoidentifythein-modulesandout-modulescorrectly;Fig.4(d).Disregardingthedirectionofthelinks,however,resultsinmodulesthatfailtocapturethemodularstructureofthenetwork;Fig.4(e).

VI.DISCUSSION

Inthiswork,wehavefocusedonapproachesthataimatidentifyingmodulesineachofthetwosetsofnodesinthebipartitenetworkindependently.Therearetwomainreasonsforthischoice.First,methodologicallyourchoiceenablescomparisonwithprojection-basedalgorithms,which,bydef-inition,cannotidentifymodulesofactorsandteamssimul-taneously.Second,inmostsituationsitisreasonabletoas-sumethattwoactorsbelongtothesamemoduleiftheyco-participateinmanyteams,regardlessofwhethertheteamsthemselvesbelongtothesamemoduleornot.Analternativeapproach,however,wouldbetogroupnodesinbothsetsatthesametime.

Anotherinterestingobservationrelatestotheoptimizationalgorithmusedtomaximizethemodularity.Althoughwehavechosentousesimulatedannealingtoobtainthebestpos-sibleaccuracy[15,36,37],onecantriviallyusethenewmod-ularityintroducedinEq.(5)withfasteralgorithmssuchasgreedysearch[42]orextremaloptimization[43].

Interestingly,onecanalsousethespectralmethodsintro-ducedin[44,45].Indeed,justastheunipartitemodularityM(P),thebipartitemodularityMB(P)canberewritteninmatrixformas

MB(P)=gTBg,

(10)

wheregis=1ifnodeibelongstomodulesand0otherwise,andtheelementsofthemodularitymatrixBaredefinedas

=

󰀅cij

Bij0(P

mi=jaa)2i=j.(11)Evenmoreimportantly,bysamplingalllocalmaximaof

themodularityinEq.(5)onecanstudy,notonlythemostmodularpartitionofthenetwork,butthehierarchicalstruc-tureofnestedmodulesandsubmodules[34]withineachsetofnodesinthebipartitenetwork.Thisisparticularlyrelevanttakingintoaccountthatthemostmodularpartitionofanet-workmay,insomecases,notrepresentthemost“relevant”divisionofitsnodes[33,34].

Finally,afewwordsarenecessaryonthecomparisonbe-tweenthedifferentapproaches.First,wehaveshownthatthe(sofar“default”)unweightedprojectionapproachisnotre-liableandcanlead,inmostsituations,toincorrectresults.Therefore,webelievethatthisapproachshouldnotbeused.Asfortheweightedprojectionapproachandthebipartiteap-proach,wehaveshownthattheirperformanceisverysimilar,andthattheyareactuallyequivalentwhenallteamsinthebi-partitenetworkhavethesamesize.Wehavealsopointedout,however,thattheycananddogivenoticeablydifferentresults

7

whenteamsizesarenotuniform.Giventhis,webelievethatthebipartiteapproachhasamorestraightforwardinterpreta-tionandwouldbepreferableincasesinwhichthemodularstructureofthenetworkisunknown.

Acknowledgments

WethankR.D.Malmgren,E.N.Sawardecker,S.M.D.Seaver,D.B.Stouffer,M.J.Stringer,andespeciallyM.E.J.NewmanandE.A.Leichtforusefulcommentsandsugges-tions.L.A.N.A.gratefullyacknowledgesthesupportofaNIH/NIGMSK-25award,ofNSFawardSBE0624318,oftheJ.S.McDonnellFoundation,andoftheW.M.KeckFoun-dation.

APPENDIXA:WEIGHTEDUNIPARTITEMODULARITYANDBIPARTITEMODULARITYFORBIPARTITE

NETWORKSWITHUNIFORMTEAMS

Next,wedemonstratethat,whenallteamsinabipartitenet-workhavethesamesizem,thebipartitemodularityisequiv-alenttothemodularityoftheweightedprojection.

Weconsidertheusualweightedprojection,inwhicheachpairofnodesi=jisconnectedbyalinkwhoseweightwijequalsthenumberoftimesthatiandjaretogetherinateam;usingourpreviousnotationwij=cij.Noself-linksarein-cludedintheprojection.

Inthisprojection,andwhenallteamshavethesamenum-berofactorsma≡m,theconstantteam-sizefactorsinEq.(5)become

󰀊

ma(ma−1)=NTm(m−1)=2W(A1)

a

󰀇󰀊

ma

a

󰀈2

=

󰀄

2W

󰀂

wints

ama(ma−1)

==(m−1)ti

(󰀂

ama)2

2W

=

󰀄

󰀊i∈swalls

2W

󰀆2

.(A5)

Oncethesummationovermodulesiscarriedout,thelasttermissimplyaconstantindependentofthepartition,andisthereforeirrelevant.Thus,uptoanirrelevantconstant,when

allteamsinabipartitenetworkhavethesamesize,thebipar-titemodularityinEq.(5)isequivalenttotheweightedmodu-[1]R.AlbertandA.-L.Barab´asi,Rev.Mod.Phys.74,47(2002).[2]M.E.J.Newman,SIAMReview45,167(2003).

[3]L.A.N.AmaralandJ.Ottino,Eur.Phys.J.B38,147(2004).[4]M.GirvanandM.E.J.Newman,Proc.Natl.Acad.Sci.USA99,7821(2002).[5]R.Guimer`a,S.Mossa,A.Turtschi,andL.A.N.Amaral,Proc.Natl.Acad.Sci.USA102,7794(2005).[6]V.Colizza,A.Barrat,M.Barth´elemy,andA.Vespignani,Proc.Natl.Acad.Sci.USA103,2015(2006).

[7]R.Pastor-SatorrasandA.Vespignani,Phys.Rev.Lett.86,3200(2001).

[8]F.Liljeros,C.R.Edling,andL.A.N.Amaral,MicrobesInfect.5,1(2003).[9]R.Guimer`a,M.Sales-Pardo,andL.A.N.Amaral,NaturePhys.3,63(2007).

[10]M.E.J.Newman,Phys.Rev.Lett.,art.no.208701(2002).[11]R.Pastor-Satorras,A.V´azquez,andA.Vespignani,Phys.Rev.Lett.87,art.no.258701(2001).

[12]S.MaslovandK.Sneppen,Science296,910(2002).

[13]S.Maslov,K.Sneppen,andA.Zaliznyak,PhysicaA333,529(2004).

[14]V.Colizza,A.Flammini,M.A.Serrano,andA.Vespignani,NaturePhys.2,110(2006).[15]L.Danon,A.D´ıaz-Guilera,J.Duch,andA.Arenas,J.Stat.Mech.:Theor.Exp.p.art.no.P09008(2005).

[16]S.P.BorgattiandM.G.Everett,SocialNetworks19,243(1997).

[17]P.Doreian,V.Batagelj,andA.Ferligoj,SocialNetworks26,29(2004).

[18]P.Uetz,L.Giot,G.Cagney,T.A.Mansfield,R.S.Judson,J.R.Knight,D.Lockshon,V.Narayan,M.Srinivasan,P.Pochart,etal.,Nature403,623(2000).

[19]H.Jeong,S.P.Mason,A.-L.Barab´asi,andZ.N.Oltvai,Nature411,41(2001).

[20]S.Li,C.M.Armstrong,N.Bertin,H.Ge,S.Milstein,M.Boxem,P.-O.Vidalain,J.-D.J.Han,A.Chesneau,T.Hao,etal.,Science303,540(2004).

[21]P.Jordano,Am.Nat.129,657(1987).

[22]J.Bascompte,P.Jordano,C.J.Melin,andJ.M.Olesen,Proc.Natl.Acad.Sci.U.S.A.100,9383(2003).

[23]M.E.J.Newman,Proc.Natl.Acad.Sci.USA98,404(2001).[24]K.B¨orner,J.T.Maru,andR.L.Goldstone,Proc.Natl.Acad.Sci.USA101,5266(2004).[25]R.Guimer`a,B.Uzzi,J.Spiro,andL.A.N.Amaral,Science308,697(2005).

[26]P.M.GleiserandL.Danon,Adv.ComplexSyst.6,565(2003).

8

larityinEq.(6).

[27]B.UzziandJ.Spiro,Am.J.Sociol.111,447(2005).[28]D.B.Stouffer,J.Camacho,R.Guimer`a,C.A.Ng,andL.A.N.

Amaral,Ecology86,1301(2005).

[29]R.J.WilliamsandN.D.Martinez,Nature404,180(2000).[30]A.-L.Barab´asiandZ.N.Oltvai,Nat.Rev.Genet.5,101(2004).[31]B.S.Everitt,S.Landau,andM.Leese,ClusterAnalysis

(ArnoldPub.,2001).

[32]L.C.Freenan,inDynamicSocialNetworkModelingandAnal-ysis:WorkshopSummaryandPapers,editedbyR.Breiger,C.Carley,andP.Pattison(TheNationalAcademiesPress,Washington,DC,2003),pp.39–97.[33]S.FortunatoandM.Barth´elemy,Proc.Natl.Acad.Sci.USA

104,36(2007).

[34]M.Sales-Pardo,R.Guimer`a,A.A.Moreira,andL.A.N.Ama-ral,arXiv:0705.1679(2007).

[35]S.Fortunato,arXiv:0705.4445(2007).[36]R.Guimer`aandL.A.N.Amaral,Nature433,5(2005).[37]R.Guimer`aandL.A.N.Amaral,J.Stat.Mech.:Theor.Exp.p.

art.no.P02001(2005).[38]R.Guimer`a,M.Sales-Pardo,andL.A.N.Amaral,Phys.Rev.

E70,art.no.025101(2004).

[39]J.ReichardtandS.Bornholdt,Phys.Rev.E74,016110(2006).[40]M.E.J.NewmanandM.Girvan,Phys.Rev.E69,art.no.

026113(2004).

[41]S.Kirkpatrick,C.D.Gelatt,andM.P.Vecchi,Science220,671

(1983).

[42]M.E.J.Newman,Phys.Rev.E69,art.no.066133(2004).[43]J.DuchandA.Arenas,Phys.Rev.E72,art.no.027104(2005).[44]M.E.J.Newman,Proc.Natl.Acad.Sci.USA103,8577(2006).[45]M.E.J.Newman,Phys.Rev.E74,art.no.036104(2006).[46]L.Danon,A.D´ıaz-Guilera,andA.Arenas,J.Stat.Mech.:

Theor.Exp.p.P11010(2006).

[47]A.Davis,B.B.Gardner,andM.R.Gardner,DeepSouth(Uni-versityofChicagoPress,Chicago,1941).

[48]Includingthediagonaltermwouldonlyshiftthemodularityby

aconstant,andisthereforeirrelevant.

[49]Thisis,tosomeextent,animplicitdefinitionofwhatmodu-laritymeansinbipartitenetworks,inthesamewaythat“higherlinkageprobabilityinsidemodules”isadefinitionofwhatmod-ularitymeansinunipartitenetworks.

[50]Evenincasesinwhichallteamshavethesamesize,smallsys-tematicdiscrepanciescanoccurbetweentheWPandtheBap-proach,giventhatthesimulatedannealingusedineachcaseisdifferentinsomeimplementationdetails.