下载文档原格式
移动社交网络中基于友好关系下的异或转发机制
任丽丽;张旭
【期刊名称】《南通大学学报（自然科学版）》
【年(卷),期】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)，。
(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号 (43)申请公布日 (21)申请号 201910224583.9(22)申请日 2019.03.23(71)申请人 西安电子科技大学地址 710071 陕西省西安市太白南路2号(72)发明人 吴建设 孙文静 丁琪琪 管铭 丁振林 周超杰 (74)专利代理机构 陕西电子工业专利中心61205代理人 田文英 王品华(51)Int.Cl.G06Q 50/00(2012.01)(54)发明名称基于节点活跃度的社交网络信息传播方法(57)摘要本发明公开了一种基于节点活跃度的社交网络信息传播方法，主要解决现有技术中存在的以下问题：(1)只根据节点的影响力作为种子节点的选择标准；(2)节点影响力之间存在严重重叠。
本发明的实现步骤为：(1)建立RIC模型；(2)确定每个节点的活跃度；(3)建立种子集合；(4)确定当前种子集合的激活节点集合；(5)更新种子集合；(6)重复步骤(4)和步骤(5)，直到种子集合大小等于种子预算值；(7)通过种子节点进行信息传播。
本发明综合考虑种子节点的两个选择标准，逐步进行种子集合的选择，使单个种子节点具有较大的影响力增量，使整个种子集合获得更大的信息影响范围。
权利要求书2页 说明书6页 附图3页CN 109978707 A 2019.07.05C N 109978707A权 利 要 求 书1/2页CN 109978707 A1.一种基于节点活跃度的社交网络信息传播方法，其特征在于，构建现实独立级联模型RIC模型，建立种子集合，更新种子集合，该方法的具体步骤如下：(1)构建现实独立级联模型RIC模型；(1a)读入数据集规模至少为100个节点的社交网络数据集；(1b)将社交网络数据集抽象为一个有向图；(1c)生成与有向图对应的邻接矩阵；(2)确定每个节点的活跃度；将社交网络信息传播开始时的每个节点从该节点出发指向其相邻节点的连边的总数，作为该节点的活跃度；(3)建立种子集合；建立一个空集用于存储种子节点，将每个节点的初始活跃度分别与其接受概率做乘积，从所有乘积值中选择最大乘积值对应的节点作为首个种子节点，加入到种子集合中；(4)使用蒙特卡洛方法，确定当前种子集合的激活节点集合；(5)更新种子集合；(5a)按照下式，计算每个非种子节点的活跃度：D(v)＝{u|u∈N(v)-N(v)∩S}其中，D(v)表示非种子集合中第v个非种子节点的活跃度，{·}表示集合符号，u表示集合中节点的序号，|表示条件符号，∈表示属于符号，N(v)表示第v个非种子节点的邻居节点集合，∩表示并集操作，S表示当前激活节点集合；(5b)将每个非种子节点的活跃度分别与其本身的接受概率做乘积，从所有乘积值中选择最大乘积值对应的节点作为种子节点，加入到种子集合中；(6)使用蒙特卡洛方法，确定当前种子集合的激活节点集合；(7)判断当前种子集合中的节点总数是否小于种子预算值，若是，则执行步骤(5)，否则，执行步骤(8)；(8)得到社交网络中信息传播所要求的种子集合；(9)种子集合中的种子节点通过与其相邻的节点进行信息传播。
人工智能开发中的亲密度传播算法解析随着人工智能技术的不断发展，亲密度传播算法成为了人们研究的热点之一。
亲密度传播算法是一种基于社交网络分析的算法，它可以分析人与人之间的亲密关系，并预测未来的关系发展趋势。
本文将通过解析亲密度传播算法的原理和应用，深入探讨其在人工智能开发中的重要性。
亲密度传播算法的原理基于社交网络的理论。
社交网络可以看作是一个由个体和个体之间的关系构成的网络，而亲密度则是描述个体之间关系亲近程度的指标。
亲密度传播算法的核心思想是，通过分析社交网络中存在的关系和交互，来推断和预测个体之间未来的亲密关系。
在亲密度传播算法中，为了衡量个体之间的关系强度，通常会使用一些评估指标，如互动次数、共同兴趣爱好等。
通过对这些指标的分析，可以构建一个个体关系矩阵，用于表示个体之间的关系强度。
在矩阵中，每个元素代表了两个个体之间的亲密度值，值越高表示关系越亲密。
基于此，亲密度传播算法可以通过以下步骤来计算个体之间的亲密度传播值。
首先，需要选择一些种子节点作为初始传播节点。
这些种子节点通常是已知关系的节点，可以用于传播关系信息。
然后，算法会根据种子节点的关系信息，向周围节点传播关系值。
传播的过程通常会使用一些预定的传播规则，如关系值的衰减规则、关系值的传递规则等。
通过多次传播迭代，就可以计算出每个节点的亲密度传播值。
亲密度传播算法在人工智能开发中有着广泛的应用。
首先，亲密度传播算法可以用于社交网络分析。
社交网络中存在着大量的亲密关系，而亲密度传播算法可以帮助我们更好地理解和预测这些关系。
通过对社交网络中的关系进行分析，可以揭示出一些隐藏的结构和规律，从而为社交网络的应用提供更好的支持。
其次，亲密度传播算法还可以用于推荐系统的开发。
在很多推荐系统中，我们需要根据用户的历史数据来为其推荐适合的产品或内容。
而亲密度传播算法可以通过分析用户与用户之间的亲密关系，来衡量用户对某些产品或内容的兴趣程度。
通过将亲密度传播算法与推荐系统相结合，可以提高推荐算法的准确性和个性化程度，从而更好地满足用户的需求。
移动社交网络中基于用户兴趣的转移推荐算法研究随着移动互联网的普及，人们越来越依赖于手机来满足社交需求，移动社交网络应运而生。
在这样的社交网络中，用户可以创建自己的个人资料，并在上面发布内容，与朋友分享互动。
与传统社交网络相比，移动社交网络更加便于随时随地与他人建立联系。
然而，在移动社交网络中用户面临一个共同的问题：如何找到与自己兴趣相似的人和内容？这时，推荐系统就能派上用场，它可以根据用户的兴趣和偏好向其推荐相关的人和内容。
因此，基于用户兴趣的转移推荐算法成为了移动社交网络中一个备受关注的研究课题。
本文将介绍这一算法的研究现状及其应用前景。
一、基于用户兴趣的转移推荐算法概述基于用户兴趣的转移推荐算法，顾名思义，指的是利用用户在不同社交网络或不同时间的行为数据，推测其对某个新社交网络或新内容的喜好程度。
这种算法可以帮助用户在新社交网络或新内容平台上快速找到感兴趣的人或内容。
在这种算法中，首先需要收集用户在多个社交网络或不同时期的行为数据，如阅读历史、好友列表、关注榜单、点赞、评论等等。
接着，通过对这些数据进行挖掘和分析，可以推测用户的兴趣和偏好。
最后，结合新社交网络或新内容平台的信息，将用户的兴趣转移过来，向用户推荐感兴趣的人或内容。
二、基于用户兴趣的转移推荐算法技术方案当前，基于用户兴趣的转移推荐算法主要包括三种技术方案：基于社交网络的转移推荐算法、基于用户话题的转移推荐算法和基于迁移学习的转移推荐算法。
1. 基于社交网络的转移推荐算法基于社交网络的转移推荐算法是最早应用于移动社交网络的推荐算法之一。
该算法利用用户在不同社交网络上的行为数据，挖掘两个社交网络之间的隐式联系，推测用户的兴趣和偏好，并将其转移到新的社交网络上。
具体来说，该算法通过社交网络之间的相似性和用户之间的社交关系来推荐用户感兴趣的人和内容。
例如，在微博上关注了某个明星，那么在新的社交网络上也很可能会感兴趣这个明星的粉丝。
2. 基于用户话题的转移推荐算法基于用户话题的转移推荐算法是近年来兴起的推荐算法之一。
基于节点亲密度和度的社会网络社团发现方法刘瑶;康晓慧;高红;刘峤;吴祖峰;秦志光【摘要】社会网络是现实社会在网络空间的延伸,研究社会网络的结构特征对于发现网络结构、预测网络行为、保障网络安全有着重要的意义.社团结构是社会网络最重要的一种结构特征.近年来,研究人员提出了大量的社团检测算法,但大多集中在无权网络,不能处理网络中越来越复杂的连接关系.为了衡量有向加权网络中节点之间的关联强度,提出了一种新的节点亲密度定义,在此基础上设计了一种基于节点亲密度和度的社团结构检测方法(community detecting method based on node intimacy and degree,CDID),并在真实的社会网络数据集上进行了实验验证.与传统的社团检测方法相比,CDID方法能够获得更加准确的社团划分结果,并为无向无权、有向无权、无向加权、有向加权网络的社团划分提供了一种统一的解决方法.【期刊名称】《计算机研究与发展》【年(卷),期】2015(052)010【总页数】10页(P2363-2372)【关键词】节点亲密度;节点度;加权网络;模块度;社团检测【作者】刘瑶;康晓慧;高红;刘峤;吴祖峰;秦志光【作者单位】电子科技大学信息与软件工程学院成都610054;电子科技大学信息与软件工程学院成都610054;电子科技大学信息与软件工程学院成都610054;电子科技大学信息与软件工程学院成都610054;电子科技大学信息与软件工程学院成都610054;电子科技大学信息与软件工程学院成都610054【正文语种】中文【中图分类】TP393近年来，随着以互联网为主的社交网络的广泛应用，越来越多的人加入到社会网络中进行信息交流活动．社会网络的应用改变了人们制造、传播和使用信息的方式．同时，社会网络中用户的规模和所制造的信息也在快速增加．据Business Insider的报道，世界上最大的社交网站Facebook的用户数量在2014－07－25已经突破22亿，占全球总人口的1/3．新浪微博的活跃用户数量在2014－09－30达到1．67亿，并且每天新增的微博信息多达1亿条．目前，已有许多学者使用复杂网络的理论和方法从关键成员影响力、社团发现、用户兴趣建模等不同方向对社会网络进行了深入的研究．其中，社团发现作为社会网络研究中的一个基础性问题，不仅在社会学、生物学、电子商务等方面具有重要研究意义，在网络安全方面也具有实际应用价值．现有的信息网络是一个边界模糊、层次不清、高度分布、动态演化的复杂网络．在这种大型的复杂网络中挖掘社团结构有助于找到系统的边界区和核心区，以便在边界区域部署防火墙、防病毒软件和入侵检测系统等安全设备，从而对边界内部实施隔离和保护．另外通过核心社团和骨干节点的识别，有助于控制病毒、舆情在网络中的快速传播．在犯罪组织识别方面，针对国际化恐怖主义和有组织犯罪将活动逐步转移到信息较为隐秘的网络上来，引入社团分析技术能够快速提取社团结构、分析其上下级关系、锁定关键目标群体，这对犯罪侦查、恐怖活动预测、态势掌控等方面都具有重要意义．近年来，研究者在社会网络分析方面做了大量的工作，但是大部份都是基于无权网络．无权网络中的社团划分就是将网络划分为若干个社团，使得社团内部节点之间的连接相对紧密，不同社团的节点之间的连接相对稀疏．然而现实网络如博客网络、电子邮件网络、科学家合作网络、新陈代谢网络等在本质上就是加权网络，不仅要观察2个节点之间是否有关联还要观察其关联的强度．节点之间的关系应该是个渐变有梯度的值，它不应该只有“亲密”和“不亲密”2种界定，而应该有“不亲密”、“比较亲密”、“亲密”和“非常亲密”等这样梯度化的量度方式．本文提出了一种新的节点亲密度定义，用于衡量有向加权网络中节点之间的关联强度，并在此基础上设计了一种基于节点亲密度和度的社团结构发现方法（community detecting method based on node intimacy and degree，CDID）．1 相关工作现代图论技术的发展为复杂社会网络的研究带来了深远的影响．其中，与真实社会网络最相关的一个图论特征就是社团结构，也称为聚类．在计算机科学、社会学、生物学等领域都有大量的研究人员使用图论的理论和方法来进行社团结构的检测，主要包括：1）图分割方法，如 GN（Girvan－Newman）算法［1］；2）模块度最优化方法，如快速Newman（fast Newman，FN）算法［2］、鲁汶（luovain）算法［3］、模拟退火（simulated annealing，SA）算法［4］等；3）标签传播方法，如标签传播（label propagation algorithm，LPA）算法［5］、基于中心（hubs）的算法［6］、COPRA 算法［7］等；4）动力学方法，如社团发现与抽取（finding and extracting communities，FEC）算法［8］、INFOMAP 算法［9］、RN（Ronhovde－Nussinov）算法［10］等．这些方法都是基于网络的结构信息进行社团发现，近年来一些学者开始考虑将网络节点的属性信息加入到社团发现中．Steinhaeuser等人［11］提出了一种为边加权的节点属性相似度（node attribute similarity，NAS）方法，然后将其与传统的随机游走方法结合．Viennet［12］将模块度函数与节点属性相似度函数进行加权求和，然后利用鲁汶算法检测出社团结构．Kewalramani［13］提出利用多个属性的相似性并通过传统的聚类方法发现Twitter的社团．Deitrick等人［14］利用用户在一段时间内发过的tweets信息来逐步提高社团发现的效果．孙怡帆等人［15］通过基于相似度的模块度函数来挖掘微博网络中的社团结构．在这些算法中，模块度最优化算法是当前使用最广的一种社团结构检测方法．Newman等人［16］提出的模块度测度最早是为GN算法定义一个终止条件，后来迅速成为众多社团检测算法衡量社团划分质量的一个重要标准，但是模块度的定义仍然存在一些问题．一般认为，模块度值越大，所得到的划分也越好，但是模块度优化时存在着分辨率限制（resolution limit）和极端退化（extreme degeneraciess）问题［17］．分辨率限制问题是指使用模块度优化的算法不能发现尺寸小于一定规模的社团［18］．极端退化问题是指全局的模块性最大化划分常常隐藏在大量（指数级）的结构并不相似的高模块性解中［19］．由于模块度的定义已经催生了大量优秀的社团检测方法，与其放弃这些方法不如考虑能否用较小的代价增强模块度最优化算法划分社团结构的有效性．Khadivi等人［20］认为采用链接加权的预处理机制和应用多层次、多粒度的社团检测算法，可缓解模块度函数的分辨率限制和极端退化问题．因此，本文着重研究如何给复杂网络的链接分配合适的权重，并采用分层次的模块度最优化算法来获得更有效、准确的社团划分结果．2 基于节点亲密度和度的社团结构发现方法针对复杂社会网络的社团划分，本文提出了1种基于节点亲密度和度的社团发现方法．为了后面描述的方便，将该方法命名为CDID．CDID方法主要分为2个阶段：1）通过定义节点亲密度对有向/无向网络的边进行加权处理；2）提出一种基于节点亲密度和度的模块度新测度，使用分层次的CDID算法，对有向/无向加权网络进行社团结构检测．2．1 基于节点度和亲密度的权重处理社会网络中，用户的关系可以通过加权图G（V，E，W）表示．V 为网络中的节点集合，表示所有用户；E为网络中2个节点之间的边，表示用户间的交流互动行为；W 为网络中边的权重，表示2个节点互动行为的紧密程度，值越大表示用户之间互动连接越紧密．n＝｜V（G）｜，m＝｜E（G）｜，n是图G 中所有节点的数目，而m则是图G中所有边的数目．用邻接矩阵An×n来表示一个具有n个节点的网络，如式（1）所示：于是，网络的总边数则可表示为定义1．节点的度．节点的度ki是与一个节点i关联的边的数目．对合作网络而言，节点的度则代表了这个用户的朋友数量，即这个用户在网络中的影响范围为在有向图中，一个节点的度分为入度（in degree）和出度（out degree）．节点的入度kini 是指从其他节点出发终止于该节点的边的数目，出度kouti 是指从该节点出发终止于其他节点的边的数目，节点的度是入度和出度之和定义2．边的权重．社会网络可以分为有向网络（如邮件网络、微博网络）和无向网络（如论文合作者网络、电影演员合作者网络）2种类型．用邻接矩阵Wn×n来表示一个无向加权网络，矩阵元素Wij表示节点i与节点j连边的权重；相应地，矩阵W＊n×n表示一个有向加权网络，矩阵元素W＊ij表示从节点i连向节点j的有向边的权重．Wij的值越大，说明节点i和节点j之间的连接越紧密，传输信息的可能性越大；反之则说明节点i和节点j之间的连接越稀疏，传输信息的可能性越小．2．1．1 节点亲密度的定义在实际的社会网络中，我们所获得的原始数据是可以直接反映2节点之间联系的频繁程度．因此，我们引入节点亲密度这个新的测量指标来处理这些原始数据的加权操作；同时给出其在有向/无向2种不同网络类型下的明确定义．在无向图中，节点的亲密度用于衡量2个节点之间互动关系的程度，其定义为其中，qij为节点i与节点j之间传输的信息量或联系的次数．在有向图中，节点的亲密度属于单向关系；如果用I（A→B）表示节点A对节点B 的亲密度，则有I（A→B）≠I（B→A）．因此，有向网络中2个节点之间的亲密度用来衡量一个节点向另一个节点联系的频繁程度．设qij为用户i向用户j传递的信息，即节点i到节点j的出度值；qji为用户i从用户j接收的信息，即节点j到节点i的入度值．定义节点i对节点j的亲密度Ii＊j如式（6）所示：其中，qouti 表示节点i向所有节点传输的信息总和；qinj表示节点j从其他所有节点接收的信息总和．从式（6）可知，I＊ij所定义的亲密度具有有向性；当节点i向节点j传输的数据越大时，则I＊ij越大；反之，当节点j向节点i传输的数据越大时，则I＊ji越大．2．1．2 权重的处理模块度Q用来衡量社团内部边的密度与社团之间边的密度的比值．Newman定义的无向无权图下的模块度为其中，kouti 与kini分别为节点i的出度和入度．从式（7）（8）可以看出，当所有节点被划分到同一个社团时，该网络的模块度值取最大值1；当每个节点独立成一个社团时，该网络的模块度取最小值0．根据模块度最大化原则，在社团划分过程中，应尽可能去除公式中值为负的加和项．从式（7）（8）还可以看出，基于模块度最优化的社团划分算法倾向于将度较高的节点划分到不同的社团中．因此在设计社团划分的节点聚类选择判据时，应综合考虑节点亲密度和节点度2个影响因素．综上所述，连接2个节点的边权重取决于2个因素：1）节点之间联系的亲密度；2）2个节点的度值．即：边的权重不能只依赖于节点之间关系的紧密程度，还要考虑度值大的2个节点更倾向于划分在不同的社团中．在无向加权网络中，节点i与节点j连接边的权重为同样地，模块度的定义可以扩展到有向网络，因此Leicht和Newman在无向模块度的基础上又定义了衡量有向网络社团分解的模块度．有向无权图的模块度为在式（9）（10）中，影响因子α的取值范围为［0，1］．在不同的网络中，节点亲密度和节点度值对社团划分的影响是不同的．亲密度对边权重的影响较大时，α值也越大；反之α值越小．特别地，当α＝1时，2节点的亲密度就是其连边的权重．节点的亲密度实质上是考虑节点间传输的信息量．结合节点亲密度与边权重的定义，当2节点传输的数据量越大时，也在有向加权网络中，节点i到节点j的有向边权重为意味着在任意时刻他们之间传输信息的可能性也越大．当α＝0时，网络的社团划分只考虑了拓扑结构．因此，影响因子α合理地平衡了节点亲密度和节点度值对边权重的影响．2．1．3 加权模块度公式应用新的边权重式（9）可得到无向加权网络中基于节点亲密度和度的新加权模块度Qw：其中，邻接矩阵W＊表示一个有向加权网络；wouti 与wini分别为节点i的出向权重和入向权重；w＊i＝wini＋其中，邻接矩阵W 代表一个无向加权网络，矩阵的元素值不再是0或1，而是与之对应边的权重值Wij；w表示网络中边的总权重值．对于有向加权网络，基于新的权重式（10），可得到基于节点亲密度和度的加权模块度Q＊如式（12）所示：2．2 算法设计层次化是社会网络社团结构的一个常见特征．大规模的社会网络往往具有多层次的组织结构，例如大社团往往是由若干较小规模的社团合并得来，而这些小社团则可能由若干更小规模的社团构成．鲁汶算法采用了多层次聚类的基本思想，在社团划分时能够获得较高的聚类质量，并且能够快速检测到网络中的层次化社团结构．为了能够在大规模的真实社会网络中进行社团结构检测，我们基于鲁汶算法提出了一种新的基于节点亲密度和度的社团划分方法CDID．该方法能够快速检测加权网络中的层次化社团结构，检测过程可分为2个阶段进行重复迭代．1）阶段1．在n个节点的无权网络中，通过式（9）（10）得到每条边的新权重值．接下来，每个节点形成一个社团，社团个数的初始值为n．然后，对于任意节点i，将节点i加入到与其相邻的每一个邻居节点所在的社团，并计算加入后的模块度增量ΔQ．比较ΔQ的值，选取ΔQ为最大值时对应的那个邻居节点j，将节点i加入到节点j所在的社团，这里要求ΔQ值必须为正．当所有的模块度增量ΔQ都为负值时，节点i保持不动仍然放置在原始社团．这个合并社团的过程重复迭代，直到没有节点的转移能使模块度值增加，这时得到社团结构的第1层次．在无向加权网络中，基于无向加权模块度式（11），将节点i移动到其邻居节点j所在的社团Cj，所导致的社团模块度增量ΔQ可采用式（13）计算：其中，wicsjo＊是社团Cj所有内部无向边的权重值之和，wi，cj是连接节点i与社团Cj内部节点的所有无向边的权重值之和，wcrjel是与社团Cj的内部节点有关联的所有无向边的权重值之和，wi是与节点i有关联的所有无向边的权重值之和，w是网络中所有无向边的权重值之和．在有向加权网络中，基于有向加权模块度式（12），将节点i移动到其邻居节点j所在的社团Cj所导致的社团模块度增量ΔQ＊可采用式（14）计算：其中，wicsjo＊是社团Cj所有内部有向边的权重值之和，wi＊，cj是连接节点i与社团Cj内部节点的所有有向边的权重值之和，wicnj是从社团Cj外部节点指向社团Cj内部节点的所有有向边的权重值之和，wcojut是从社团Cj内部节点指向社团Cj外部节点的所有有向边的权重值之和，wiin是指向节点i的所有有向边的权重值之和，wiou t 是从节点i出发的所有有向边的权重值之和，w＊是网络中所有有向边的权重值之和．2）阶段2．以阶段1检测出来的社团作为新的节点构建一个新的网络．原社团之间的边权重值之和作为新节点之间的边的权重值，原社团内部边的权重值之和作为新节点的自循环边的权重值；然后在新网络中重复阶段1的算法进行社团结构的检测，得到社团结构的第2层次．用一个名词pass来定义这2个阶段．因为要将划分出来的社团作为节点构建新网络，所以每经过一个pass，中间社团（meta－communities）的数目减少，并且大部分计算时间花在阶段1．重复执行pass，直到社团结构不能再划分出更高层次为止，并得到模块度的最大值．CDID方法的伪代码如下所示：算法1．CDID方法的伪代码．输入：读入用邻接表表示的网络G（V，E，W）、统计节点总数n；输出：一组社团集合．begin passrepeatPhase1：将网络G中各节点初始化为独立社团；repeatfor i∈Vdofor j∈Vdo将节点i从它所在的社团删掉，加入到与它相邻的每一个邻居节点j所在的社团；计算加入后的模块度增量ΔQ；end forifΔQ＞0then选取ΔQ为最大值时对应的那个邻居节点j，将节点i加入到节点j所在的社团；else节点i保持不动；end ifend foruntilΔQ的值不再改变；end Phase1Phase 2：以Phase1检测出来的社团作为新节点，原社团之间的边权重值之和作为新节点之间的边的权重值，原社团内部边的权重值之和作为新节点的自循环边的权重值；执行Phase 1；end Phase2until社团结构不能再划分出更高层次；记录模块度的最大值；end Pass3 实验结果与分析为了验证CDID方法的有效性和合理性，我们选用了原始的不加权的鲁汶算法、简单加权的鲁汶算法来与CDID算法进行社团划分的对比实验．不加权方法（no weight method，NW）直接采用模块度式（8）来进行社团划分．简单加权方法（simple weighted method，SW）是只考虑节点之间互动的次数作为权重，如节点i向节点j发送5封邮件，即节点i指向节点j的边权重为5；节点j向节点i发送10封邮件，即节点j指向节点i的边权重为10．CDID方法是一种复杂加权方法，使用模块度式（11）（12）来进行社团划分．此外，为了验证CDID方法在无向无权、有向无权、无向加权、有向加权4种不同类型网络下的性能，我们选用了4个不同类型的真实社会网络数据集和一个人工生成的基准网络数据集（LFR benchmark）［21］．4个真实数据集可由表1简单汇总表示．Table 1 Real Social Network Datasets表1 本实验所采用的真实数据集Nameof Number of Edges Datasets Type Number of Nodes Contact Times ENRON Email Directed－Weighted 151 1 771 33 124 Cell Phone Calls Directed－Weighted 400 1 562 9 834 School Email Directed－Weighted 4 368 76 015 679 290 DBLP Undirected－Weighted 142 419 304 940 404 0941）数据集1．由CALO项目（a cognitive assistant that learns and organizes）收集并提供的 ENRON电子邮件数据集．该数据集是2001年美国安然公司151名高级管理者之间邮件往来记录，共计33 124封邮件［22］．2）数据集2．Cell Phone Calls数据集．包含2006年6月份在Isla Del Sueno 的400部手机10d内的9 834次通话记录．对 Cell Phone Calls网络进行社团划分意在提供Catalano组织的关键信息［22］．3）数据集3．某高校电子邮件数据集．这是我们采集的某高校邮件服务器上2011－01—2011－12的邮件数据．用节点来表示邮件用户，用边来表示2个用户之间有邮件传送的关系，且传送关系具有有向性．另外考虑到域外用户和本域用户，只提取发送方和接收方都是本域用户的邮件．经处理，该数据集包含4 368个节点、679 290封邮件，每个用户一年的平均邮件收发量是155．52封．4）数据集4．DBLP论文合著关系网络，即由论文合著作者之间形成的社会关系网络．DBLP是由德国特里尔（TRIER）大学建立的一个计算机类期刊和会议论文集的数据库系统，为用户提供权威的论文数据和方便的查询服务．本实验下载并抽取了该站点提供的2011年到2015年被421个与数据库系统、数据挖掘、数据安全等领域相关的国际会议（包括SIGMOD，VLDB，KDD，ICDE等）所收录的论文104 110篇，其中合著作者142 419位．3．1 有向网络社团划分实验本实验对表1中的有向网络数据集进行社团划分．这里以ENRON邮件数据集的划分结果为代表进行详细分析．图1给出了使用CDID方法、NW方法以及SW方法对ENRON邮件数据集进行社团划分的结果比较．对于CDID方法，α＝1．0，表明在式（10）中α＝1；α＝0．8，表明在式（10）中α＝0．8 ．Fig．1 Comparison of different methods in terms of community size distribution based on ENRON dataset．图1 ENRON邮件数据集社团大小规模分布比较从图1可以看出，CDID方法划分结果的社团粒度小于NW和SW划分结果的社团粒度；CDID方法能够发现较小的社团，有效缓解了模块度最优化算法的分辨率限制问题．同时由于CDID方法引入了新权重，社团划分时可参考的信息更多，超大社团的规模也有所减少，社团划分的准确性有所提高．图2展示了CDID方法与NW方法、SW方法对ENRON邮件数据集进行社团划分后得到的社团数目和模块度的对比，横坐标表示影响因子α的取值．从图2可看出，当采用NW方法进行社团划分时，得到的模块度值为0．410，社团个数为8；当采用SW方法时，得到的模块度值为0．629，社团个数为7；而采用CDID 方法，当α＝1．0时，模块度值为0．631，社团个数为9．实验结果表明CDID 方法在保证较高的模块度值（即社团划分质量）时，能得到更多的社团数目即更细致的社团划分，有效缓解了模块度最优化算法的极端退化问题．Fig．2 Comparison of different methods in terms of modularity and community number based on ENRON dataset．图2 ENRON邮件数据集社团划分的结果比较从图2可以看出：当α值越大时，社团的模块度值越高，当α＝0．8时社团个数最多．可见，相对于节点的拓扑度，节点之间的亲密度对社团划分的模块度和社团层次结构的影响力更大．3．2 无向网络社团划分实验本实验对表1中的无向网络数据集进行了社团划分．这里以DBLP数据集的划分结果为代表进行详细分析．首先，为了对DBLP网络不同合著作者之间的初始权重进行合理赋值，本文将DBLP网络中合著作者之间的初始权重关系的形成看作一个投票过程．Ai代表署名排序在第i位（i≤4）的作者，OA代表署名排序在第5位及之后的作者．每一篇合著论文相当于一轮投票，在任意一轮投票中，如果第i位合著作者（Ai）与论文的第1位作者（A1）在署名排序中靠得越近，则Ai与A1之间的关系权重将获得较高的投票．另外通过对DBLP网络进行统计发现，99%的论文其合著作者数目小于等于10，所以可以只抽取论文的前10位作者．基于以上考虑，表2给出了一种对DBLP网络中的节点（即作者）关系赋予初始权重的赋值策略，然后使用式（9）对DBLP网络进行加权处理．图3展示了采用CDID方法、NW方法以及SW方法对DBLP网络进行社团划分得到社团大小的规模分布情况．为了更清楚地展示对比结果，图3中仅显示了社团大小最大的80个社团．Table 2 Initial Weight Assignment Strategy of DBLP Network表2 DBLP网络初始权重赋值策略Author Relationship Assigned Value A1－A24 A1－A33 A1－A4 2 A2－A3 1 A2－A4 1 A3－A4 1 A1－OA 1Fig．3 Comparison of different methods in terms of community size distribution based on DBLP dataset．图3 DBLP数据集社团大小规模分布比较3种方法得到的社团数目都在7 900以上．从图3可以看出CDID方法检测到的社团粒度明显小于NW加权方法和SW加权方法．NW方法检测到的最大社团为4 959，SW 方法检测到的最大社团为3 082，CDID方法检测到的最大社团为1 815，CDID方法相比NW方法降低了63%，相比SW方法降低了41%．CDID 方法的模块度值为0．952，比NW方法增加了10．7%，比SW方法增加了8．1%．因此，我们可以说CDID方法在减小超大社团的规模、缓解模块度的分辨率限制问题、提高社团划分质量等方面有着良好的表现．图4展示了影响因子α采取不同值的CDID方法、NW方法以及SW方法对DBLP数据集进行社团划分得到的模块度和社团数目的对比．从图4可以看出，采用CDID方法进行社团划分时，其划分结果具有相对较高的模块度值；同时，当影响因子α的取值从0增加到1时，CDID方法得到的社团数目介于8 050～8 100。
移动社交网络中基于影响力的数据转发算法刘艳萍;王青山;王琦;付沙沙;任丽丽【摘要】在移动社交网络中，人们通过携带无线设备在近距离范围内彼此传递信息，从而达到信息的传播。
由于移动社交网络中一般不存在端到端的连接，使得数据转发算法成为一个重要问题。
文章从社区和节点的社会属性角度，利用社区和节点的影响力，提出了一种基于影响力的数据转发算法（data forwarding algorithm based on impact ，DFAI）。
在该算法中，携带数据包的节点只有在遇到影响力达到一定要求的节点时，才拷贝数据包给相遇节点。
仿真试验结果显示，与经典的Epidemic和Label算法相比，DFAI可以明显降低网络开销，同时接近Epidemic算法达到的最大传递率。
%Mobile social users can communicate by physical interact with each other via mobile device in mobile social networks .In view of the intermittent and uncertain network connectivity in the mobile social network , the data forwarding algorithm becomes important . From the social perspective of community and node ,a data forwarding algorithm based on impact (DFAI) is proposed in this paper . In DFAI ,the node with the packet only copies to the encounter node whose impact meets certain re‐quirement .The simulation results show that the proposed algorithm can reduce network overhead ob‐viously compared with Epidemic algorithm and Label algorithm ,and its maximum delivery ratio is close to that obtained by Epidemic algorithm .【期刊名称】《合肥工业大学学报（自然科学版）》【年(卷),期】2015(000)002【总页数】4页(P195-198)【关键词】移动社交网络;影响力;转发;延迟【作者】刘艳萍;王青山;王琦;付沙沙;任丽丽【作者单位】合肥工业大学数学学院，安徽合肥230009;合肥工业大学数学学院，安徽合肥 230009;合肥工业大学数学学院，安徽合肥 230009;合肥工业大学数学学院，安徽合肥 230009;合肥工业大学数学学院，安徽合肥 230009【正文语种】中文【中图分类】TP301.6网络中由于节点密度稀疏、电量有限等原因导致数据在传输过程中不能确保端到端之间存在一条路径，这类网络被称为时延容忍网络，也叫容迟网络（delay and disruption－tolerant interoperable networking，DTN）［1－2］。
团树传播算法
1群体树传播算法
群体树传播算法（Group-Tree Broadcasting Algorithm，GTB）是一种以拓扑信息为基础的网络路由算法，它由一组交换站构成，这组交换站构成一棵树状结构，其中根节点接受和播发数据包，树形结构代表了网络的拓扑结构，路径由父节点到子节点，树形结构支持以完全消息一致的方式实现网络之间的路由操作，并进行可靠性维护。
2优点
GTB算法有许多优点，其中最突出的几个优点：
（1）GTB算法是建立在一棵树状结构上，因此它能够减少网络中数据库的開銷，使得网络可以运行的更加高效；
（2）树形结构的拓扑终能够增加传输消息时路径的可靠性；
（3）GTB算法在网络拓扑中增加了很多灵活性，从而使得网络系统更容易进行修改，提高了系统的可靠性；
（4）GTB算法还可以支持多种多样的路由协议，支持多种协议的灵活性和可靠性也提高了；
（5）GTB算法通过构建以根节点为中心的树形拓扑网络，有效减少了控制信息传输时间。
3缺点
GTB算法也有一些缺点，其中最重要的是：
（1）GTB算法仅适用于以根节点为中心的树形网络，如果网络拓扑复杂，GTB算法不适用；
（2）GTB算法依赖于根节点，一旦根节点出现问题，整个网络便无法正常运行；
（3）GTB算法的更新速度较慢，若要修改网络结构需要更改整个树形结构，这需要较长的更新时间；
（4）GTB算法并不能有效解决网络中间节点掉线隔离等问题。
4结论
可以说，GTB算法是一种可灵活构建，易于实现的网络路由算法，它可以有效地减少网络中的广播开销和网络拓扑的复杂性，从而提高网络的可靠性，但也存在着一些显著的缺点，这些缺点需要我们在设计网络时充分考虑，以避免网络出现隔离的现象出现。
