讲稿综合组同济

TongjiUniversityinconformitywiththerequirementsforthedegreeofDoctorofPhilosophyResearchonDataForwardingProtocolDesignandPerformanceysisofSocialNetworksCandidate:ZhongLiStudentNumber:School/Department:ElectronicsandInformationDiscipline:EngineeringMajor:ComputerSoftwareandTheorySupervisor:Prof.ChangjunJiangDecember,可以根据他们的社交关系来发布和共享信息。目前，不仅传统PC端的社交动社交网络如此蓬勃发展，大量具有性的问题有待解决。其中，具有代表性致力于推广的4G网络，在一定程度上缓解了沉重的通信流量负载。这些通信流所以设计高效的数据传输协议是十分紧迫的；其次，随着移动端新社交应用的不断开发，一些对实时（如社交游戏、数据质量（如音频、）有高要求的社 越弱。使用两个簇参数(𝑚(𝑛),𝑟(𝑛))来描述节点现象的真实分布性质，其中掘，本工作给出了动态图模型，设计了自适应动态社区检测算法LASS（Loca-ActivityandSocial-Similarity）数据转发算法，算法的数据转发准则本工作首次研究了由移动用户、网络接入点（AP）和构成的混合通信架构AP进行通信的远距离节点。社区内的链路Support动车辆-移动车辆的会话模式。给出了近似目的集合、RSU重要性、时空接近性TongjiUniversityDoctorofsocialnetworksapplythesocialscienceandthewirelesscommunicationtechnologytonetworks.Inabroadsense,thesocialnetworkisacommunicationsystemcontainingsocialrelationsofusers.Inthenetwork,userscouldpublishandshareinformationbasedontheirsocialrelationships.Now,notonlymostonlinesocialapplicationsinPCterminalsprovidetheinterface,butalsomanynewlydevelosocialapplicationsattractpeople’sinterests.Asthedevelopmentofsocialnetworks,manychallengingproblemsarise.Amongthem,oneoftherepresentativeproblemsistheresearchondatafrowardingprotocoldesignandperformanceysisinsocialnetworks.Itcanbeexinedinthefollowingthreefolds.First,alongwiththeexplosivegrowthofusersin,communicationtrafficisalsoincreasingrapidly.The4Gnetworkwhichispromotedbyermentcanpartlyeasetheheavycommunicationtrafficload.Inthesecommunicationtraffic,exceptforthetraditionalvoicedata,therearestilllargeamountofsocialcommunicationflowsbroughtaboutbythenewsocialapplications.Inordertobalancethenetworkload,efficientdataforwardingprotocolisnecessarycomparedtobuildsomespecialinfrastructureforsocialnetworks.Second,withdevelosomenewsocialapplications,someapplicationswhichhavehighrequirementsforrealtime(i.e.,socialgames)anddataquality(i.e.,voice,s),arealsopromptingthestudiesonefficientdataforwardingprotocols.Besides,wealsoneedsometheoreticalresultsofnetworkperformancetoguidetheprotocoldesigningandnetworkconstructing.Inthiswork,weconsidertwogeneralproblemsbelow,oneistheproblemofsocialnetworksperformancescalinglaw,theotheristheproblemofdataforwardingprotocoldesignforsocialnetworks.Inthepreviousstudies,intheaspectofnetworkperformanceysis,therelatedworksdonotgivethepracticalmodelingandyticalmethodsforthenodemobilityinsocialnetworks.Intheaspectofthedataforwardingprotocoldesign,therelatedworksneglecttherelationbetweenthenetworkarchitectureandthesocialrelationships.Meanwhile,theyalsolackthedetailedexplorationonthesocialrelationships.Thus,thisworkgivestheboundsofthenetworkscalinglawandthehighperformancedataforwardingalgorithmsinsocialnetworks,withconsideringthenetworkTongjiUniversityDoctorofarchitectureandthesocialrelationships.Throughextensiveexperiments,thisworkalsoverifiestheefficiencyofthosealgorithms.Themaincontentandinnovationpointsarelistedasfollows.ThemaincontentandinnovationpointsarelistedasFirst,wirelessnetworkscalinglawdefinesthechanginglawsofbasicnetworkperformance(capacityanddelay,etc)alongwiththeincreasingnetworkscale(numberofnodes).Theresearchonnetworkscalinglawfocusesmoreontheattributesofsystemarchitecture,ratherthanconsideringtoomanydesigndetails.However,differentfromthetraditionalwirelessnetworkscapacityysis,forsocialnetworks,thisworkdesignsamodelwithsocialcharacteristicsanddefinesanactivitylimitcoefficientdenotingthenodestrength.Thelargerthestrengthis,theweakerthemobilityis.Wealsousetwoclusterparameters(𝑚(𝑛),𝑟(𝑛))todescribethedistributionpropertyofnodegrou,where𝑚(𝑛)denotesthenumberofclustersand𝑟(𝑛)denotestheradiusofthecluster.Wegivetheclassificationofthenodestrongmobilityandweakmobility,anddesigndifferentschedulingschemesandaroutingbasedonManhattanmulticasttree.Finally,weobtaintheorderofmulticastcapacityunderdifferentmobilitycases.Thisworkhassomeusefulresultsforchoosingthemodelanddesigningthenetworkprotocolinlargescalesocialnetworks.Second,wefindthatdirectlyusingthesocialpropertyminingmethodsandsomesocialmeasurements,whicharefromthegraphtheoryandcomplexnetworks,insocialnetworksmayresultinalowefficiencyperformanceindataforwarding.Thus,aboutsocialpropertymining,wegiveadynamicweightedgraphanddesignaself-adaptiveweighteddynamiccommunitydetection.Throughdefiningthecommunicationcriticalvalueandweighteddensityembryo,weavoidthelowweightededgesformingsomemeaninglesscommunities.Incommunitydynamicdetection,weusethelocalinformationtodealwiththenetworkchanges.Thedetectionmethodhasalowcomplexityandcouldobtainagooddetectionresult.Then,aboutsocialmeasurements,basedonthecommunitystructure,wedefinethenodelocalactivityandgiveaninnerproductmethodtomeasurethesocialsimilarity.Thisinnerproductsocialsimilaritycanprovideanewinmeasuringthesimilarity.Finally,weproposeLASSdataforwardingscheme,inwhichtheforwardingcriterionistochoosethemeetingnodewiththehighsocialsimilaritywiththedestinationastherelay.ThisschemecanguaranteeagoodperformanceofdataTongjiUniversityDoctorofforwardinginThird,tothebestofourknowledge,theproposedhybridarchitecture,consistingofphones,APsandbasestations,wasnotconsideredforanyMSNscenario.Underthishybridunderlyingcommunicationnetwork,weextendthetraditionalconceptofacommunity,withconsideringthoselongdistancenodesthatoftencommunicatewitheachotherthroughAPs,buthavenotdirectlylinks.So,thelinksinacommunityshouldcontainboththedirectphysicallinksandsomelongdistancelinkswithstrongcommunicationcapability.Thisworkgivesanewconceptofthecommunitystructure,callspace-crossingcommunity.Correspondingly,thespace-crossingcommunitydetectionmethodisalsogiven.Then,basedonthisnewkindofcommunity,wedefinethedifferentlocalactivityforcommonusersandstationaryAPs.Weproposeahighefficiencydataforwardingschemeunderthehybridunderlyingcommunicationnetworks,callSAIS.ThetwophasesinSAIS,socialattractionphaseandinfrastructuresupportphase,cantogetherguaranteeagoodperformanceindataforwardinginMSNs.,westudytheproblemofdataforwardinginaspecialkindofsocialnetworks-vehicularnetworks.Weconsiderthedifferencesbetweenthevehicularnetworksandcommonnetworks.Usingthelightweightsharedpartialtravelinginformationandvehiclesocialbehaviorinformation,weadvancethequalityofdataforwardinginvehicularnetworks.Wegiveseveraldefinitionsofapproximatedestinationset,RSUimportanceandspace-timeapproachability.Weproposeanapproachabilitybasedvehiculardataforwardingscheme,withconsideringthepartialtravelinginformationsharingandsocialrelationship.Infact,thehighefficiencyoftheschemecomesfromthedeterministicinformation(partialsharedtravelinginformation)andnon-deterministicinformation(vehiclesocialbehavior).Finally,theproblemsrequiringfurtherstudiesare:socialnetworks,scalinglaws,networkcapacity,hybridunderlyingcommunication mmunitystructure,space-crossingcommunity,localactivity,innerproductsocialsimiarity,vehicularnetworks,space-timeapproachability 第1章绪 移动社交网络标度律问 移动社交网络数据传输协议设 研究................................................................................................ 第2章预备知 移动模 会话类 第3章移动社交网络异构移动模型下组播容量标度律研 网络模 移动模 通信模 多播构 容量的定 强移动情况下的调度机 弱移动情况下的调度机 路由策略 强移动情况下的多播容量下 弱移动情况下的多播容量下 强移动情况下的多播容量上 第4章移动社交网中基于局部活跃性和社交相似性的数据转发协议研 社区检测算 MSNs机会式数据转发算 MSNs的网络架 动态 社区结构的描述性定 自适应动态社区检测算法 社区结构初始 动态算 局部活跃 社交相似 LASS算 性能评 LASS数据转发算法实 讨 数据集的选 通信临界值的选 边权重的定 局部活跃性的有效计算方 LASS的公平性问 部署实 预备知 运 本章小 网络模 关于跨空间社区的描述性定 跨空间社区检测算 SAIS数据转发算 局部活跃性和内积社交相似性两种情 SAIS数据转发算 SAIS算 数据 仿真设 SAIS数据转发算法实 第6章部分行驶路线信息共享对车辆网数据转发的功 部分共享信 跨空间社区结 时空接近 社交接近 基于接近性的度量准 基于接近性的数据转发算 数据集介 轨迹数据预处 在地图中部署 相遇记录的提取和跨空间社区检测结 仿真设 实验结果和分 第7章结论与展 致 参考文 个人简历、在读期间的学 与研究成 11章绪论1967年，Harvard大学的社会心理学家Milgram通过一个传递信件的小世界（SmallWorld）实验对现实社交网络进行了[1]，得到著名的“六度分隔”理论：世界上任何两个人，都可通过熟人找熟人的方式建立联系，而两人之间的平均最少“中介”数是6，此研究是对社交网络最早的具有性的研究。之后，人们把对社交网络的研究拓展到更为一般的复杂网络领域，社交网络则被看做是一种典型的复杂网络。1998年，Cornell大学的Watts和Strogatz在Nature上名为“小世界网络集体动力学”的文章，揭示出现实中的复杂网络具有高聚类性和相对短的平均路径长度，并建立了一个小世界网络模型[2]。1999年，NotreDame大学的Barabási和Albert在Science上名为“随机网络中标度的涌现”的文章，揭示了复杂网络的无标度（Scale- ）性质，并建立了一个无标度网络模型[3]。钱学森给出了复杂网络的一个较严格的定义：具有自组织、自相似、吸、小世界、无标度中部分或全部性质的网络称为复杂网络。这时期众多关于复杂网络的理论研究大量涌现[4]。最近几年，随着互联网的快速发展，特别是Web2.0的迅速兴起使得各种社交网络（OnlineSocialNetwork如雨后春笋般涌现，如人人网、等。这些网络的用户数少则几万，多则几千万甚至上亿，从而产生了规模越来越庞大的网络数据，而且人们也发现，社交网络正逐渐改变着数据的模式[5]。社交网络又作为一个独立的研究领域再次得到了学界和工业界的广泛关注。本质上说，社交网络是通过一个或多个互相依赖的连接而构成的一个实体（人、组织或系统）结构[6]。这些连接可以是由地理相遇，经济交换，商品，信息分发或参与活动等所带来的联系而产生的[7-9]。当前，基于PC端的社交网络渐成既定格局，社交网络正往成的飞速发展，无线移动设备（如智能、iPad等）逐渐成为人们日常生活的必促成了移动性社交网络（SocialNetworks，MSNs）的形成[10]。的眼球，如移动社交游戏Sony’sVita及一些基于地理的社交服务Foursquare、势已经。4G网络，在一定程度上缓解了沉重的通信流量负载。这些通1 ModelsGatheringSession等。在这种架构下，数据是要经过第应用或者服务提供商的，大进行通信和交流，并在物理世界维持着社交关系，如E-SmallTalker[19]、MobiClique[20]、Who’sNearMe[21]等。这是一种便利的通信方式，而且可以作社交关系信息可以提升数据转发的性能[22]。在本，我们主要在协议设计方法中考虑节点的社交群体特性和节点的社交特性这两大类。对于前者，社区结构是一个很好的刻画指标。社区是指节点联系非常紧密且内部链路多于外部链路的一种结构[23-25]。如果人们具有共同，或者与他人频繁相遇，则这些人可以形成一个社区。然而，社区定义的主11观性非常强，目前还没有统一的社区定义。社区检测与图论中的图分割（graphpartitioning）类似。图分割的主要目的是将网络大致等分成给定数量的子网络，使得子网络之间的边的连接尽可能地少，通常是通过迭代分割将网络划分成子网络的：先将网络按分成两个子网络进行最优划分，然后再重复对这些子网络进行最优二分，直到划分成给定数量的子网络。而社区检测是根据社交网络点间的联系把其中潜在的群体特性挖掘出来的方法。如果节点间的联系是通过自上报的逻辑关系形成的，那么社区检测的结果即为显性社交群体；如果节点间的联系是通过物理相遇潜在形成的，那么社区检测的结果即为隐性社交群体。不管是哪一种，因为社区结构表征了一组共同点的，所以这对数据传输协议继点的选择有很大指导性作用。譬如社交网络中的分发就是明显的例证[26]。对于后者，中心性（Centrality），相似性（Similarity），连接力度（TieStrength）等从复杂网络领域来的度量指标，可以作为节点的社交特性的体现。对于中心性，常用的有度中心性（DegreeCentrality）、介数（BetweennessCentrality）和紧密中心性（ClosenessCentrality）。对于相似性，常用的有欧几里得距离、夹角余弦、海明距离、Pearson相关系数和Jaccard距离等。以上各种中心性和相似性我们会在第2章中详细介绍。节点的社交特性，反映了用户在社交网络中的所处的位置和作用，所以对于数据传输协议设计也起着重要作用。譬如中的效应是一个有力的例证[27,28]。模型的现实性10]。而移动社交网络虽然可以看做一种无线网络的应用类型，但关于MSNs数据传输协议设计方面，首先，虽然社交网络与复杂网络和图论方法，来建立MSNs中的数据传输协议会导致协议可能的低效性。譬如，目前社区检测所的环境为社区数量事先未知，结构可能会有交叠，社区关系加着从复杂网络到移动社交网络转化过是否能真正体现社交特性的问题。那么MSNsMSNs研究是基于AdHoc组网方式下提出，相应的社区属性挖掘方法和协议算法也均MSNsMSNs的含义非常广泛，如生物信息网络，车辆网络等都含有社交网络的。在这些 与传统的无线网络容量分析不同，针对移动社交网络，我们设计了具有社交特性的移动模型，定义了活跃限制系数来表示移动限制的强度，强度越大，移动性越弱。使用两个簇参数(𝑚(𝑛),𝑟(𝑛))来描述节点现象的真实分布性质，其中𝑚(𝑛)表示簇数量，𝑟(𝑛)表示簇半径。给出了节点强弱移动的分类，并分别设计了不同的调度机制和基于曼哈顿多播路由树的路由策略，得到了强弱移动情况下多播容量阶的结果。第二，移动社交网中基于局部活跃性和社交相似性的数据转发协议研究属性发掘，我们给定动态图，设计了自适应动态社区检测算法SAWD相似性定义可为衡量节点的社交相似性提供新的见解。最后，提出LASS（Loca-ActivityandSocial-Similarity）数据转发算法，算法的数据转发准则是选第三，混合通信架构下移动社交网中基于跨空间社区结构的数据转发协议研究我们首次研究了由移动用户、网络接入点（AP）和构成的混合通信架AP进行通信的远距离节点。社区内SAIS（SocialAttractionandInfrastructureSupport。该算法的两个阶段可共同保轻量级的部分行驶路线信息（而不是大型地图或道路信息”与“车辆社交行为架构下研究移动车辆-RU重要性、时空接近性等概念，并提出了基于接近性（iy）的数据转发算法。该算法充分考虑了部分行驶路线信息共享在具有社交行为属性的车辆网中对数第三章研究移动社交网络异构移动模型下组播容量标度律。给出了MSNs考虑新的适用于移动社交网络的社交属性发掘算法和社交度量方法，给出基于内积的相似性度量，并就此设计高效MSNs数据转发协议。第五章研究混合通信架构下移动社交网中基于跨空间社区结构的数据转发协议。首次给出了跨空间社区的概念和检测方法，明晰了MSNs混合通信架构的实际应用意义，提出了混合通信架构下MSNs的高效数据转发算法，验证了跨空间社区在数据转发中的积极作用。第六章研究部分行驶路线信息共享对车辆网数据转发的功效。充分考 222章预备知识可以从以下几个方面来分类：部署模型、扩展模型、移动模型、通信/干扰模型和会话类别等。在本，我们对移动模型和会话类别进行特别说明。随机行走模型（RandomWalk随机路点移动模型（RandomMobility（RandomMobility型无边界仿真区域移动模型（ASimulationAreaMobility高斯马尔科夫移动模型（Gauss-MobilityoftheRandomWalkMobility城市街区移动模型（CitySection指数相关移动模型（ExponentialRandomMobility列移动模型（ColumnMobility追踪移动模型（PursueMobility参照点组移动模型（ReferencePointMobility型单播广播选播组播数据收集Data⋯𝑚个目的点中的𝑑个(1≤𝑑≤𝑚≤𝑛−1)点。在无线传感器网络中的，数据收集（DataCollection）和数据聚合（Data给定两个函数𝑓(𝑛)≥0，𝑔(𝑛)≥0𝑓(𝑛)~𝑔(𝑛)lim𝑓(𝑛)⁄𝑔(𝑛)=𝑓(𝑛)=𝜊(𝑔(𝑛))lim𝑓(𝑛)⁄𝑔(𝑛)=𝑓(𝑛)=Ο(𝑔(𝑛))代表limsup𝑓(𝑛)⁄𝑔(𝑛)=𝑐<∞𝑓(𝑛)=𝜔(𝑔(𝑛))等价于𝑔(𝑛)=𝑓(𝑛Ω(𝑔(𝑛))等价于𝑔(𝑛Ο(𝑓(𝑛))。另外，定义两个函数有：max{𝑓(𝑛),𝑔(𝑛)}={ 𝑖𝑓𝑓(𝑛)= 𝑖𝑓𝑔(𝑛)=min{𝑓(𝑛),𝑔(𝑛)}={ 𝑖𝑓𝑓(𝑛)= 𝑖𝑓𝑔(𝑛)=假设社交网络用图𝐺表示，网络中有𝑛个节点，下面我们给出几个常见的中心性度量方法，扩展性的知识见文献[30-32]。度中心性（Degree么该就居于中心地位，在该网络中拥有较大的“权力”。在这种思想的指导𝐷𝐶(𝑖) 𝑛−介数/中间中心性（BetweennessCentrality）[30,介数描述，它测量的是对资源控制的程度。一个在网络中介数越高，就1𝐵𝐶(𝑖)=(𝑛−1)(𝑛−

，紧密中心性（ClosenessCentrality）[30,𝑛−𝐶𝐶(𝑖)= 𝐷𝑗∈𝐺,𝑗≠𝑖离、PearsonJaccard距离[36]等，这些度量常用于社交网络、推荐系Web搜索聚类分析[37-41]等领域。每种度量准则在不同的环境下各有其优缺点[40,42]。关于相似性度量方法的知识参见文献[42]。（1）得距离。两个𝑛维向量A(𝑥11,𝑥12,…,𝑥1𝑛)与B(𝑦11,𝑦12,…,𝑦1𝑛)间的欧式距离：𝑑=√∑(𝑥1𝑘−𝑦1𝑘)2两个等长字符串𝑠1与𝑠2之间的距离定义为将其中一个变为另外一个所需要作的最小替换次数。其应用领域一般为信息编码学，为了增强容错性，应使得编码间的最小距离尽可能大。余弦距离余弦距离，也称为余弦相似度，是用向量空间中两个向量夹角的余弦值作为衡量两个间差异的大小的度量。向量是空间中有方向的线段，如果两个向量的方向一致，即夹角接近零，那么这两个向量就相近。而要确定两个向量方向是否一致，这就要用到余弦定理计算向量的夹角。两个𝑛维向量A(𝑥11,𝑥12,…,𝑥1𝑛)与B(𝑦11,𝑦12,…,𝑦1𝑛)间的余弦距离： 𝑐𝑜𝑠(𝜃)

𝑥1𝑘2 𝑦

𝑘=1余弦距离使用两个向量夹角的余弦值作为衡量两个间差异的大小。相比欧氏距离，余弦距离更加注重两个向量在方向上的差异。欧氏距离和余弦距离各自有不同的计算方式和度量特征，因此它们适用于不同的数据分析模型：欧氏距离能够体现数值特征的绝对差异，所以的用于需要从维度的数值大小中体现差异的分析；余弦距离的是从方向上区分差异，而对数值不敏感。之后，余弦距离为了解决对维度上数值的差异不敏感这一问题，通过所有维度上的数值都减去一个均值，得到了调整余弦相似度（AdjustedCosineSimilarity）。Pearson相关系数Pearson相关系数是衡量随量X与Y相关程度的法，相关系数的取值范围是[−1,1]。相关系数的绝对值越大，则表明X与Y相关度越高。当X与Y线性相关时，相关系数取值为1（或1（。两变量X与Y间的Pearson相关系数可通过以下计算：𝑁∑𝑋𝑌−∑𝑋∑𝜌𝑋,𝑌= √𝑁∑𝑋2−(∑𝑋)2√𝑁∑𝑌2−(∑Jaccard距离Jaccard距离用两个两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。两个集合A与B间的Jaccard距离：|𝐴∪𝐵|−|𝐴∩𝐽𝑑

|𝐴∪在这里，为了使本文结构更加清晰，我们用如下图示的方式来给出第3-6章所使用的网络架构，见图2.133 蜂窝网络 蜂窝网络2.1网络架构与各章节演进关系3一个活跃性指数𝛾和两个簇系数(𝑚(𝑛)𝑟(𝑛))来描述移动模型的异构性，其中𝛾0,1]表示节点移动的强度，𝑚(𝑛)表示簇数量，𝑟(𝑛)表示簇半径。我们根据每的调度机制和基于曼哈顿多播树的路由策略。假设有𝑛𝑠=Θ(𝑛)𝑛节点的多播容量阶为 )且𝜃(𝑛)=𝑛2；在弱移动情况下，当𝑛𝑑𝑛√𝑂

𝑚(𝑛))，多播吞吐量为Ω(

2

𝑑=

𝑚(𝑛)) 𝑛

=AdHoc网络移动模型发展领域的相关研究。首先，对于静态无线网络，Gupta和Kumar在文献[13]定义了协议干扰模型和物理如文献[43,44]中研究的广播问题，文献[45-47]中研究的多播问题，以及文献[48]中研究的数据汇集问题。其中，Keshavarz-Haddad等人在文献[43]中研究了广播容量问题，每会话的广播容量数量级为Θ(1/𝑛)。Shakkottai等人在文献[46]中研comb路由机制，这种机制下每会话的多播吞吐量数量级为Ω(1)，其中

数量。Li在文献[47]中针对随机网络假设𝑛𝑠=Ω(𝑙𝑜𝑔𝑛𝑑√𝑛𝑙𝑜𝑔𝑛/𝑛𝑑)，于是当𝑛𝑑𝑛 )当𝑛= 时，每多播会话容量数量级为Θ(1)。Liu等人在文献[48]络容量研究中。其中，针对信道模型，Franceschetti等人在文献[49]中证明节点随机部署时网络的单播容量为Θ(1)其次，对于移动无线网络，-携带-转发协议可以进一步利用移动性来提如此粗糙的假设。文献[68,69]表明，在大多数应用场景下，节点在大部分时间内只在某一区域内移动，且很少到达其他区域。这种现象可称为有限/局部移动移动性外，文献[70,71]在长期的实验中发现了另一现象，即，许多节点往Garetto等人在文献[72]中基于类似的这种现实（局部移动性+簇结构）移动1的范围内，则每节点的单播吞吐量为Θ(

后，基于文献[72]，Huang等人在文献[73]中把网络拓展为有基础设施支持的网络，他们证得在强移动情况下每节点的容量达到Θ(1Θ(𝑚𝑖𝑛𝑘2𝑐𝑘))，其他 情况下的每节点容量为Θ(𝑚𝑖𝑛𝑘2𝑐,𝑘)) 文献[74]中，Peng等人研究了异构性提升多播容量的问题，但是该研究只针对静态网络，且异构性只是针对簇的异构性。文献[75]AdHoc网络的延移动节点𝑖home所有多播会话点的数方格𝐴𝑡𝑒𝑠home𝜇动性越弱。使用两个簇参数(𝑚(𝑛),𝑟(𝑛))来描述节点现象的真实分布性质，其次，基于簇模型(𝑚(𝑛)𝑟(𝑛))，我们定义𝜁(𝑛)=√𝑙𝑜𝑔(𝑚(𝑛)𝑚(𝑛)界传输范围，即所有节点为静态节点时，此传输范围可保证网络的连通性[76]。（1）强移动情况𝜁(𝑛)=𝜊(1每节点的多播容量为 )。节点传输范围为

=Θ(1)调度机制和路由策略可得多播容量下界为λ= （2）弱移动情况𝜁(𝑛)=𝜔(1=Θ(𝑙𝑜𝑔𝑚(𝑛))

2Ω( 当2

= λ 𝑛1

Ω( 当𝑛𝑑= 节点𝑖在时刻𝑡的位置标示为𝑋𝑖(𝑡)1≤𝑖≤𝑛。节点𝑖与𝑗在时刻𝑡的距离定义为𝑑𝑖𝑗(𝑡)=∥𝑋𝑖−𝑋𝑗∥1不同；二，整个网络点密度分布具有空间异构的特点。定义一个活跃指数𝛾，𝛾∈[0,1]，我们有活跃限制系数𝜃(𝑛)=

2𝑋ℎ移动的节点𝑖的密度函数∅(𝑋)=∅(𝑋−𝑋)

𝑠(𝜃(𝑛)∥𝑋−𝑋ℎ

， ， 𝑠(𝜃(𝑛)∥𝑋−𝑋ℎ 机行走模型，随机路点模型，运动模型等。但是，这些模型与现实情况不符。了一个由二元参数(𝑚(𝑛),𝑟(𝑛))所描述的簇模型，𝑚(𝑛)代表簇个数，𝑟(𝑛)代表簇home点”，构建移动模型的过程如下：3.1图3.1中的第一列为三种不同对象在整个网络中均匀分布。𝑚(𝑛)=𝛩(𝑛𝑣)𝑣∈[0,1]并且𝑟(𝑛)=𝛩(𝑛−𝜚)𝜚∈[0lim𝑚(𝑛)𝑟2(𝑛)=𝑣−2𝜚<0并且0≤𝜚≤2缩[73]。特殊的，当𝑚(𝑛=𝑛3.2所示为簇模型𝑆𝐼𝑁𝑅

≥ 𝑁0+

其中，𝑁0代表接收端的背景噪声，𝛼>2是信号因子，𝛽代表目的节点其相应的home点集合由ℎ,𝑋ℎ,…,𝑋ℎ}来表示。在不同的多播会话中，每个点𝑣 𝑛𝑠=𝛩(𝑛)点作为源节点，每个源节点对应𝑛𝑑个目的节点，即网络中存在𝑛𝑠个多播会话。我们𝑣𝑖𝒱𝑖,𝐷用来表示一个多播会话，其中𝑣𝑖是一个源节点，𝒱i,D表示𝑣𝑖的目的节点集合，1≤𝑖≤𝑛𝑠。相应的，由于每个节点𝑣𝑖home点𝑋𝑖ℎ，所以一个多播会话中会有𝑛𝑑home点。𝑛𝑑home点也构成home点集合，记为𝒳ℎ={𝑋ℎ𝑋ℎ𝑋ℎ 我们通过定义两节点的关键传输范围𝜁(𝑛)=√𝑙𝑜𝑔(𝑚(𝑛))/𝑚(𝑛)来保证任意3.3所示，AC中心通信，在条件𝜁(𝑛)=√𝑙𝑜𝑔(𝑚(𝑛))/𝑚(𝑛)下，这个 𝑠(𝜃(𝑛)∥𝑋−𝑋ℎ∥)𝑑𝑋的阶为1[72]。通过这个结果， 们可以推导出，节点以高概率活动在的阶为 大致限制在Θ(1)1：如果网络和移动节点满足条件𝜁(𝑛)𝑜(1)情况为强移动2：如果网络和移动节点满足条件𝜁(𝑛𝜔(1)情况为弱移动2中，移动性是比较微弱的，在一定3.1[72]：假设根据簇模型(𝑚(𝑛)𝑟(𝑛))，把{𝑋1𝑖≤𝑛}home点集合布置在网络𝒪上，区域 ≥16被划分成规则的小方格，每个小方格面积 ≥16𝛿)𝜁2(𝑛),𝛿>0，并且小方格𝐴𝑡𝑒𝑠home点的数量为𝑁ℎ(𝐴𝑡𝑒𝑠)。home布在小方格当且仅当𝑛|𝐴𝑡𝑒𝑠|<𝑖𝑛𝑓𝑁

)≤

)<2𝑛|𝐴𝑡𝑒𝑠|

Θ(1)𝑑𝑖𝑗(𝑡)<

𝑚𝑖𝑛(𝑑𝑘𝑗(𝑡),𝑑𝑘𝑖(𝑡))>(1+调度机制𝒮⋕可以保证节点𝑖和节点𝑗带宽在两个传输方向上是一样的。文献[76]使用Θ(1)在弱移动情况下，我们有𝜁(𝑛)=𝜔(1)𝑅𝑇=Θ(𝜁(𝑛))调度机制𝓢𝐛：基于类似于引理3.1𝐾2-TDMA3.4所示，小方格边长为√(16+𝛿)𝜁(𝑛)3.2：在物理模型下，对任意阈值𝛽，存在一个常数𝐾,0𝐾，可以保证‖𝑋ℎ−𝑋ℎ‖≤√5√(16+ 𝑃∙‖𝑋ℎ−

≥𝑃∙(√5√(16+

ℎ

)

−𝑋

≤∑8𝑖∙

𝐾𝑖−2

)(

16+𝛿𝜁𝑛∞𝑁+∑

−

≤𝑁+∑𝑃∙8𝑖∙[(𝐾𝑖−

)() 0

16+𝛿𝜁𝑛当𝛼>2

𝑖=1𝑃∙5−2∙(√(16+𝑆𝐼𝑁𝑅≥𝑁+𝑃∙(√(16+𝛿)𝜁(𝑛))−𝛼∙ 0我们令𝐺(𝑛)=√(16+𝛿)𝜁(𝑛)

𝑖=1

𝑃(52−𝛽∙ )−𝑁(𝛼+𝑃∞ 𝑆𝐼𝑁𝑅−𝛽≥(𝐺(𝑛𝑁(𝛼+𝑃∞ 𝑖=1对任意给定𝛽，存在一个足够大的常数0<𝐾<∞， 5−2−𝛽∙ >𝑖=1(𝐾𝑖−考虑一个多播会话𝑣𝑖𝒱𝑖,𝐷home点，所以相应的我们有𝑋ℎ→𝒳ℎ3.1所描述的路由策略ℛ，我们为每一个多播会话构 3.1中，在强移动情况下，小方格的边长为𝑐，c3.1home点。其次，此边长与移动半径同阶都为Θ(1)，它可以使相邻的两个小方格中的节点在调度机制𝒮⋕相遇。类似的，在调度机制𝒮b3.1中小方格的边长为√(16+𝛿)𝜁(𝑛)3.1把整个网络区域分隔成一系列规则的小方格。每个小方格𝜁(𝑛)homeijhome点标示为(𝑖𝑗)；独立随机的选择𝑛𝑑个home点，形成一个目的点集合，标示为𝒳ℎ={𝑋ℎ,𝑋ℎ,…𝑋ℎ 对树EST(𝑋ℎ)中的每个连接𝑢𝑣，假设节点𝑢和节点𝑣分别在小方格(𝑖,𝑗)和小方格(𝑖,𝑗)。在方格(𝑖,𝑗)或者(𝑖,𝑗) 𝑢

𝑣

𝑢

𝑣 对树EST(𝑋ℎ)的每条边𝑢𝑤，在每个被连接𝑢𝑤所的方格中，找到个home点。依次连接这些home点，形成接点𝑢和点𝑣路径，从𝒳ℎ中移除环，这个结果数树标示为MT(𝑋ℎ)； 因为每个home点都有一个移动节点在它附近，根据上述构建的树MT(𝑋ℎ)MTR(𝑣 输出：得生成树

home点𝑋ℎhome点集合𝜒ℎ处于状态，于是有𝑛𝑑+1个连通单元for𝑖=1:

将部署区域分割为最多𝑛𝑑+1𝑖1/⌊√𝑛𝑑+1−这两个home点相连，我们可使两个连通单元合并；end概率链路容量𝝁𝑺(𝒊𝜇𝑆(𝑖,𝑗)=其中，𝜋𝑆(𝑡)代表在平稳遍历调度机制𝑆下，在时刻t并发传输的节点对集合。表示由{𝑋ℎ,𝑋ℎ}所生成的Borel-field。概率链路容量定义了节点𝑖和节点𝑗之间的最 引理3.3[76]：在强移动情况下𝜁(𝑛)=𝑜(1)，使用调度机制𝒮⋕⋕点(𝑖𝑗)和任意有限值𝑐1>0⋕𝜇𝑆(𝑖𝑗)=Θ(𝑃𝑟{ 𝑐1|ℱ𝑖𝑗 𝜇𝑆⋕(𝑖,𝑗)=Θ(𝑔(𝑛)𝜂(𝜃(𝑛)∥𝑋ℎ−𝑋ℎ∥))其中𝑔(𝑛)=

并且𝜂(∥𝑌∥)= 𝑠(∥𝑋−𝑌∥)𝑠(∥𝑋∥)𝑑𝑋 引理3.4[47]假设有𝑛个独立 量

∈{0,1}且𝑝=

=1)设𝑋= 𝑋

Pr(𝑋≤𝜁)≤ 0<𝜁< 𝜁(1−Pr(𝑋>𝜁)<(𝜁− 当𝜁>引理3.5[47]：对于部署于网络𝑎2中的𝑛𝑑+1𝐸𝑆𝑇(𝑋)表示由算法2生成的德生成树(EST)，于是有𝑘1,2,𝑛𝑠‖𝐸𝑆𝑇(𝑋)‖≤2√2∙√𝑛𝑑∙𝑎引 3.6：给定网格分隔𝐴𝑡𝑒𝑠，在强移动情况下，一个多播流流经𝐴𝑡𝑒𝑠的概率

。+ ,。

的边长为𝑐。𝑃𝑟(𝑙

)表示多播流经过

𝑙ℎ+ 𝑐(𝑙ℎ+ 𝑃𝑟(𝑙,𝐴𝑡𝑒𝑠)=𝜃2(𝑛) 𝑐

+1) + 𝑐(𝑙ℎ+𝑙𝑣)≤√2𝑙𝑐≤

𝑃𝑟(𝑙,𝐴𝑡𝑒𝑠)=𝑚𝑖𝑛(𝜃(𝑛)+𝜃2(𝑛),𝑃𝑟𝑎𝑙𝑙(𝑙,𝐴𝑡𝑒𝑠)=𝑂(𝑛𝑠∙

𝑃𝑟𝑎𝑙𝑙(𝑙,𝐴𝑡𝑒𝑠)=2𝑛𝑠∙ + 𝜃这里我们给出如何运用路由策略ℛ和调度机制𝒮⋕来获得强移动情况下多播容量的下界。假设存在一个多播会话1⟶{1121𝑘hoeℛhoe𝒮⋕3.5hoehoehoehoehoe点的一棵曼hoe1传输数据到他其中的一个目的节点1。根据曼hoe点容量的下界为𝜆=(1 证明：假设𝐴𝑡𝑒𝑠和𝐵𝑡𝑒𝑠为相邻方格。设𝑁ℎ(𝐴𝑡𝑒𝑠)和𝑁ℎ(𝐵𝑡𝑒𝑠)分别表示home点2因为𝜁(𝑛)=𝜊(1)，考虑引理3.1，我们有𝑁 )= =𝑁 结合引理 ) )∙𝑁 )𝑁 因为𝑑

=√5𝑐，结合式(3.5)#

)=𝑡𝑒𝑠其中𝑐取合适值，以保证𝜂(√5𝑐)>0 𝑂(𝑛𝑠∙

() 𝜃 𝜃𝑆#

)∙𝑁𝐴 )𝑁 𝜆 𝑛∙(4√𝑛𝑑𝑐+ 𝜃2(𝑛)1𝜆Ω )引理3.7：给定网格分隔𝐴𝑡𝑒𝑠，在弱移动情况下，一个多播流经𝐴𝑡𝑒𝑠𝑚𝑖𝑛(4√(16+𝛿)𝜁(𝑛)√𝑛𝑑+2𝑛𝑑(16+𝛿)𝜁2(𝑛),1)2Ω( 当2

=𝑂(𝑚(𝑛)𝜆 𝑛1

Ω( 当𝑛𝑑=

为相邻方格。因为ζ(𝑛)=𝜔(1)，根据𝐾2−𝑇𝐷𝑀𝐴O(𝑛𝑠∙(4√(16+𝛿)𝜁(𝑛)√𝑛𝑑+2𝑛𝑑(16+𝛿)1𝜆≥ 𝑛𝑠∙(4√(16+𝛿)𝜁(𝑛)√𝑛𝑑+2𝑛𝑑(16+𝛿)√Ω( 当√

=𝑂(𝑚(𝑛)𝜆 𝑛1

𝑙𝑜𝑔𝑚(𝑛)Ω( 当𝑛𝑑= ∑𝑖:𝑋ℎ∈𝐼ℒ∑𝑗:𝑋ℎ∈𝐸ℒℎℎ节点的网络容量的上界为𝜆≤ ℎℎ𝑠:𝑋

𝑑:𝑋

𝑠 𝑑引理3.8[72]：根据假设𝑥3𝜂(𝑥)𝑑𝑥<∞，对任意简单规则凸闭合曲线ℒ1𝜃2(𝑛)

𝜂(𝜃(𝑛)∥𝑋−𝑌∥)𝑑𝑥𝑑𝑦= 𝑋∈𝐼ℒ 引理EMST总边长渐进于𝜏(𝑑)𝑛𝑑𝑎，其中𝜏(𝑑)表示只与维度𝑑有关的一1( 证明：我们令𝑙𝑘,𝑖表示第𝑘个多播会话第𝑖条边的边长。网络面积归一化为𝑙𝑘,𝑖通过ℒ的概率为𝑙𝑘,𝑖𝑐𝑜𝑠𝜓𝑘,𝑖，其中𝜓𝑘,𝑖表示𝑙𝑘,𝑖随量𝜀𝑘,𝑖定义如下

当𝑙𝑘,𝑖𝑘,𝑖= 当𝑙𝑘,𝑖𝑛𝑠 𝑛𝑠 𝑛𝑠𝐹ℒ=𝐸(∑∑𝜀𝑘,𝑖)=∑∑𝐸(𝜀𝑘,𝑖)=∑∑𝑘=1𝑛𝑠

𝑘=1 𝑘=1∑∑𝑙𝑘,𝑖𝑐𝑜𝑠𝜓𝑘,𝑖≥𝑘=1因此，我们有𝐹ℒ≥𝑐2𝑛𝑠√𝑛𝑑 𝜇𝑖𝑗≤𝑛2𝑔(𝑛) 𝜂(𝜃(𝑛)‖𝑋− 𝑋∈𝐼ℒ ∑𝑖:𝑋ℎ∈𝐼ℒ∑𝑗:𝑋ℎ∈𝐸ℒ 𝑛2𝑔(𝑛) 𝜂(𝜃(𝑛)‖𝑋− 𝑋∈𝐼ℒ根据引理3.8，我们最终有𝜆= )AdHoc为组织方式的异构移动社交网络的多播容量上的簇参数(𝑚(𝑛),𝑟(𝑛))来对移动模型进行了改进和拓展。通过利用不同的调度机4个节点所隶属的共同社区越多，两个节点间社交相似性越大。在本章决这一问题，我们在本章中设计了一种基于动态网络社区检测的MSNs数LASS（Loca-ActivityandSocial-Similarity）了每个社区内成员的内部活跃性（即局部活跃性）LASS算法的性能优于其他几种流行的社交网络数据转发算法。业网络中。综述性文献[25]和[78]可以作为这一领域的读物。在静态社区检测算法研究方面，和Girvan做出了先驱性的工作，MODULARITYQ的概念来评估社区检测结果的质量。之后，Leicht等人分别在文献[80]和[81]中将上述工作进一步拓展为和有向的社区检测。很多基于MODULARITYQ的优化算法也被不断提出[82-85]。此外，Palla等人在文献[86]K-CLIQUE里程碑式测算法被提出[37,87-91]。其中，Hui的社区检测算法[87]AFOCS算法[37]均为非集中式算法，进一步AFOCS可同时处理动态和交叠的社区结构。定程度上提前限制了社区的尺寸。文献[88]FacetNet算法则要求事先预知(extremedegeneracy)问题[92]。文献[91]iLCD算法，对于网络的动态变化考虑不充分，只研究了网络中动态增加边的情况。Hui的分布式算法[87]无和Spray-and-Wait[94]（DTNs）SimBet的数据转发算法，该算法利用节点中间中心性提高数据转发的成功概率。Hui等人在文献[99]针对DTN网络提出了名为BUBBLERAP的算法，该算法利用K-CLIQUE社区结构点的全局和局部中 作为相似性来引导高效的数据转发。Wu等人在文献[102]中提出一种基于communityhome的移动社交网络多副本路由算法。4.1.2节所详述。虽然没有明确说明，但是许多文献普遍基于如每个节点不同程度的局部活跃性；在交叠区域内，在一起的方形，三角形或圆形代表如图4.1(a)所示，假设Laura、Thomas和Stephen是大学橄榄球的会发送一条信息。Thomas与许多其他成员频繁交流（即：他的局部活跃性择行为活跃的节点还是选共同较多的节点？如果我们选择Stephen，则可能较高的节点作为中继节点。因此，我们提出一种基于局部活跃性和动态网络SimilarityLASS算法确定社区结构和节点局部活跃性。我们定义通信临界值和密两种类型，进而利用局部信息来处理网络的动态变化。4.8.1NMI（规范化交互信息）SAWD算法获得高质量检测结果（即检测结果与真同越多且在社区内的局部活跃性较高，这可以保证数据转发的优异性能。于蜂窝网络的，则将出现一些问题。首先，当前蜂窝网络已经承载了移动通能[6,18,103]。AdHoc模式。该模式不仅可为蜂窝网络分AdHoc的机会式数据转发问题（4.1.2节所详述机制在部署时必须使用集中式协调（coordination）机制。例如文献[99]中的BUBBLERAP算法，数据包持有节点需要知道它即将到达的节点是否与目的节有集中协调器的支持，那么所有这些所谓的基于AdHoc的策略均无法运行。MSNsAdHoc网络往往共存。作为集中式协调器，蜂窝AdHoc网络负责更为繁重的数据传输任务。这与从蜂窝网络卸载部分沉重的网3GLTE通信技术，AdHoc且表示为𝒢={𝐺0𝐺1𝐺𝑡，其中𝐺𝑡=(𝑉𝑡𝐸𝑡𝑊𝑡𝐹𝑡)表示在时刻𝑡捕捉的网络快照，𝑉𝑡表示节点集合，𝐸𝑡={(𝑢,𝑣)|𝑢,𝑣∈𝑉𝑡表示边集合，𝑊𝑡={𝑤𝑡∈[0,1)|𝑢,𝑣𝑉𝑡且(𝑢,𝑣)𝐸𝑡}表示时刻𝑡时边的权重集合，𝐹𝑡𝐸𝑡→𝑊𝑡表示为边赋予权重的映射。节点集合和边集合会随着时间的变化而变化。对节点𝑢，设𝑑𝑡𝑢根据节点在移动社交网络中的物理移动令 =1代表在时刻𝑡(0≤𝑡<

代表从时间𝑡𝑛𝑜𝑤−∆ 𝑙𝑡代表从时间 𝑡=𝑡𝑛𝑜𝑤−∆ 所有节点的相遇次数之和，0𝑡𝑛𝑜𝑤。我们定义在当前时刻𝑡𝑛𝑜𝑤节点𝑢和𝑣的 𝑤𝑡𝑛𝑜𝑤 𝑡=𝑡𝑛𝑜𝑤−∆𝑢𝑣∗ ∗

为了避免设备检测相遇的不对称性，我们假设𝑤𝑡𝑛𝑜𝑤=𝑤𝑡𝑛𝑜𝑤 经验值，根据文献[99,104]所述，我们统一对所有算法设定∆为6∗3600s。，={ 其中元素𝐶𝑡∈𝒞𝑡并且其生成子图形成了图𝐺𝑡的一个社区；𝑘个网络快照中的社区数量。尤其地，我们设𝐶𝑡⋂𝐶𝑡≠∅ 即{𝐶𝑡|𝑖∈𝐶𝑜𝑚𝑡(𝑢)}；令𝒞𝑡(𝑢)表示在时刻𝑡包含𝑢的所有社区结构组成的集合。本𝑂𝑡(𝑢,边(𝑢,𝑣)在时刻𝑡时生成的密度Φ(𝑂𝑡(𝑢,Γ(𝐶𝑡, α𝑆𝑆𝑡(𝑢,自适应动态社区检测算法我们借鉴文献[37]中的AFCOS算法提出本章的自适应动态社区检测算Dynamic存在重复性操作。文献[37]已经证明了算法的正确性。此外，文献[37]还给出了AFOCS、K-CLIQUE算法和基于MODULARITYQ算法的性能比较。当K-CLIQUE算法和MODULARITYQ算法应用于动态图时，两种算法与社区准则。其次，SAWD将增加和移除节点或边的情况划分为“池内”和“池外”两大类情况，以便利用局部信息处理络变化。SAWD分为两个步骤：（2去局部的处理发生变化的社区结构（即4.6.2节的动态算法。4.34.5糙社区将会合并，形成初始社区结构。4.1通信临界值（CommunicationCritical定义权值集合{𝑊𝑡}的中位数为在时刻𝑡时的通信临界值，记为{𝑥𝑡} 定义4.2密度胚WDE（WeightedDensityEmbryo）给定时刻𝑡时的一条边(𝑢,𝑣)，所有节点属于𝑁𝑡(𝑢)⋂𝑁𝑡(𝑣)的𝐺𝑡(𝑥𝑡)生成子图称为时刻𝑡时由(𝑢,𝑣)生成的𝑥𝑡级密度胚，记为𝑂𝑡(𝑢,𝑣;𝑥𝑡)。出于简便起见且不引起，将𝑥𝑡级密度胚𝑂𝑡(𝑢,𝑣;𝑥𝑡)、𝑂𝑡(𝑢,𝑣;𝑥𝑡)的节点和边集合分别记为𝑂𝑡(𝑢,𝑣)、𝑉𝑡(𝑢,𝑣)和𝐸𝑡(𝑢,𝑣)。图4.2(a)给出了一个密度胚𝑂𝑡(𝑢,𝑣)的示例子图(b)0.09的边生成的，蓝色的社区结构是由权为0.08的边然后，我们定义WDE𝑂𝑡(𝑢,𝑣) 𝛷(𝑂(𝑢,𝑣))=|𝐸𝑡(𝑢,𝑣)| 2定义4.3社区准则（WeightedCriterionofCommunity）一个WDE𝑂𝑡(𝑢,𝑣)为一个社区结构当且仅当密度满足𝛷(𝑂𝑡(𝑢,𝑣))𝛿(𝑂𝑡(𝑢,𝑣))

|𝑉𝑡(𝑢,𝑣)|

|𝑉𝑡𝛿(𝑂𝑡(𝑢,𝑣)) (|𝑉𝑡(𝑢,2阈值𝛿(𝑂𝑡(𝑢,𝑣))是一个递增函数[37]，是传统密度阈值（如完全图）的松的版本。根据定义4.3，一些节点和边就可以被为不同的社区，但有些社区会4.4耦合系数（Coupling对两个社区𝐶𝑡和𝐶𝑡，耦合系数𝛤(𝐶𝑡,𝐶𝑡)被定义为 𝑡𝛤(𝐶𝑡,𝐶𝑡) (𝑢,𝑣)∈𝐶𝑖 𝑡 𝑡 𝑡 𝑡𝑢∈𝐶𝑖 𝑣∈𝐶𝑖 ′+𝑚𝑖𝑛(∑𝑢′∈𝐶𝑡∑𝑣′∈𝐶 ′,∑𝑢′′∈𝐶𝑡∑𝑣′′∈𝐶𝑡𝑤′′′ 𝑢 𝑢4.5社区合并准则（CombiningCriterionof对两个社区𝐶𝑡和𝐶𝑡，如果它们的耦合系数𝛤(𝐶𝑡𝐶𝑡)≥𝛼 初始社区结构的构建方法见算法4.1输入：𝐺0=(𝑉0,𝐸0,𝑊0,𝐹0)𝑥0←对𝐺0𝐸′←for每个𝑤𝑡∈ if𝑤𝑡< 𝐸′←𝐸′∖(𝑢,从最大权重边(𝑢,𝑣)∈𝐸′if𝐶𝑜𝑚𝑡(𝑢)∩𝐶𝑜𝑚𝑡(𝑣)=IfΦ(𝑂𝑡(𝑢,𝑣))≥𝛿(𝑂𝑡(𝑢,𝑣))且|𝑉𝑡(𝑢,𝑣)|≥𝒞𝑟𝑎𝑤=𝒞𝑟𝑎𝑤∪{𝑉𝑡(𝑢,𝒞𝑖𝑛𝑖𝑡←for𝐶𝑡,𝐶𝑡∈𝒞𝑟𝑎𝑤且 ifΓ(𝐶𝑡,𝐶𝑡)≥ 𝐶′←合并𝐶𝑡和 𝒞𝑖𝑛𝑖𝑡=(𝒞𝑖𝑛𝑖𝑡∖{𝐶𝑡, 𝐷𝑜𝑛𝑒←加边和移除边操作。算法4.3-4.6给出了动态算法的详细描述及流程。在这4.2可以检测出边的添加和删除。合𝐶𝑜𝑚𝑡(𝑢)。在最后的实验中，如果我们发现社区点的数量为1，我们主要区分两种类型的节点。一种是𝐶𝑜𝑚𝑡(𝑢)=∅且𝑁𝑡(𝑢)=∅的外来新节点，即：它不在当前网络池中。另一种是𝐶𝑜𝑚𝑡(𝑢)≠∅且𝑁𝑡(𝑢)=∅ ←for每个𝑤𝑡∈ 𝑤𝑡<

← ∖(𝑢, 𝑥𝑡←对𝐺𝑡𝐸′←for每个𝑤𝑡∈ if𝑤𝑡< 𝐸′←𝐸′∖(𝑢, 计算 和 △“池外”情况包 外来新节点算法 移除节点算法首先，我们来分析外来新节点4.3。这里有两种可能情况，一种是节点添加时不带边，一种是节点添加时带有边。如果节点𝑢则我们只将点𝑢添加到当前社区结构内即可。如果𝑢属于后一种情况，则情况稍4.3所示：（1）因为𝑢添加时带有边，所以9-13；（2）外来节点17（3）节点集合，𝑢可能会与它们形成新的社区，即步骤18-22。if节点𝑢𝐶𝑆𝑡=else𝑢𝑥𝑡←对𝒞𝑡for每个𝑤𝑡∈ if𝑤𝑡< 𝐸𝑡←𝐸𝑡∖(𝑢,更新集合𝐶𝑡,𝐶𝑡𝐶𝑡←𝑢 for𝑖=1𝑑𝑜𝑡𝑜𝑂𝑡(𝑢,𝑣)←基于𝐶𝑡⋃{𝑢}的生成子图ifΦ(𝑂𝑡(𝑢,𝑣))≥𝛿(𝑂𝑡(𝑢,𝑣))且|𝑉𝑡(𝑢,𝑣)|≥𝐶𝑡←𝐶𝑡∪ 𝑂𝑡(𝑢,𝑣)←基于𝐶𝑡∩𝑁𝑡(𝑢)的诱导子图ifΦ(𝑂𝑡(𝑢,𝑣))≥𝛿(𝑂𝑡(𝑢,𝑣))且|𝑉𝑡(𝑢,𝑣)|≥将𝑂𝑡(𝑢,𝑣)的𝑉𝑡(𝑢,𝑣)定义为一个新的社区for𝑣∈𝐶𝑆𝑡且𝐶𝑜𝑚𝑡(𝑢)∩𝐶𝑜𝑚𝑡(𝑣)𝑂𝑡(𝑢,𝑣)←基于𝑁𝑡(𝑢)∩𝑁𝑡(𝑣)的生成子图ifΦ(𝑂𝑡(𝑢,𝑣))≥𝛿(𝑂𝑡(𝑢𝑣))且|𝑉𝑡(𝑢,𝑣)|≥将𝑂𝑡(𝑢,𝑣)的𝑉𝑡(𝑢,𝑣)作为一个新社区对𝐶𝑡,𝐶𝑡,…,𝐶𝑡和𝐶′ 将𝒞𝑡更新为其次，我们来分析移除节点的算法4.4（1）如果𝑢是个孤立节点或步骤8-12；二是，移除节点后的剩余结构重新形成新的社区，即步骤14-16。4.4if𝑢为孤立节点或𝑑𝑡=𝒞𝑡←𝒞𝑡∖𝑥𝑡←对社区图𝒞𝑡for每个𝑤𝑡∈ if𝑤𝑡< 𝐸𝑡←𝐸𝑡∖(𝑢,for𝒞𝑡(𝑢)或𝒞𝑡(𝑣)内的每个子集𝑂𝑡(𝑢,𝑣)←利用𝒞𝑡(𝑢)的一个子集𝐶𝑡ifΦ(𝑂𝑡(𝑢,𝑣))≥𝛿(𝑂𝑡(𝑢,𝑣))且|𝑉𝑡(𝑢,𝑣)|≥𝐶𝑡←𝑉𝑡(𝑢,对𝐸𝑡(𝑢,𝑣)从最大权重边(𝑢,𝑣)∈𝐸𝑡(𝑢,𝑣)将𝒞𝑡更新为首先，我们来分析新增边的算法4.5。这里有两种可能情况，一是新我们还需判定节点𝑢或𝑣10-15（2）如果新增边来自新添加的外来节点，则我们只需处理边(𝑢,𝑣)即可，即确定是否