网络科学与社会学习课件

网络科学与社会学习新浪围脖：汪小帆老师提纲网络科学：社会网络分析群体智慧：网络社会学习蜂拥控制：集群行为涌现FirstLesson:Isitreallyasmallworld?MeC.K.ChuiP.ErdösG.R.Chen

Erdöspublished>1,500paperswith>500coauthorsCommunicationNetworkViewNETWORKVIEWOFTHEWORLDTransportationPowerGridSocialBiologicalLanguageWhatisaComplexNetwork?Complex,varyingWeights&directionsThemoreoneworkswithcomplexnetworks,themoreonetendstofindthemeverywhereNodecomplexityStructuralcomplexityNonlineardynamicsDifferentkindsMultidimensionalNetworksinWeb2.0MultipleTypesofNodesandMultipleTypesofRelationshipsInterdependentNetworks传染病、时尚、观点和谣言等在社会网络中的传播病毒在Internet和移动通信网上的传播电网上的大规模相继故障局部动荡引起的全球经济危机

研究各种复杂网络的共性特征和分析它们的理论方法什么是网络科学？IdentificationofInfluentialSpreadersDegreekBetweenessKitsakM,GallosLK,HavlinS,etal.NaturePhysics,2010,6(11)K-shell网络科学测量网络数据发现网络性质建立网络模型分析网络行为设计网络性能ClassificationofNetworksUnweightedUndirectedWeightedUndirectedUnweightedDirectedWeightedDirectedFeaturesweaddresstonodesandedgesdependonwhatwewanttostudy.ThefirstthingtodoistoknowwhatkindofcomponentsandinteractionsbetweenthemarewetalkingaboutDegreeofaNodeAveragedegreeki:No.ofedgesconnectedtonodeiOut-degreeandIn-degreeTrueintheaggregatebutnotindetail!你所关注的人数=？你的粉丝数围脖上所有关注的人数=！围脖上所有的粉丝数围脖：一个典型的有向网络汪小帆老师130关注5987粉丝957微博底层有向网络如何影响网络行为？有向网络的蝴蝶结无向网络的连通巨片网络连通性朋友的朋友知多少？平均度外平均度AveragePathLengthDistancedij

:No.ofedgesalongtheshortestpathconnectingiandj.DiameterD=maxdij

AveragepathlengthL=avedij

Small-worldeffectL~lnNClusteringCoefficient?C>>CrandomDegreeDistributionP(k)ProbabilitythatarandomlyselectednodehasexactlykedgesTheGaussianornormaldistributionplaysacentralroleinallofstatisticsandhaslongbeenregardedasthemostubiquitousdistributionintheworld.1998,Watts&Strogatz,Small-WorldModelRegularNetRandomGraphLargeLandCDoesthereexistasmallworldwithhighclustering(smallLandlargeC)？WS‘Small-World’ModelSmallLandC

Startwithorder:BeginwithaNNnet.,whereeachnodeisadjacenttoitsKneighbornodes.WS‘Small-World’ModelRandomization:Randomlyrewireeachedgeofthenetworkwithprobabilityp(shiftingoneendoftheconnectiontoanewnodechosenatrandom)WS‘Small-World’ModelNormalizationLog.ScaleAveragep=0,C(0),L(0)大p=1,C(1),L(1)小0<p<<1,C大，L小C(p)~C(0),L(p)<<L(0)1999,Barabasi&Albert,Scale-FreeNetworkDegreedistributionofmanynetworks:ScaleFreeFeatureBarabási&Albert,Science,1999,286(5439):509-512HeterogeneousNature:MostnodeshaveverylowdegreesAfewnodeshavingveryhighdegrees(1)GROWTHNetworkscontinuouslyexpandbytheadditionofnewnodesWWW:additionofnewdocumentsCitation:publicationofnewpapers(2)PREFERENTIALATTACHMENT

Anodeislinkedwithhigherprobabilitytoanodethatalreadyhasalargenumberoflinks.WWW:newdocumentslinktowellknownsitesCitation:wellcitedpapersaremorelikelytobecitedagainAScale-FreeNetworkModelA.-L.Barabási,R.Albert,Science286,509(1999)Lesson2:

WhyWatts&Strogatzdidn’tdiscoverthepower-law?“Wedidn’tcheck!Weweresoconvincedthatnonnormaldegreedistributionsweren’trelevantthatweneverthoughttolookatwhichnetworksactuallyhadnormaldegreedistributionandwhichonesdidnot.”Don’tworryaboutreinventingthewheel!网络结构建模挑战究竟应该刻画网络的哪些拓扑特征？BA

EBAFitnessMLW‘Real’Internet

(15May2005)

21999

219992199921999219990.003

0.01

0.010.24

0.46

4.14

3.49

3.713.45

3.49

3

2.69

2.452.36

2.18

27.8262.8339.16111.87141.12网络结构建模挑战两个网络可以在不少性质方面都很相近，但在其它方面仍然差别很大！网络结构建模挑战基于不完整网络数据建立的模型能否用于实际网络？网络结构建模挑战如何模拟多个网络之间的相互影响？混合网络环境下的集群行为！网络结构建模挑战如何刻画网络结构的演化特征？Wealink（若邻网）DataCollection2005.5.11-2007.8.22Who?UserIDWithWho?FriendlistWhen?TimeNodes:223,624Edges:

273,395Meandegree:2.45

Max.degree:

1657

EvolutionofthenumbersofnodesN(T)andedgesE(T),andnetworkdensityd(T)fromJune11th2005toAugust11th2007

EvolutionofNetworkSizeEvolutionofDegreeAssortativityofWealink

Assortativity同配性Disassortativity异配性在线社会网络中个体（话题）活动性分布社会媒体Comic在线社交Wealink延拓指数分布幂律分布活动性概率模型在每一时间步T以概率α

出现一位新用户ui，以概率1-α以前出现过的老用户ui再次出现，且某一老用户出现的概率与TA以前出现频率的β(>0)次方成正比。

β<1亚线性优先延拓指数分布

β=1线性优先幂律分布HHu,DHan,XWang,Individualpopularityandactivityinonlinesocialsystems,PhysicaA,389,1065，2010建立两种分布的桥梁！科学与直觉小世界现象值得惊讶吗？聚类系数0.06大还是小？幂律度分布意味着什么？相同<k>的ER随机图L~logN相同<k>的ER随机图C=10-5相同<k>的ER随机图泊松分布Areyoucomparingtotherightthing?RandomNetworkUniverse(Allnetworkswiththesamenumberofnodesn)(2n(n-1)/2)AllRandomNetworkswithSameNumberofLinksAllNetworksWithSameDegreeDistributionAllRandomNetworkswiththeSameDegreeSequenceYourObservationOnSynchronizationIfthecouplingstrengthofascale-freenetworkisgreaterthanathreshold,thenthenetworkwillsynchronizenomatterhowlargeitisXWang&GChen.SynchronizationinScale-FreeDynamicalNetworks:RobustnessandFragility.IEEETrans.Circuits&Systems-I,Jan.,2002Synchronizabilityofascale-freenetworkisrobustagainstrandomremovalofnodes,butisfragiletospecificremovalofthemosthighlyconnectednodes相同的度序列，但是。。。不同的社团结构相同的度序列，但是。。。不同的同配性质(a)同配网络(b)中性网络(c)异配网络一切从零开始：用零模型验证零假设零假设(Nullhypothesis)：具有性质A的网络G也具有性质P验证零模型(Nullmodel)：与网络G具有相同规模和性质A的随机化网络作为零模型的随机化网络0阶零模型：相同<k>1阶零模型：相同P(k)2阶零模型：相同P(k,k’)0阶0阶零模型1阶2阶给定网络G生成零模型的随机重连算法相同<k>相同P(k)相同P(k,k’)一个例子：HOT模型的零模型0阶1阶2阶3阶基于零模型的拓扑性质分析典型应用：模体分析N(j)：拓扑特征j在一个实际网络中出现的次数Nr(j)：特征j在相应的随机化网络中出现的次数重要性剖面(SignificanceProfile)超家族Superfamily基于三元组重要性剖面，19个网络分成4个家族零模型的应用：同配性质分析Assortative:hubsshowatendencytolinktoeachother.Disassortative:Hubstendtoavoidlinkingtoeachother.零模型的应用：同配性质分析与具有相同度序列的零模型相比Z同配Z异配同一超家族，不同同配性CommunityStructure:

与谁比较？基于网络科学的社会网络分析测量网络数据发现网络性质建立网络模型分析网络行为控制网络性能提纲网络科学：社会网络分析群体智慧：网络上的社会学习蜂拥控制：集群行为涌现ClassicalBoidsModelReynolds,“Flocks,Herd,andSchools:ADistributedBehavioralModel”,ComputerGraphics,21(4),1987.

CollisionAvoidance(Separation)avoidcollisionswithnearbyagentsVelocityMatching(Alignment)

attempttomatchvelocitywithnearbyflockmatesFlockCentering(Cohesion)StayclosetonearbyflockmatesFlockingControlAlgorithmPositionVelocityQuasi-latticeBasicFlockingAlgorithmOlfati-Saber,IEEET-AC，2006;Tannereral.,IEEET-AC,2007Separation&CohesionAlignmentPositionVelocityBasicFlockingAlgorithmSeparation&CohesionAlignmentDoesitleadtoflocking?InTheory:G(0)connectedFragmentationG(t)connectedforalltFlockingInPractice:Tracking-NavigationalFeedbackVirtualleader:Navigationalfeedback:

PositionVelocityGoalofControl:TrackingFlockingwithaVirtualLeaderOlfati-Saber,FlockingforMulti-AgentDynamicSystems:AlgorithmsandTheory,IEEETransAC，2006Separation&CohesionAlignmentTrackingInTheory&InPractice:Alwaysleadtoflocking!Uninformedagent

FlockingwithminorityofinformedagentsInformedagentSeparation&CohesionAlignmentTrackingSimulationResults:N=100,M0=10提纲网络科学：社会网络分析群体智慧：网络上的社会学习蜂拥控制：集群行为涌现ComplexNetworks&ControlLab,SJTU人肉搜索为何几乎百发百中？教育医疗等却为何如此难以形成最佳共识？围脖上的意见领袖对粉丝的影响力有多大？热门话题、名人堂。。。群体智慧：大众比精英更聪明！Galton,Nature,1907

个人观察网络结构

校正规则个人观察与人交流校正

信念网络上的社会学习123一致性：能否形成共识？最优性：是否最佳共识？可控性：能否引导共识？ComplexNetworks&ControlLab,SJTUCasestudy:Whoissinging?StatespaceTruestate

PrivatesignalLikelihoodfunctionNetworkstructureBeliefComplexNetworks&ControlLab,SJTUEachagentshouldknowtheglobalstructureofthenetworkEachagenttriestodeducetheinformationofeveryotheragentBayesianSocialLearning:NetworkCaseComputationburden+highcomplexityComplexNetworks&ControlLab,SJTU人肉搜索有效克服了这两个困难！BayesianConsensus[Jadbbaie,Sandroni,andTahbaz-saleh2010]Bayesian+ConsensusComplexNetworks&ControlLab,SJTU(e)Thereisnootherstatethatisobservationallyequivalenttothetruestatefromthepointofallagentsinthenetwork.TheWisdomofCrowds(a)Thesocialnetworkisstronglyconnected;(b)Allagentshavestrictlypositiveself-reliances;(c)Thereexistsanagentwithpositivepriorbeliefonthetruestate;ComplexNetworks&ControlLab,SJTUSimilarityBreedsConnection:HomophilyPrincipleinSociologyComplexNetworks&ControlLab,SJTUUpdateruleSociallearningwithsimilarity-basedcommunicationConfidenceradiusComplexNetworks&ControlLab,SJTUr=0.3r=0.1r=0.02容忍差异才能一致N=100,20discriminativeagents,80indiscriminativeagentsTwostates,twosignals{H,T}Priorbeliefs:randomdistributionin[0,1]OriginallyconnectComplexNetworks&ControlLab,SJTUDifferencesBetweenTightandLooseCultures:A33-NationStudyIfoneweretoorderallmankindtochoosethebestset