collectnokia

AnalysisofLargeMulti-modalSocialNetworks:PatternsandaGeneratorNanDu1,HaoWang1,andChristosFaloutsos21NokiaResearchCenter,Beijing{daniel.
du,hao.
ui.
wang}@nokia.
com2CarnegieMellonUniversity,Pittsburghchristos@cs.
cmu.
eduAbstract.
On-linesocialnetworkingsitesofteninvolvemultiplerela-tionssimultaneously.
Whilepeoplecanbuildanexplicitsocialnetworkbyaddingeachotherasfriends,theycanalsoformseveralimplicitso-cialnetworksthroughtheirdailyinteractionslikecommentingonpeo-ple'sposts,ortaggingpeople'sphotos.
Sogivenarealsocialnetworkingsystemwhichchangesovertime,whatcanwesayaboutpeople'ssocialbehaviorsDotheirdailyinteractionsfollowanypatternThema-jorityofearlierworkmainlymimicsthepatternsandpropertiesofasingletypeofnetwork.
Here,wemodeltheformationandco-evolutionofmulti-modalnetworksemergingfromdierentsocialrelationssuchas"who-adds-whom-as-friend"and"who-comments-on-whose-post"si-multaneously.
Thecontributionsarethefollowing:(a)weproposeanewapproachcalledEigenNetworkAnalysisforanalyzingtime-evolvingnetworks,anduseittodiscovertemporalpatternswithpeople'ssocialinteractions;(b)wereportinherentcorrelationbetweenfriendshipandco-occurrenceinon-linesettings;(c)wedesigntherstmulti-modalgraphgeneratorxSocial1thatiscapableofproducingmultipleweightedtime-evolvingnetworks,whichmatchmostoftheobservedpatternssofar.
Ourstudywasperformedontworealdatasets(NokiaFriendViewandFlickr)with100,000and50,000,000recordsrespectively,eachofwhichcorrespondstoadierentsocialservice,andspansuptotwoyearsofactivity.
Keywords:SocialNetworkAnalysis,GraphGenerator,Multi-modalNetworks.
1IntroductionResearchofrealworldcomplexnetworks,likesocialnetworks[24],biologicalnetworks[11],topology[15]ofWWWandInternetraisesmanysignicantandimportantproblems.
Whatpatternsdothehuman-to-humaninteractionsfollowinlarge-scalesocialnetworksHowcanweusesuchpatternstofacilitateexistingapplications,suchasanomalydetection[1][18]andcollectiveclassication[8],andmakefurtherinnovations1http://research.
nokia.
com/people/hao_ui_wang/index.
htmlJ.
L.
Balcazaretal.
(Eds.
):ECMLPKDD2010,PartI,LNAI6321,pp.
393–408,2010.
cSpringer-VerlagBerlinHeidelberg2010394N.
Du,H.
Wang,andC.
FaloutsosAsaresultofthewidespreadadoptionofWeb2.
0technology,socialnet-workingsitesorservices(SNS)arebecomingubiquitousandpenetrateintoeverycornerofpeople'sdailylives.
Insuchsystems,peopleoftenbelongtomultipleso-cialnetworksbecauseofdierentperson-to-personinteractions.
Forexample,inNokiaFriendView(http://betalabs.
nokia.
com/apps/nokia-friend-view),Flickr(www.
flickr.
com),Facebook(www.
facebook.
com),eBay(www.
ebay.
com),LinkedIn(www.
linkedin.
com),andTwitter(www.
twitter.
com),theyallprovidethebasicfunctionthatenablespeopletoaddeachotherasfriendsthroughtheircontentandconversations,whichcontributestotheemergenceofourrsttypeofsocialnetwork,namely,the"friendnetwork"orthe"buddynetwork".
Inaddition,theyalsoallowpeopletoparticipateinspecicactivities.
InFriendView,wecancommentonthepostswrittenbyourcolleagues.
InFlickr,wecantagthephotosuploadedbyourfriends.
IneBay,wecanratetheprod-uctssoldbyourpartners.
Asaconsequence,interactionswithpeoplecenteredaroundcontentformanothertypeofsocialnetworkcalledthe"commentnet-work"orthe"participationnetwork"fromsuchactivitiesas"commenting-on-posts","tagging-photos"and"rating-products".
Therefore,thesetwotypesofsocialnetworksdescribedierentfacetsofthesamesocialnetworkingsystem.
Foreachofthem,recentresearchhasreportedfascinatingpatterns,like[26]orlognormal[7]orDoubleParetoLogNormal(DPLN)distribution[25]forthedegree,aswellassmallandshrinkingdiameter[20].
Inthispaper,weareinterestedinansweringthefollowingquestions:–DohumansocialinteractionsandbehaviorsfollowanytemporalpatternIsthereanyregularityinherentinthedailyactivitiesofindividualsandgroupsCanweusesuchpatternstomakepredictionsoftheirfuturebehaviors–Givenarealsocialnetworkingsite,isthereanycorrelationbetweenthebuddynetworkandtheparticipationnetworkForinstance,canweinferthefriendshipbetweentwopeopleinbuddynetworkaccordingtothediscreteobservationsoftheirco-occurrenceintheparticipationnetwork–Howcanweproduceanintuitivegeneratorthatwillmimicthebehaviors,andcorrelationsofthesenetworkswithinarealsocialnetworkingsitesimul-taneouslyMostexistinggeneratorstrytomimictheskeweddistributionofdegreeorweightofonlyasinglenetwork,andthusfailtoincorporatethepossiblecorrelationswithothernetworks.
Here,wewantamulti-modalgraphgenerator,whichshoulddescribethewayinwhichthedierentso-cialnetworksdiscussedabovecouldco-evolveovertimethroughthelocalinteractionsandactivitiesbetweenindividuals.
Answeringthesequestionscanhavemanypracticalapplications.
First,identi-fyingmeaningfulpatternshiddeninhumanactivitiescontributestoclassifyingpeopleintodierentgroupsaccordingtothesimilarityoftheirsocialbehaviors,basedonwhichwecanhaveadeepinsightaboutthecompositionandevolutionofthenetworktheybelongto.
Discoveringnewpatternsalsohelpstodiscardun-realisticgraphmodels.
Second,knowingthecorrelationbetweendierentsocialrelationsisgoodforustodesignbettersystemsthatfurtherexpandtherangeofhumaninteractionsbyoeringparticularfriendorproductrecommendationsAnalysisofLargeMulti-modalSocialNetworks395accordingtospecicusercontext.
Finally,intuitivegraphmodelsarealsovitalforsimulationstudiesofroutingalgorithmswhenitishardorevenimpossibletocollectlargerealdata,forunderstandinghowthemacroandglobalpatternsofnetworkscanemergethroughthemicroandlocalinteractionsamongpeopleovertime,andforcompressingandsummarizingtherealnetworksbymodelparameters.
Thepaperisthenorganizedasfollows.
Section2reviewsrelatedwork.
Section3presentsourobservedpatterns.
Section4describesthexSocialmodelindetail.
Section5givestheconclusion.
2RelatedWorkInthissection,wemainlysurveythevariousdiscoveredpropertiesofrealworldnetworks,andseveralwell-knowngraphgenerators.
2.
1NetworkPatternsManyinterestingpatternsthatrealgraphsfollowhavebeendiscoveredinrecentworklikethepower-lawdistributionofthenumberofmessages(photos),powerlawcommentdistribution,powerlawintervaldistribution[16],powerlawdegreedistribution[26],powerlawedge-weightdistribution[24],powerlawnode-weightdistribution[24],SnapshotPowerLaw(SPL)[22],CliqueParticipationLaw(CPL)[13],Clique-DegreePowerLaw(CDPL)[13],TriangleWeightLaw[13],EigenvaluePowerLaw(EPL)[2],shrinkingdiameter[20],andoscillatingconnectedcomponent(GCC&NLCC)[22].
Thesepatternsareimportantforustounderstandthestaticandtemporalpropertiesofrealworldnetworks,toidentifyauthoritiesandsub-groups,aswellastoreneroutingalgorithmsandrecommendations.
Moreover,theyarealsovitalforeliminatingunrealisticgraphgeneratorsandguidingustodesignbetterones,becauseideallyagraphmodelshouldbeabletomimicallthesepatternsasmanyaspossible.
2.
2GraphGeneratorsGenerally,thegraphgeneratorsofrecentliteraturecanbemainlyclassiedasemergentgraphmodels,andgenerativegraphmodels.
Thebasicprincipleofemergentgraphmodelsisthatthemacronetworkpropertiesshouldemergefromthemicrointeractionsofnodesovertime.
ThistypeofmodelsincludeErd¨os-Renyi(ER)model[14],small-worldmodel[27],BAmodel[6],Copymodel[9],RandomMultiplicationModel[9],ForestFiremodel[20],'buttery'model[22],and'RTG'model[2].
[See[5]and[9]foradetailedreviewanddiscussion].
Recently,Goetz[16]alsoprovidesmodelstomimictheevolvingandspreadingmechanismofblogsystems.
Moreover,researchfromtheeldsofeconomicsandgametheoryalsobroughtutility-basedmodels[17][4][12][13]whereeachnodetriestooptimizeaspecicutilityfunction,andthenetworkstructurecanarisefromthecollectivestrategicactivitiesofallthenodes.
Generativegraphmodelsoftenassumeaglobalmathematicruleandperformiterationsofsuchrule396N.
Du,H.
Wang,andC.
Faloutsosrecursivelyuntilthegeneratednetworksmeetseveralpropertiesofrealnetworks.
Suchmodelsincludekroneckermultiplicationmodel[19]andtensormodel[3].
Insummary,themajorityofearliergraphgeneratorsoftenfocusedonmodel-ingsomemainpropertiesofonlyonesinglenetwork.
Forexample,[27][6][20][22]arelimitedintryingtomodelunweightednetworks,andcannotbegeneralizedtoweightednetworks.
Goetz[16]describestheevolvingprocessofblogs,butfailtoincorporatetheweights.
AlthoughRTG[2]cangenerateweightedgraphs,itstillonlyfocusedononesinglenetwork.
Astothegenerativemodels,theyusu-allycannotmimicthemicromechanismofnodeandedgeaddition,whichmakesithardforustounderstandtheinherentnaturalprocessofrealnetworks.
Incontrast,ourworknotonlyconsiderstomimicmostoftheknownpatterns,suchasgeneratingweightednetworksfromlocalnodes'interactions,butalsofocusesonco-evolutionofdierentnetworkssimultaneously.
3ToolsandObservationsInthissection,weseektondpatternsinherentinlarge-scaleon-linesocialnetworkingsites.
WerstgiveapreliminarydescriptionofNokiaFriendViewandFlickrdatasets,andthenwepresenttheproposedEigenNetworkanalysismethod,andthediscoveredCoParticipationFriendshipCorrelationpattern.
3.
1DataDescriptionThedatasetsthatwehaveanalyzedincludetheinteractionrecordsfromNokiaFriendView,andFlickr.
NokiaFriendViewisalocation-enhancedexperimentalmicrobloggingapplicationandserviceoperatedbyNokiaBetaLabsfromthebeginningofNovember2008totheendofSeptember2009whentheservicewasnished.
ItallowsuserstopostmessagesabouttheirstatusandactivitiesfromGPS-enabledNokiaS60phonesorfromtheweb.
Anytwouserscanaddeachothertotheirbuddylistthroughemailrequestandconrmation.
Theuserscanalsocommentonthestatusmessagespostedbythebuddiesintheirsocialnetwork.
Asaresult,weusethreedierenttypesofrecord,,,,todescribetheseactionsrespectively.
Here,theedgeweightofbuddynetworkisthetotalnumberofcommenttimesbetweenthem.
Forthedataset,thereare34,980users,20,873buddylinks,62,736statusmessages,and22,251comments[10].
Theuniquefeatureofthisdatasetisthatithasrecordedacompleteevolvingprocessofasocialnetworkingsitefromtheverybeginningtotheend,overthecourseof11months.
Thedetailedrecordsenableustohaveadeepinsightaboutthewaythatpeopleinteractwitheachother.
IntheFlickrdataset(wherepeoplecanuploadphotos,addcontacts,andcommentonortagphotos),weusesimilartuplesasFriendViewtodescribethedatawhichincludesabout542,105users,46,668,661contactlinks,101,520,484photos,and8,999,983commentsfrom2005to2007.
Becausethesedatasetsbelongtodierentservices,havedierentscales,andwerecollectedAnalysisofLargeMulti-modalSocialNetworks397fromdierenttime,thediversityofourdatacanthusbeguaranteed.
Noticeweonlyusetheencrypteduseridinthisstudy,andrestrictourinterestonlyinthestatisticalndingswithinthedata.
3.
2EigenNetworkAnalysisWhiletheactivitiesandinteractionswhereeachofusisinvolvedeverydayappearnearlyrandom,intuitiontellsthattherealsoseemstobesomeregularrecurrenceofpatterns,especiallywhenwetakethetemporal,spatial,andsocialcontextintoconsideration.
Forinstance,wemaycheckseveralemails,andseesomenewsafterarrivingattheoceinthemorning.
Thenwemightchatwithourfriendsthroughinstantmessagingduringtheworkinghours,andintheevening,wemightwriteblogs,makecomments,uploadphotos,orevenplayon-linegames.
Sinceasocialnetworkisinherentlythecollectionofpeopleandtheirinteractions,analyzingthetemporalbehaviorsofindividualsandsubgroupscanhelpustohaveadeepinsightabouttheoverallcompositionoftheentirenetwork.
Weformulateourapproachasfollows.
GivengraphG,foreij∈E(G),wecharacterizethetemporalactivityofalltheedgesbyatwo-dimensionalE*DbinarymatrixM,whereE=|E(G)|,andDisthetotalnumberofdaysthatgraphGhasbeeninstudy.
M(p,q)=0010.
.
.
0100.
.
.
1011.
.
.
(1)Therefore,thepthrowrepresentsthebehaviorofaparticularedgeeijspanningtheDdays.
Onaspecicdayq,ifnodeviandvjhasatleastoneinteractionwitheachother,thenM(p,q)=1;otherwiseM(p,q)=0.
WethendoSingularValueDecomposition(SVD)onmatrixManditisfactorizedasM=U*Σ*VT(2)wherethecolumnsofD-by-KmatrixVformasetoforthonormalinputbasisvectorsforM,thecolumnsofE-by-KmatrixUformasetofcorrespondingorthonormaloutputbasisvectors,andthediagonalvaluesinK-by-KmatrixΣarethesingularvaluesarrangedinthedescendingorderbywhicheachcorre-spondinginputismultipliedtogiveacorrespondingoutput.
Byintuition,theSVDonmatrixMimplicitlydecomposestheEedgesintoKgroups.
Eachcolumn(orsingularvector)ioftheE-by-KmatrixUdescribestheextenttowhicheachedgeofGparticipatesintheithgroup.
EverycolumnjoftheD-by-KmatrixVshowstheextenttowhichthejthgroupisactiveoneachday.
ThenonnegativerealnumbersonthediagonaloftheK-by-KmatrixΣindicatesthestrengthofeachgroup.
Foreachsingularvaluesi,theenergyofsiisdenedass2i,sowekeeptherstfewstrongestsingularvalueswhosesumcovers80-90percentileofthetotalenergy.
Here,webuildmatrixMfor398N.
Du,H.
Wang,andC.
Faloutsos010020030000.
050.
1DayStrengthFriendView01002003004000.
200.
20.
40.
6DayStrengthFriendView14th,productpromotion020040060080000.
020.
040.
060.
080.
1DayStrengthFlickr02004006008000.
150.
10.
0500.
050.
1DayStrengthFlickr(a)1stvector(b)2ndvector(c)1stvector(d)2ndvectorFig.
1.
The1stand2ndsingularvectorofmatrixVthatdescribethecorrespondingdailyactivitiesofthe1stand2ndsubgraphconsistingoftheselectededgesintheparticipationnetwork(formedbythecommentrelation)ofFriendView(a-b),andFlickr(c-d)respectivelytheparticipationnetworkwhichemergesfromthecommentinteractionsamongusersinFriendViewandFlickrrespectively.
M(p,q)=1meansthatforthepthedgeeij,atleastoneofthetwonodes(viandvj)commentedonthemessagesorphotospostedbytheotheroneontheqthday.
Figure1showsthetoptwosingularvectorsofthematrixVfromFriendViewandFlickr.
InFigure1(a-b),wehavetwogroupsofedgesthatshowdierentpatternsofbehavior.
TherstgroupofFigure1(a)hasbasicallyaperiodicpattern,whilethesecondgroupofFigure1(b)appearsmorebursty,wherethespikeoccursonthe14thday.
BasedonthecompleterecordsofFriendView,itwasdiscoveredthatthe14thdaywasjustduringtheweekthatNokiadidlotsofadvertisingworktopromoteFriendViewbycallingformoreopenbetatesters.
ForFlickr,bothofthetwogroupsshowninFigure1(c-d)behavepe-riodically.
Thereisacleartrendofoverallgrowthintheamplitudewithsomeoscillation.
WeguessthismaybecausedbythequicklyincreasedpopularityandfastdevelopmentofFlickrasmoreandmoreusersjoinedinthesystemaftertheyear2006.
Figure2furtherpresentstheevolvingprocessofthesubgraphG1xandG2xconsistingoftheselectededgesthatactivelyparticipateinthe1stand2ndsingularvectorofmatrixU.
Beingactivemeansthatweonlykeepthesetofedgeswhosesumoftheenergy(whichisthesquareofthecorrespondingvalue)covers80-90percentileofthetotalenergy.
InFigure2,theevolvingpatternofG1xandG2xareclearlydierent.
SubgraphG1xcontainsasize-4clique(completegraph)whereeachblue-squarenodehasconnectionswitheachother.
Thiscliqueremainsstableintopologyandintotalnumberofactivitiesoverthewholeperiod,exceptforG12whereveedgesshowninredhadsignicantlyincreasednumberofactivities,andforG13wherethethenumberoftheiractivitiesdroppedback.
Foreij∈E(G1x),x>1,redcolorofeijindicatesthatitsweight(whichisthetotalnumberoftimesthatnodeviandvjinteractwitheachotherinthexthmonth)issignicantlyhigherthanitspreviousvalueingraphG1x1,andgreencolormeansthereverse.
Wemadefurtherinvestigationsintotheegocentricsubgraphofaroundsuch4blue-squarenodesintheentirenetwork.
Theiraveragedegree,andnodebetweenness[24]are39and0.
42respectively.
Becausedegree,AnalysisofLargeMulti-modalSocialNetworks399(a)G11of2008.
11(b)G12of2009.
1(c)G13of2009.
3(d)G14of2009.
5(e)G16of2009.
9(f)G21of2008.
11(g)G22of2009.
1(h)G23of2009.
3(i)G24of2009.
5(j)G26of2009.
9Fig.
2.
TheevolvingprocessofthesubgraphG1xandG2xconsistingoftheselectededgesbelongingtothe1st(toprow)and2nd(bottomrow)singularvectorofmatrixUintheparticipationnetworkofFriendView.
G1x(G2x)wherex>1,redindicatesthattheweight(representingthenumberoftimesthattwouserscommentoneachother'smessages)isatleastanorderofmagnitudehigherthanitspreviousvalueinG1x1(G2x1),greenmeansthereverse,andblackshowsthesamelevel.
andnodebetweennessaretwopopularmeasurestoquantifyanode'sauthorityorcentralityinasocialnetwork,thesubgraphformedfromtheseactiveedgesinthe1stsingularvectorofmatrixUactuallyrepresentsthecentralpartorthecoreofFriendView'sparticipationnetwork.
WeseethatinNovember,2008andJanuary,2009,therearetwosignicantincreasesinthenumberofinteractionsasmostedgesinthesubgraphareredcomparedwiththepreviousgraph,whichalsocoincideswiththetwospikesinFigure1(a).
Moreover,becausetheopenbetatestingforFriendViewactuallynishedinSeptember,2009,inFigure2,thesubgraphbecomessparse,whentheinteractionsbetweenusersdroppedgradually,andalsoconformswiththedecreasingtrendinFigure1(a).
Incontrast,thesubgraphG2xislooselycon-nected.
Inthebeginning,itonlyconsistedofseveralseparatededges.
NoticeinFigure1(b),thereisaburstyintherstmonthwhenNokiadidalotofpub-licitywork.
Asaresult,thereweremanyseparatedshort-terminteractionsatthattime.
Therefore,becausesubgraphsformedbytheselectededgesfromthesingularvectorsofmatrixU(whicharealsotheeigenvectorsofM*MT)holddier-entlocaltemporalpatterns,andrepresentdierentcompositionsoftheoverallnetwork,theyaredenedastheEigenNetworks,andourmethodologyisthuscalledEigenNetworkanalysis.
Observation1.
EigenNetwork.
TheEigenNetworkscanreveallocalcomposi-tionsofrealworldsocialnetworks,andholddierenttemporalpatternsovertime.
400N.
Du,H.
Wang,andC.
Faloutsos3.
3CoParticipation-FriendshipCorrelationInrealsocialnetworkingsiteslikeFriendVieworFlickr,ontheonehand,peo-plespendtheirdaytimeinfollowingtheupdatedstatusoftheirfriendsintheexplicitbuddynetwork.
Ontheotherhand,peoplearealsothemajorplayersintheimplicitparticipationnetworkthatemergesfromtheactivitiesweadopt.
Asaconsequence,isthereanycorrelationbetweenthesetwotypesofinteractionWillthereoccurrenceofoneparticularimplicitactivitycontributetoaformationofthecorrespondingexplicitinteractionMorespecically,canwequantifytheextenttowhichtwopeoplewillbecomefriendsinthebuddynetworkaccordingtothediscreteobservationsoftheirco-occurrencesinthecorrespondingpartic-ipationnetworkAnunderlyingpremiseisthattheprobabilityfortwopeopletobecomefriendsincreaseswiththenumberofactivitiesinwhichtheyhaveengagedtogether.
020406000.
20.
40.
60.
81kProbabilityp(k)FriendViewrealrandom020406000.
050.
10.
150.
2kProbabilityp(k)Flickrrealrandom(a)FriendView(b)FlickrFig.
3.
TheprobabilityP(k)ofbeingfriendsasafunctionofthenumberofco-commentedmessageskinFriendView(a),andphotosinFlickr(b)respectively.
Foreachk,redcurveindicatestheactualprobabilityofbeingfriends,andbluecurveshowstheexpectedvalueinrandomgraphs.
Theoutliersaremarkedbyredcircles.
Figure3showsthisbasicrelationshipinredcolorforFriendViewandFlickrrespectively,thatis,theprobabilityP(k)oftwopeopletobecomefriendsasafunctionofthetotalnumberoftimesthattheyhaveparticipatedinkcommonactivities.
P(k)iscalculatedasfollows.
Werstndalltuplessuchthatnodeviandvjhavekparticipatedactivitiesincommon.
ThenP(k)isthefractionofsuchtuplesforagivenkthatnodeviandvjarealsofriendsinthebuddynetwork.
Weseethatwhenkisroughlysmall(kP0(k),wesaythatthecorrelationisover-representedinthedatacomparedtochance;ontheotherhand,ifP(k)NokiaFriendViewMobileSocialNetwork.
CSE(4),278–283(2009)11.
Chung,F.
,Lu,L.
,Dewey,T.
G.
,Galas,D.
J.
:J.
Comput.
Biol.
10(5),677–687(2003)12.
Demaine,E.
D.
,Hajiaghayi,M.
,Mahini,H.
,Zadimoghaddam,M.
:Thepriceofanarchyinnetworkcreationgames.
In:PODC,pp.
292–298(2007)13.
Du,N.
,Faloutsos,C.
,Wang,B.
,Akoglu,L.
:Largehumancommunicationnet-works:patternsandautility-drivengenerator.
In:KDD2009,pp.
269–278(2009)14.
Erdos,P.
,Renyi,A.
:Ontheevolutionofrandomgraphs.
Publ.
Math.
Inst.
Hun-gary.
Acad.
Sci.
5,17–61(1960)15.
Faloutsos,M.
,Faloutsos,P.
,Faloutsos,C.
:Onpower-lawrelationshipsofthein-ternettopology.
In:SIGCOMM,pp.
251–262(August-September1999)16.
Goetz,M.
,Leskovec,J.
,Mcglohon,M.
,Faloutsos,C.
:Modelingblogdynamics.
In:ICWSM2009(2009)17.
Laoutaris,N.
,Poplawski,L.
J.
,Rajaraman,R.
,Sundaram,R.
,Teng,S.
-H.
:Boundedbudgetconnection(bbc)gamesorhowtomakefriendsandinuencepeople,onabudget.
CoRR(2008)18.
Lee,J.
-G.
,Han,J.
,Li,X.
:Trajectoryoutlierdetection:Apartition-and-detectframework.
In:ICDE2008,pp.
140–149(2008)19.
Leskovec,J.
,Chakrabarti,D.
,Kleinberg,J.
M.
,Faloutsos,C.
:Realistic,mathemat-icallytractablegraphgenerationandevolution,usingkroneckermultiplication.
In:Jorge,A.
M.
,Torgo,L.
,Brazdil,P.
B.
,Camacho,R.
,Gama,J.
(eds.
)PKDD2005.
LNCS(LNAI),vol.
3721,pp.
133–145.
Springer,Heidelberg(2005)20.
Leskovec,J.
,Kleinberg,J.
,Faloutsos,C.
:Graphsovertime:densicationlaws,shrinkingdiametersandpossibleexplanations.
In:KDD2005,pp.
177–187(2005)21.
Leskovec,J.
,Hunttenlocher,D.
,Kleinberg,J.
:SignedNetworksinSocialMedia.
In:CHI,pp.
1361–1370(2010)22.
McGlohon,M.
,Akoglu,L.
,Faloutsos,C.
:Weightedgraphsanddisconnectedcom-ponents:patternsandagenerator.
In:KDD2008,pp.
524–532(2008)23.
Newman,M.
E.
J.
:Powerlaws,paretodistributionsandzipf'slaw.
ContemporaryPhysics46,323(2005)24.
Onnela,J.
-P.
,Saram¨aki,J.
,Hyv¨onen,J.
,Szabo,G.
,deMenezes,A.
M.
,Kaski,K.
,Barabasi,A.
-L.
,Kertesz,J.
:Analysisofalarge-scaleweightednetworkofone-to-onehumancommunication.
NewJ.
Phys.
9(6)(June2007)25.
Reed,W.
,Jorgensen,M.
:Thedoublepareto-lognormaldistribution-anewpara-metricmodelforsizedistribution(2004)26.
Watts,D.
:SmallWorlds:TheDynamicsofNetworksbetweenOrderandRandom-ness.
PrincetonUniversityPress,Princeton(1999)27.
Watts,D.
J.
,Strogatz,S.
H.
:Collectivedynamicsof'small-world'networks.
Nature393(6684),440–442(1998)