下载文档原格式
移动社交网络中基于友好关系下的异或转发机制
任丽丽;张旭
【期刊名称】《南通大学学报（自然科学版）》
【年(卷),期】2017(016)002
【摘要】移动社交网络是延迟容忍网络(delay tolerant networks,DNTs)的典型应用,该网络的特点是缺乏端到端的持续连接.为克服这一障碍,提高数据的传递率,文章分析了移动社交网络中节点与社区、节点与节点之间的联系,把友好节点作为待选节点,通过交集的形式提出了一种基于友好关系下的异或转发策略(FRXO).通过计算机仿真实验与DTNs网络中经典算法比较,发现FRXO算法的传递率高于Label 算法且能明显降低网络中数据包的拷贝数目,有效地减少了资源消耗.
【总页数】5页(P1-5)
【作者】任丽丽;张旭
【作者单位】蚌埠医学院公共基础学院,安徽蚌埠 233030;安庆师范大学数学与计算科学学院,安徽安庆 246133
【正文语种】中文
【中图分类】TP393
【相关文献】
1.移动社交网络中基于影响力的数据转发算法 [J], 刘艳萍;王青山;王琦;付沙沙;任丽丽
2.移动社交网络中基于代理转发机制的轨迹隐私保护方法 [J], 张少波;Md Zakirul
Alam Bhuiyan[;刘琴;王国军
3.移动社交网络中基于拍卖模型的数据转发激励机制 [J], 刘浩;陈志刚;张连明
4.移动社交网络中基于朋友圈的路由机制 [J], 陈琪;王兴伟;王学毅;黄敏
5.机会移动社交网络中基于群组构造的数据分发机制 [J], 李婕; 洪韬; 王兴伟; 黄敏; 郭静
因版权原因，仅展示原文概要，查看原文内容请购买。
基于亲密度和吸引力的二分网络社区发现算法张晓琴; 刘莉楠【期刊名称】《《计算机工程与应用》》【年(卷),期】2019(055)023【总页数】7页(P170-176)【关键词】二分网络; 社区发现; 亲密度; 吸引力; 归一化互信息; 模块度【作者】张晓琴; 刘莉楠【作者单位】山西财经大学统计学院太原 030006; 山西大学数学科学学院太原030006【正文语种】中文【中图分类】TP3931 引言目前对于复杂网络研究逐渐成为网络科学关注的热点，在数学和自然科学领域中，复杂网络被抽象地理解为一系列节点和节点之间的连边，其涉及的领域极其广泛，例如社会人际关系网络[1]、计算机网络[2]、电力网络[3]、交通网络[4]等。
基于复杂网络之间的节点并不是随意连边，而是“乱中有序”的特点，复杂网络的社区发现问题近年来引起了专家与学者们的广泛关注。
社区[5]被定义为具有相似行为特征的个体因某种关系而聚集成的团体，研究网络中的社区对理解整个网络的结构和功能起到至关重要的作用，并且可以帮助分析及预测整个网络各元素间的交互关系。
二分网络是复杂网络中一种重要的表现形式，已成为复杂网络的重要研究对象。
在现实世界中，很多网络都呈现出二分结构，例如科学家-论文合作网络[6-7]、俱乐部会员-活动网络[8]、电影-演员合作网络[9]、疾病-基因网络[10]、P2P中终端计算-交互数据网络[11]等。
目前，对二分网络进行社区划分主要从以下两方面展开：一方面是将二分网络投影[12]成单模网络，利用单模网络中的社区发现算法进行划分，但是投影会导致信息大量缺失或增加多余的额外信息，最终的划分效果不佳；另一方面直接对二分网络进行社区划分，可以保留原始二分网络的信息。
Barber[13]拓展了Newman[14]的单模网络模块度，重新定义了二分模块度，并提出了BRIM（Bipartite，Recursively Induced Modules）算法。
基于社交网络的社区发现算法研究毋建军【摘要】随着社交网络的快速发展及应用，围绕社交网络用户及信息交互自发形成的网络社区已经成为当前社交网络研究领域的重要分支，并取得了许多研究进展及成果，但仍然存在许多挑战及问题。
本文从网络社区研究的网络结构、网络信息、时间三个重要因素考虑，在网络社区的定义、特性的基础上，分类、对比了典型的社区发现模型、算法及社区划分评价方法，并对其存在的问题及未来发展方向进行了分析探讨。
%Along with the rapid development and application of social communication network , online community centering on social communication network users and information interaction becomes an important branch in the field of social communication networkstudy.Although many results have been made , there are many challenges and problems .Considering network structure , network infor-mation and time , this paper analyzes and compares typical community discovery models , algorithms and evaluation methods based on the definitions and features of network community , and discusses the problems and future development direction .【期刊名称】《长春大学学报（自然科学版）》【年(卷),期】2016(026)003【总页数】5页(P35-38,43)【关键词】社交网络;社区算法;动态社区;SNS分析【作者】毋建军【作者单位】北京政法职业学院信息技术系，北京102628【正文语种】中文【中图分类】TP391随着Twitter、Facebook、新浪微博、人人网、微信等社交网络的广泛应用，社交网络大数据集合孕育而生，在大数据基础上，不同领域、学科的研究人员基于社交网络的链接结构、用户交互行为、信息扩散传播等方面，进行了社交网络用户关系挖掘、信息扩散传播的机制分析、网络结构变迁、新型(网络)虚拟关系演化等基础性问题的研究。
社交网络中的信息传播模型社交网络已经成为人们日常生活中不可或缺的一部分。
同时，人们在社交网络中所产生的全部信息，都会被用户自己、被好友、被陌生人看到，并被传播。
这些信息传播背后的模型也是人们十分关心的一个问题。
在这篇文章中，我们将会从几个不同的角度来探讨社交网络中的信息传播模型。
一、社交网络中的信息扩散模型信息扩散模型是研究信息在社交网络中传播的一种数学方法。
该方法利用数学模型来描述社交网络中的用户和信息，以及他们之间的关系，从而研究信息在社交网络中的传播规律。
这种模型的好处在于能够真实地模拟社交网络中的信息传播，并能够预测信息在社交网络中的传播效果。
在信息扩散模型中，常用的模型有: 独立级联模型、线性阈值模型和非线性阈值模型。
独立级联模型指的是，每个用户以一定的概率独立地转发信息。
该模型的优点在于模拟简单，但研究的对象过于简单，无法反映社交网络中的复杂关系。
线性阈值模型则是指在社交网络中，每个用户有一个阈值，只有当信息在社交网络中传播到达该阈值时，该用户才会将信息转发。
该模型比独立级联模型更接近现实，但也存在一些缺点，比如无法反映用户的心理因素和复杂的社交网络中的关系。
非线性阈值模型是一种能够兼顾以上两种缺点的模型，通过对用户与信息传播的关系进行建模，实现了更加精细的信息传播模型。
二、社交网络中的信息传播路径社交网络是追踪信息传播路径的最佳场所之一。
信息传播路径能够揭示许多有用的信息，比如信息的来源、信息接收者、信息传播过程中的噪声和筛选机制。
此外，研究信息传播路径还能帮助人们理解信息在社交网络中的传播规律，进而实现信息的更精准的传播。
在追踪信息传播路径时，有两种方法:（1）基于网络拓扑结构的路径追踪方法: 该方法主要是通过使用网络分析工具挖掘社交网络中的用户之间的关系，找到信息传播的路径。
这种方法基于社交网络的结构设定，因此无法直接看到信息的传递过程，但可以揭示出信息在社交网络中的各种规律。
摘要随着互联网Web2.0概念和技术的快速发展，以Facebook、Twitter、新浪微博为代表的社交网络应运而生，由于社交网络与现实社会之间紧密的联系，使得社交网络为大众的日常社交生活、分享信息和交流意见等社交行为提供了重要的媒体平台，从而极大地改变了大众的生活方式。
近年来处于移动互联网的时代，社交网络用户可以通过手机和浏览器随时随地发布信息、转发信息、评论信息，及时了解动态、沟通情感，因此网络信息一经发布即被社交网络推送到所有关注者，通过关注者的转发传播扩散，最终呈现“核裂变”式的几何级数扩散态势；期间再通过意见领袖对网络信息的发酵、传播、爆炒等行为，使得该信息对现实社会产生巨大的影响，特别是谣言、诈骗等不良信息会直接影响到国家的安全和社会的稳定。
因此对社交网络用户的影响力与转发行为进行研究，不仅对提供服务的社交网络平台的企业具有长远的发展意义，而且对整个国家的稳定发展也有非凡的价值。
基于上述研究背景和意义，本文的主要工作包括：（1） 社交网络用户影响力分析与评估方面：首先从定性的角度分析社交网络用户影响力的相关特性，并且从定量的角度分析传统的社交网络用户影响力度量方法；接着介绍一种基于PageRank算法思想的社交网络用户影响力算法；最后根据真实的社交网络数据，通过实验分析验证本文提出的社交网络用户影响力算法的有效性；（2） 社交网络用户转发行为分析与预测方面：首先阐述说明影响社交网络用户转发行为的主要因素；其次介绍衡量社交网络用户之间亲密度的算法和分析社交网络用户对网络信息的个性化兴趣并提取相关特征；然后提出一种基于神经网络模型和梯度下降优化算法的社交网络转发行为预测模型；最后，根据社交网络用户经常遇到的实际案例对该预测模型进行验证和评估；（3） 社交网络用户影响力与转发行为分析系统方面：结合上述研究成果，本文设计并实现社交网络用户影响力与转发行为分析系统，对系统的总体架构设计、数据库设计和核心模块实现进行了详细介绍。
2018年7月计算机工程与设计July 2018第 39 卷第 7 期COMPUTERENGINEERINGANDDESIGN Vol. 39 No. 7移动社会网络中基于社会感知的数据转发算法邓敏，徐方+，熊曾刚，叶从欢，夏洪星(湖北工程学院计算机与信息科学学院，湖北孝感432000)摘要：在移动社会网络中利用节点携带者的社会属性设计高效的数据转发算法是当前研究难点问题，针对这一难题提出一种基于社会感知的数据转发算法。
该算法包含一种数据转发度量，由两个效用函数组成，分别是利用节点的社会属性计算的社会相似性效用、利用节点间的社交联系计算的节点介数中心度效用，转发度量结合这两个效用函数获取网络节点的社交强度和重要性；利用该转发度量选择最优中继节点，设计高效的数据转发算法。
采用真实数据集进行的仿真结果表明，该算法相比于其它3种经典算法具有明显的优越性。
关键词：移动社会网络；转发算法；社会感知；社会相似性；中心度中图法分类号！TN915 文献标识号：A文章编号％1000-7024 (2018) 07-1835-06d o i：10. 16208/.. issnl000-7024. 2018. 07. 007Social-aware data forwarding algorithm in mobile social networksDENG M in, XU Fang+，XIONG Zeng-gang, YE Cong-huan, XIA Hong-xing (School of Computer and Information Science，Hubri Engineering University，Xiaogan4320A b s tra c t：tt is difficult to use social context of node^s carriers for designing efficient data forwar networks.To address t his problem，a social-aware data forwarding algorithm was proposed.A forwarding metric was introduced，in which node^s social properties were used to calculate the social similar and the social connection of network nodes was used to calculate the betweenness metric was combined with two utility functions to derive the social strength among users and their importance，and it was used to determine the best relay node.An efficient data forwarding algorithm based on above knowledge was presen tensive simulations on real traces s how that the proposed algorithm is more efficient than other state-〇--art algorithms.Key w ords：mobile social networks；forwarding algorithm；social awareness；social similari引言移动社会网络[1](mobile social networks，MSNs)为 用户提供方便灵活的网络服务，能广泛应用于智慧城市、车载网络、应急救援和健康医疗等领域[2]。
机会网络中基于节点社会性的数据转发策略彭舰;李梦诗;刘唐;李林峰;黎红友【期刊名称】《四川大学学报（工程科学版）》【年(卷),期】2013(045)005【摘要】合理地选择代理节点是实现机会信息高效的转发和交付的关键问题.为了避免机会网络中,由于节点的移动性、交替活跃及网络拓扑动态变化等因素造成的传输限制,从社会网络与机会网络相结合的角度出发,提出了一种基于节点社会性的机会网络中的转发策略SNOP(data forwarding algorithm based on the sociality of node in opportunity network).SNOP利用网络中的社团结构、社团间相似性及节点的社团活跃,有针对性地选择移动代理节点(agents),以离线的方式计算节点的社会性,在线完成转发,以此实现信息的高效和可靠交付.在真实数据集上的实验结果表明,与现有的转发算法相比,SNOP能够有效地提高信息交付的效率,降低端到端的传输延迟及网络开销.【总页数】7页(P57-63)【作者】彭舰;李梦诗;刘唐;李林峰;黎红友【作者单位】四川大学计算机学院,四川成都610065;四川大学计算机学院,四川成都610065;四川大学计算机学院,四川成都610065;四川师范大学基础教学学院,成都610068;四川大学计算机学院,四川成都610065;四川大学计算机学院,四川成都610065【正文语种】中文【中图分类】TP393【相关文献】1.机会网络中基于节点暂态社区的消息转发策略 [J], 张健2.稀疏机会网络中基于固定中继节点与消息相关性的缓存管理策略 [J], 马学彬;李爱丽;张晓娟;贾磊磊;肖静3.延迟容忍移动传感器网络中基于节点优先级的数据转发策略 [J], 刘唐;彭舰;王建忠;刘浏4.机会网络中基于节点相遇间隔的缓存管理策略 [J], 张峰5.机会网络中基于陌生节点的竞争转发策略 [J], 刘慧;钱育蓉;张振宇;杨文忠因版权原因，仅展示原文概要，查看原文内容请购买。
移动群智感知中基于节点竞争的数据转发算法
王巧莉;张振宇;吴晓红
【期刊名称】《现代计算机：上半月版》
【年(卷),期】2018(000)009
【摘要】针对移动群智感知网络中的数据转发问题,提出一种基于节点竞争的转发算法。
该算法为参与数据转发的节点提供一定的奖励,调动节点参与竞争转发的积极性,达到促进数据转发的目的。
其中,节点的竞争能力体现在节点的剩余能量、节点活跃度、节点关系强度、历史转发次数上,充分利用竞争能力较强的节点加快数据的转发过程。
仿真结果表明,与Epidemic、Prophet及SW等算法相比,在保证较低网络开销的基础上,能够充分利用节点的转发能力,从而提高数据交付率和减少延迟。
【总页数】6页(P3-7)
【作者】王巧莉;张振宇;吴晓红
【作者单位】新疆大学信息科学与工程学院乌鲁木齐830046;新疆大学信息科学与工程学院乌鲁木齐830046;新疆大学软件学院乌鲁木齐830008;新疆大学软件学院乌鲁木齐830008
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.移动群智感知网络中基于QoS感知与协作竞争的机会传输机制 [J], 袁桂霞;周先春
2.移动群智感知中基于节点竞争的数据转发算法 [J], 王巧莉;张振宇;吴晓红
3.移动群智感知中基于雾节点协作的感知用户身份隐私保护 [J], 刘慧; 毕仁万; 熊金波; 赵明烽; 金彪; 林劼
4.移动群智感知系统中基于离散布谷鸟搜索算法的任务分配 [J], 杨正清; 周朝荣; 袁姝
5.移动群智感知中基于雾节点协作的感知用户身份隐私保护 [J], 刘慧; 毕仁万; 熊金波; 赵明烽; 金彪; 林劼
因版权原因，仅展示原文概要，查看原文内容请购买。
机会移动社交网络中基于群组构造的数据分发机制李婕; 洪韬; 王兴伟; 黄敏; 郭静【期刊名称】《《计算机研究与发展》》【年(卷),期】2019(056)011【总页数】12页(P2494-2505)【关键词】机会移动社交网络; 关系度量; 合作博弈; 数据分发机制; 群组构造【作者】李婕; 洪韬; 王兴伟; 黄敏; 郭静【作者单位】东北大学计算机科学与工程学院沈阳110819; 东北大学信息科学与工程学院沈阳110819【正文语种】中文【中图分类】TP393随着移动互联网的迅速发展，人们通过移动智能终端获取大量各种形式的网络资源，而目前移动设备接入互联网的形式主要是通过基站，这样就大大增加了基站的流量负载，同时也增加了通信运营商对基站设备资金和技术的投入.在基础设施部署困难或者不完善的场景中，移动设备之间的通信就变得极为困难.针对以上问题，一些特殊的网络已被提出，如无线传感器网络、移动自组织网络[1]等.机会移动社交网络(opportunistic mobile social networks, OMSNs)[2]作为结合网络节点移动属性和社会属性的特殊移动自组织网络，能够很好地契合特殊场景下的网络环境，卸载部分基站的流量负载，近年来机会移动社交网络成为研究学者们关注的热点.机会移动社交网络利用网络节点的移动性带来的接触机会实现近距离的无线数据传输，其具有非持续性连接、时延长、能耗大等网络传输特性，使机会移动社交网络的应用得到一定程度的限制，目前机会移动社交网络的研究面临的挑战性问题有：如何寻找到一条中断容忍、低时延、低能耗的数据传输路径；如何充分利用节点的移动性和社会性特征提高网络性能；如何避免节点自私性而增强网络整体性能.针对这些挑战性问题，本文提出了基于群组构造的数据分发机制(data dissemination mechanism based on group structure, DDMGS)，该机制主要有4方面贡献：1) 充分挖掘机会移动社交网络中节点的移动特性和社会关系特性，确定节点重要性、兴趣相似度和通信关系紧密度，构建节点关系度量模型；2) 由于基于位置关系的拓扑结构具有周期稳定性，基于兴趣关系的拓扑结构具有长期稳定性，而基于通信关系的拓扑结构具有动态性，因此依据这3种行为属性关系构成的网络拓扑特征设计了3种群组构造算法；3) 基于不同的行为属性关系构成的群组结构设计了数据分发机制，引入节点缓存区管理机制提高传输性能，引入合作博弈理论来规避节点的自私行为，降低传输能耗，促进节点协作，提高整体网络性能；4) 验证并评估了DDMGS的性能，与机会移动社交网络中的主要数据传输算法在消息传输成功率、平均传输时延、平均跳数、数据分发开销比率等性能评价指标上进行了对比和分析，验证了DDMGS的有效性.1 相关工作目前，数据分发机制按照消息传输方式的不同大致分为四大类：基于洪泛的数据分发机制[3-6]、基于上下文感知的数据分发机制[7-9]、基于编码的数据分发机制[10]、基于群组的数据分发机制[11-14].由于机会移动社交网络的节点具有社会属性并且会自然地形成各种群组，所以充分利用节点的社会特性便成了机会移动社交网络的重要研究内容之一.文献[11-12]分别提出了经典的数据分发机制SimBet和Bubble Rap，这2种算法均考虑到节点的社会性.随后很多基于群组的数据分发机制相继被提出.文献[13]考虑到机会移动社交网络拓扑的动态性，提出在机会移动社交网络中存在一个嵌套的核心外围层次结构(nested core periphery hierarchy, NCPH)，即加权度大的一些节点组成网络核心，同时网络周边由加权度小且不活跃的一些节点组成，当外围节点被迭代移除时，NCPH仍被保留，并利用网络的这种特征提出一种上下路由协议，即路由分为上传阶段和下载阶段，该路由协议在数据传送延迟和比率方面实现了优越的性能，并且具有较低的转发成本.文献[14]中作者提出一种基于社区和社交性的组播数据分发机制，引入动态社交特征的概念来捕获节点的动态连接行为，考虑了更多的节点之间的社会关系，采用社区结构来为每个节点选择最佳的中继节点从而提高多播机制的性能.该文中提出了2种基于社区和社交性的多播算法：第1种是基于社区及社会特征的组播算法Multi-CSDO(community and social feature-based multicast involving destination nodes only)，它只涉及到社区发现中的目标节点；第2种被称为Multi-CSDR(community and social feature-based multicast involving destination nodes and relay candidates)，它涉及社区发现中的目标节点和候选中继节点.文献[15]关注于群组的移动性和群组外形，提出一种算法可以根据若干移动设备的移动性以及它们所组成的外形高概率地判断这些移动设备是否是属于一个群组.文献[16]是有关D2D通信的研究，它通过判断某一设备进组是否会提升本组吞吐量来进行设备筛选，完成群组构造，提升了D2D通信的吞吐量等性能指标.文献[17] 考虑OMSNs 中节点间存在周期性相遇的特点设计了基于节点周期性相遇的数据分发机制，并通过实验对比验证了相对于传统DTN路由机制在数据分发成功率上的提升.由此可以看出：在机会移动社交网络中考虑节点的社会属性和群组结构能够有效地提高数据分发效率.但目前的研究存在不足有：没有考虑节点的多方面社会属性，例如没有充分考虑节点的移动轨迹对数据传输的影响；并且未考虑由节点不同的社会关系构成的网络拓扑是有区别的，所以导致群组结构单一，群组划分与实际情况差距较大；未考虑由于节点自身的资源受限而出现的自私行为.因此，本文提出的基于群组构造的数据分发机制，根据节点的移动性特征、节点重要性、节点间兴趣相似度和节点间通信关系紧密度等多维社会属性设计了不同的群组构造机制，并引入合作博弈理论，加强节点之间的协作，通过与传统路由机制的对比实验论证了本文所提出的数据分发机制的可行性和有效性.2 网络模型由于机会移动社交网络的拓扑结构是动态变化的，所以每个时刻网络的拓扑都是不同的，为了对节点移动模型进行直观的描述，本文将机会移动社交网络某时刻的“快照”作为网络模型.将机会移动社交网络中的用户抽象为节点，其在网络中可以自由移动；节点可以选择和其通信范围内的任意节点进行通信，或者拒绝通信；由于节点的能量存储和缓存空间都是有限的，所以网络在某一时刻会存在拒绝转发数据的节点；节点之间采用Bluetooth，WiFi直连通信等近距离通信方式进行数据传输，节点只有处于相互通信范围内时才能进行通信，本文假设各节点通信半径相同.用户间的联系抽象为边，即将网络建模为图G(V,E)，其中V={v1,v2,…,vn}表示用户的标识集合，E={e1,e2,…,el}表示用户间的关系.如图1所示，如果2节点间存在兴趣或者通信等关系，则2节点间存在1条无向边，边上的权重w(i,j)代表节点i和j之间某种关系的紧密程度.Fig. 1 Topology of the opportunistic mobile social network图1 机会移动社交网络拓扑3 算法设计本文根据户节点的位置关系、兴趣和通信关系等移动特征和社会特征对节点重要性、兴趣相似度和通信关系紧密度进行定义和建立度量模型，基于3种节点关系度量对节点进行群组构造.在构造群组基础上，利用节点的群组属性，对节点之间的合作博弈建模，引入缓存管理机制，设计基于群组结构的数据分发机制.3.1 基于位置关系的群组构造方法1) 移动模型在OMSNs中，节点的移动模型影响节点在数据传输过程中的时延和成功率等性能.目前为止，经典的随机移动模型，由于其节点的速度和移动方向都是随机的，不太适用于机会移动社交网络.文献[18]提出了一种基于校园社区的移动模型(campus based mobility model, CBMM)，该模型分析了用户的日常行为特征，重点关注节点之间的间隔联系时间和联系时长的分布，很好地呈现了节点的社会特征.本文将该移动模型与基于地图最短路径的移动模型(shortest-path map based movement, SPMBM)结合，给出基于地图的工作移动模型(map based working day movement, MBWDM).2) 节点重要性度量人们的移动不是随机的，而是有规律的，并且活动范围相对固定，例如上班族工作日规律地从家到公司，大学生在校园内按课程表作息活动，公交车每天总是在同一条路线上行驶，出租车司机总喜欢去客流量多的地方载客等.在机会移动社交网络中，我们将节点的相遇定义为2个节点移动至对方的通信范围内.只有相遇的节点才能进行通信，所以节点在机会网络中所处的位置决定了其承担通信任务的重要性.当用户节点处于聚集节点较多的位置时，能检测到较多节点发出的消息，那么该用户节点可以作为其他节点的中继节点进行数据的转发；反之，当其处于节点稀疏的位置时，能检测到的用户信息较少，能够承担通信任务的重要性减弱.因此，我们根据节点接收到的信号量来定义节点的重要性.定义1. 节点的重要性.节点在单位时间内接收到的检测信号量，表示为(1)其中，signal(τ,i)是节点i在时刻τ检测到的信号数量.3) 基于位置因素的群组构造方法在本群组构造发方法中，基于节点的移动轨迹，确定节点之间的位置关系，在同一时间片内处于相同或相近的地理位置时，节点相遇的机会大，从而更容易形成以地理位置为特征的群组结构，由于节点的移动具有周期性规律，因此基于位置属性的群组具有周期稳定性，其构造方法分为2个阶段：引导阶段和演化阶段.算法1. 基于节点位置关系的群组构造算法.1) 引导阶段输入：n个节点;输出：m个群组.① 选择节点重要性较大的前m个节点作为初始节点，每个节点有一个唯一的群组ID号，假设群组的ID号为1～m；② 在所有节点的移动过程中，将没有群组归属节点加入到与其首次相遇的节点所属的群组中，直到每个节点都有其唯一的群组ID号.2) 演化阶段输入：n个节点、m个群组;输出：每个节点所属的群组ID号.① 在节点移动过程中，每个节点对自己与其他节点的相遇次数进行计数，将此信息保存在节点的隶属参数APS中，节点i的APS表示为APS=(aps1i,aps2i,…,apsmi)，其中，apsji表示节点i和群组Cj中节点的相遇次数；② 通过更新APS调整节点的群组归属，比较节点与每个群组的相遇情况，将节点加入一个或多个群组中，例如：若则将节点i加入到群组Xij(t)中，其中θ是一个阈值；③ 进行群组的合并，如果其中|C1|和|C2|分别表示群组C1和C2中的节点数，δ是一个阈值，则群组C1与C2合并.3.2 基于兴趣的群组构造方法兴趣是节点具有的重要社会属性之一，也是相对稳定的行为属性之一，因此基于用户兴趣相似度的网络拓扑结构具有相对长期稳定性.本文设计了一种适用于静态拓扑结构的基于兴趣的群组构造算法，该算法将具有相同或相似的兴趣爱好的用户进行聚类，得到一种按兴趣划分的群组结构，当用户请求感兴趣的内容时，请求消息将在其所属群组内进行转发与传播，使请求成功率得到极大的提高.1) 兴趣相似度度量本文用兴趣相似度来度量用户之间在兴趣爱好方面的相似程度.移动节点的兴趣资源都会以文件的形式存储在移动设备，我们采用文档聚类技术对存储在节点中的数据进行聚类来模仿节点的兴趣.文档fi的文件向量即节点的兴趣矩阵表示为其中，tk表示关键字，关键字可以是音乐、电影、体育、经济等等;witk表示关键字相应的权重，witk的计算过程为witk=1+ln ntk，(2)其中，ntk表示关键字tk出现的次数.为了将witk的范围控制在[0,1]之间，其标准化为(3)定义2. 兴趣相似度.节点i和节点j兴趣向量中相同的关键字以及对应的权重为intsim(i,j)=(4)其中，Y(tk,tl)=1，仅当tk=tl时，否则为0，其中L为兴趣文档长度常量.2) 基于兴趣的群组构造方法团(clique)[19]的概念被引入到该群则构造算法中.定义3. 团. 团体的一个子集形成一个团，该团由3个或更多个成员组成，每个成员都与团的其他所有成员具有对称关系.基于兴趣的群组构建算法分为3个步骤：团的构造、互相重合团的融合以及孤立节点的归属.1) 团的构造.对于网络拓扑G，遍历所有的节点，对每一个节点V找出它对应的所有相连节点的集合Vn.判断该节点集合是否可以满足完全图的条件，如果可以，则将该节点集合连同节点V就可看作本网络拓扑中的一个团.2) 团的融合.如果团K和团L拥有共同节点，则首先判断团K和团L的大小.如果团L较小，则判断去除团K和团L的共同节点，剩余节点是否仍然成团，如果仍然成团则将团L拆分为更小的团,如果不成团，则将团L直接加入到团K中;如果团K和团L节点数目相同，则根据先前提出的兴趣相似度判断共同节点应属于哪个团，而剩下节点的归属问题和团L较小时的情况相同.3) 孤立节点的归属.在网络拓扑G中，经过团的构造和融合，如果还存在孤立的节点，则根据孤立节点与它相连的团的兴趣相似度的大小，把这些孤立节点归属到不同的团中.算法2. 基于兴趣的群组构造算法.输入：具有n个节点、m条边的兴趣关系网络G(V,E,w)，边权值的阈值γ；输出：群组集合GS.① 初始化群组集合GS←∅；② FOR V中每一个顶点v do③ 找到v的所有相邻顶点，记作集合Vn；*顶点v形成团{v}*④ IF Vn=∅⑤ CONTINUE；⑥ END IF⑦⑧ IF {{v}+Vn}⊄GS⑨ GS←{{v}+Vn}；⑩ CONTINUE；END IFEND IFEND FORFOR GS中每个团K doGS中找出团K的所有弱相邻顶点，记作集合在E中找出团K与其弱相邻顶点连接的边，记作E′；IF w>γEND IF从GS中找出团K的所有强相邻顶点，记作集合END FOR3.3 基于通信关系的群组构造方法在移动用户的通信行为中，通话时间和通话次数是最能直接表达通信关系紧密程度的度量指标.但是，通信关系紧密度又是一个随社会关系变化的量，因为人们在社会中的身份或地位发生了变化，会导致与其他人的通信关系发生变化，这种变化或增强或减弱人们之间的通信关系，所以本文考虑随时间变化的通信关系的衰减度.在计算通信关系紧密度时需要对时间进行周期划分，并且通过分析节点在网络中的重要程度，以及节点之间的周期通信关系和衰减函数计算得到通信关系紧密度. 1) 通信关系紧密度度量定义4. 社交中心性(social centrality).社交中心性代表了网络中节点的相对重要程度，我们采用Freeman[20]的度中心性来计算社交中心性.节点A的社交中心性可以定义为(5)其中，dAB(τ)=1当且仅当节点A和节点B在时刻τ有通信行为，N是网络中节点的个数.定义5. 衰减函数(decay).衰减函数取决于节点在社交网络中的重要程度以及与其他节点的社交时间，当2个节点才开始建立通信关系且2个节点的社交性强时，其关系衰减度较小.衰减函数的计算为(6)其中，τ是节点A和节点B有通信行为的时刻，T是周期.可以看出，当通信行为发生时刻越近，且社交中心性越大时，衰减函数的值越大.定义6. 通信关系(communication relationship).周期通信关系代表一个周期内节点之间通话时间和通话次数的关系，其计算公式为(7)其中，v(A,B,T)，vt(A,B,T)表示在周期T内用户A和B的通话时间、通话次数，v(A,T)，vt(A,T)和v(B,T)，vt(B,T)分别表示在周期T内用户A和用户B的总通话时间、总通话次数.定义7. 通信关系紧密度(communication tight-ness).综合衰减函数和周期通信关系得到通信关系紧密度，表示为CR(A,B,T)×DAB(T-τ)，(8)其中，XAB(τ)=1当且仅当节点A和节点B在时刻τ有通信行为，或τ=T时；否则XAB(τ)=0.CR(A,B,T)是上个周期的周期通信关系，这里我们使用上个周期的周期通信关系来计算本周期的通信关系紧密度.本文采用增量式的动态群组构造算法，即计算本周期的群组结构时是基于上个周期的群组结构进行调整，避免重复计算.2) 基于通信关系的群组构造算法① 群组核.群组内部存在的稳定群组核心节点或群组核心节点的集合称为群组核，群组核之间没有重叠部分.② 单独节点.度为0的节点集合.③ 边缘节点.群组核以及单独节点外的节点或节点集合称为边缘节点.边缘节点之间可能存在一条或多条边，但是它们不能形成群组核或加入到已存在的其他群组核中.④ 移动群组.移动网络中一组内部紧密联系的用户群称为移动群组.移动群组由群组核和满足条件的边缘节点组成.⑤ 节点与群组的相似度.节点与群组的相似度是判断节点是否可以加入该群组的条件，本文对余弦相似度进行改进，可以计算有权网络中节点与群组的相似度，即：(9)其中，N(u)代表节点u的邻接节点集合，N(K)代表群组K的节点集合，N(u)∩N(K)是节点u的邻接节点集合与群组K的节点集合的交集.⑥ G(V,E,w).G表示有权无向图，V是G中节点的集合，E是G中边的集合，w(u,v)表示E中边(u,v)的权重.Gt(Vt,Et,wt)：时间片t的网络图快照.C1,C2,…,Ct,…：随时间变化的群组结构.时间片t时的群组划分结果，即其中m是群组数量.⑦ ΔG. ΔG表示图增量，有4种情况:节点加入、节点移除、边加入、边移除.算法3. 基于通信关系的群组构造算法.1) 初始群组构造输入：通信关系网络图G(V,E,w)、边介数阈值α、节点度阈值d；输出：初始时刻群组构造结果① 对网络进行预处理，设定度为d的阈值，选出度高于d的节点；② 采用设定边介数阈值的GN算法，将从②中得到的少量节点中挖掘出群组核；③ 遍历网络中除群组核外的其他节点，计算这些节点与群组核的相似度，将该节点归入到与之相似度最大的群组核中，对没有与群组核直接相连的节点，则计算与其相连的移动群组的相似度，将其加入到与之相似度最大的群组中；④ 进一步对③结果进行优化，遍历所有其他节点，计算节点与群组相似度，如果发现节点所归属的群组不是与其相似度最大的群组，则重新将其划分到正确的群组中，得到最终的群组结构.2) 每个时间片群组的动态变化执行算法输入：网络拓扑图快照Gt(Vt,Et,wt)、图增量ΔG.输出：时间片t+1的网络群组结构Ct+1.① 当新节点加入时，有2种情况：如果是单独节点，则将该节点单独划分为一个群组；如果是边缘节点，则根据该边缘节点与其相连移动群组的相似度，并将其加入到相似度值为最大的一个移动群组中.② 当旧节点移除时，有2种情况：如果移除的节点是单独节点，则保持原有的群组结构；如果移除的节点是边缘节点，那么该节点的移除将影响其相邻节点的归属群组，这是个连锁反应，所以需要迭代计算其所影响到的节点，直到所有被影响的节点处于稳定的状态.③ 当新的边加入时，有2种情况：如果新加入的边的2个顶点位于同一个群组，则保持原群组结构；如果新加入的边的2个顶点位于不同的群组，则重新计算这2个节点与其相连群组的相似度，将其划分到相似度最大的群组.④ 当旧的边移除时，有2种情况：如果旧的边的2个顶点位于不同的群组，则保持原群组结构；如果旧的边的2个顶点位于同一个群组，则重新计算这2个节点与其相连群组的相似度，将其划分到相似度最大的群组.3) 算法复杂性分析本文设计3种群组构造算法：基于位置关系的群组构造算法采用动态的分布式群组构造算法、基于兴趣的群组构造算法采用静态社区划分方法、基于通信关系的群组构造算法采用增量式动态群组构造算法，前两种构造的群组相比基于通信关系的群组构造具有相对高的稳定性，算法复杂度低于增量式动态群组构造算法.增量式动态群组构造算法认为网络拓扑的变化是平滑的，当计算当前网络的群组结构时，在上个时间片的群组结构上进行调整，所以计算速度加快，时间复杂度降低.该算法在同一个群组内增加边和删除不同群组之间的边时，算法复杂度为O(1)；在不同群组之间增加边和在同一个群组内删除边时，算法较复杂，最坏的情况下时间复杂度是O(n)，但群组的调整次数要小于节点个数n，所以一般情况下的时间复杂度小于O(n).3.4 缓存区管理机制在机会移动社交网络中，消息传输采用的是“存储-携带-转发”的方式，而移动终端设备的缓存空间是有限的，为了减少网路开销和缓存压力，保证消息的交付率，需要对节点的缓存空间进行管理.节点缓存空间的管理主要依据消息的优先级和生存期(time to live， TTL).根据节点之间群组重合度，为每个节点分配转发消息的优先级，因为群组结构是动态变化的，所以在时段t群组重合度为(10)其中，分别代表节点i所属的移动轨迹组、兴趣组、通信组.当且仅当否则群组重合度高的节点转发消息的意愿强，所以消息的优先级就高.源节点在产生消息时，在该消息中设置时间值TTL为当前的系统时间，每经一跳节点，便计算当前系统时间和初始时间的差值，当差值大于给定阈值(在仿真中给出1 433 min)时，删除该消息.每个节点用一个队列存储消息列表，该列表记录消息的基本信息，如消息ID号、消息优先级和TTL.当节点u接收消息时，对优先级是0的消息不存储，对优先级不为0的消息，如果其缓存区足够则直接存储，如果其缓存区已满需要遍历消息列表删除优先级低的消息，如果消息的优先级相同则删除TTL较小的消息.节点每隔一段时间需要删除TTL为0的消息，完成缓冲区的清理工作.3.5 基于群组构造的数据分发机制本文设计的基于群组构造的数据分发机制(data distribution mechanism based on group structure， DDMGS)采用单副本模型，在选择下一跳节点时，不仅考虑节点所属的群组之间的关系，还引入博弈论，促使节点协作转发.3.5.1 基于合作博弈的问题建模1) 博弈模型的定义为① 局中人N. N={1,2,…，n},表示机会移动社交网络中的所有节点.② 策略集合S. S={D,F}表示每个节点可以采取的行动集合，Si表示节点i的决策，Si=D表示拒绝，Si=F表示转发.③ P. P={pij}表示节点i的支付函数.2) 支付函数pij包含3部分：群组重合度、合作能力、声誉度.① 群组重合度群组重合度θij(t)是节点之间的所属群组的相似关系，重合度越高节点越相似，群组重合度θij(t)利用式(10)计算.② 合作能力合作能力φij(t)是关于电量的函数，定义为(11)其中，Eij(t)表示节点i和节点j之间在时段t转发数据包所要花费的电量，Erem表示节点i或节点j的剩余电量.可以看出，电量随着时间的流逝越来越低，节点的合作能力也越来越低.③ 声誉度声誉度φij(t)是用节点在某时间间隔t内的转发消息数、产生消息数和接收消息数来度量，定义为(12)其中，Fij(t)表示节点i和节点j在时段t转发的消息数，Gij(t)表示节点i和节点j在时段t产生的消息数，Rij(t)表示节点i和节点j在时段t接受的消息数.节点i在时段t支付的表达式为pij(t)=αθij(t)+βφij(t)+γφij(t)，。
