社会网络中基于路径的社团划分方法_张欣欣.pdf
《社会网络中基于路径的社团划分方法_张欣欣.pdf》由会员分享,可在线阅读,更多相关《社会网络中基于路径的社团划分方法_张欣欣.pdf(6页珍藏版)》请在咨信网上搜索。
1、第 39 卷第 2 期福建师范大学学报(自然科学版)Vol.39,No.2(2023 年 3 月)Journal of Fujian Normal University(Natural Science Edition)Mar.2023DOI:10.12046/j.issn.1000-5277.2023.02.004文章编号:1000-5277(2023)02-0035-06社会网络中基于路径的社团划分方法张欣欣,许力,周赵斌(福建师范大学计算机与网络空间安全学院,福建师范大学福建省网络安全与密码技术重点实验室,福建 福州350117)摘要:针对社会网络中用户信息时的传播路径,提出一种社会网络中
2、基于路径的社团划分方法 首先,采用边介数中心性来进行社团划分,接着设计了一种基于重要路径的社团更新方法来解决初步划分社团之后的碎片问题,最后针对信息传播中用户态度发生变化的问题,提出基于 PSO 算法的社团动态更新方法实验分析说明,本方案时间复杂度较小,性能也具有一定的优势关键词:社会网络;社团划分;重要路径;边介数中心性;粒子群优化算法中图分类号:TP393.1文献标志码:A收稿日期:2022-06-02基金项目:国家自然科学基金资助项目(U1905211);中央引导地方科技发展专项(2021L3032)通信作者:周赵斌(1989),男,实验师,研究方向为网络与信息安全和无线网络 zbzho
3、u Path-Based Community Detection Method in Social NetworksZHANG Xinxin,XU Li,ZHOU Zhaobin(College of Computer and Cyber Security,Fujian Normal University,Fujian Provincial Key Lab ofNetwork Security and Cryptology,Fuzhou 350117,China)Abstract:Aiming at the transmission path in social network,this pa
4、per proposes a path-basedcommunity detection method in social network Firstly,the edge betweenness centrality is used todivide the community,and then a community update method based on important path is designed tosolve the fragmentation problem after the preliminary division of the community Finall
5、y,aiming atthe change of user attitudes in information dissemination,a community dynamic update methodbased on PSO algorithm is proposed Experimental analysis shows that the complexity of this schemeis small,and the performance has certain advantagesKey words:social networks;community detection;impo
6、rtant path;edge betweenness cen-trality;particle swarm optimization社交网络1 是一类基于 WEB 的社会网络系统,例如脸书、推特和微博等,它是一种人与人之间的关系与互动的结合,人们用电子邮件交换信息所构成的关系网络是在线社交网络的最早形式 随着无线通信技术的迅猛发展,社会网络(social networks,SNs)应运而生 在社会网络中,个体基于不同的关系如亲人、好友、合作等关系可构成一个多渠道的通讯网络,发生在复杂网络上的各种传播行为与人们的生活密切相关,如社会网络上的信息、谣言、行为等社会信息的传播时刻影响着人们的日常生
7、活和工作2 Dong3 认为社交网络具有典型的无尺度网络和小世界网络属性 Pietilnen 等4 发现移动社会网络中人们表现出空间上复杂的移动性以及各个用户具有复杂的个人属性随着科学技术的发展,社团结构发展成为社会网络中的重要属性,它通常代表具有相似属性、爱好或者更亲密关系特点的用户群体,就网络的介观结构而言,社团的研究吸引了很多学者,检测社会网络中的社团结构是分析社会网络的重要任务 例如,疫情期间通过对社会关系的检测来识别社团,可以及时做到对社团中的成员合理有效控制 在科研合作网络中,有效识别出合作社团有利于学术交流和知识传播 近年来,对于社团检测的研究热度不减,学者们对其深入研究并提出了
8、很多经典方福 建 师 范 大 学 学 报(自 然 科 学 版)2023 年法 这些算法主要分为 3 类5:第 1 类是传统的图划分和数据聚类方法,包括图划分、谱聚类6 等:第 2 类是使用分裂算法去除连接不同社团节点的边,常用的是由 Girvan 和 Newman 提出的算法78;第 3 类则是优化算法,比如模拟退火算法等启发式算法9 随着数据的积累,社会网络的规模正在逐渐增长并变得巨大,这就导致了大型社会网络的社团检测无法用传统的算法在时间和空间复杂性方面解决问题,所以社团检测算法的可伸缩性是一个关键问题 为了解决这一问题,学者们1014 进行了大量研究,这些方法可分为并行社团检测方法、局部
9、社团检测方法和基于网络规模缩减的社团检测方法 Satuluri 等人15 研究了一种图稀疏技术来加速现有的图聚类算法,在这种方法中,通过除去一些可能位于社团之间的边来保留网络的社团结构 Macropol 等人16 提出了一种顶级图簇的新技术来寻找一个大型网络的最佳社团,该方法只找到了最佳簇的一个子集,而不是整个图中的所有簇,并通过减少搜索空间来节省时间和内存 Abou-ieili 等人17 提出了新的粗划分策略,它允许任意大小的顶点集折叠在一起,以解决图聚类问题这些社团检测的方法都是基于全局网络拓扑的,在社团检测过程中并没有充分利用社会网络的结构特征,事实上,在社会网络中用户传播信息时的传播路
10、径是很重要的,针对这个特点,本文提出一种社会网络中基于路径的社团划分方法 首先,采用边介数中心性来进行社团划分,接着设计了一种基于重要路径的社团更新方法来解决初步划分社团之后的碎片问题,最后针对信息传播中用户态度发生变化的问题,提出基于 PSO 算法的社团动态更新方法1预备知识1.1社团结构社团18 是指网络中内部节点比外部节点连接更为紧密的一组节点 在社会网中,同一个社团的用户属性比来自不同社团的用户更为相似,这就意味着他们可能会分享更多的信息、兴趣、经验和其他有用的信息 因此,检测社会网络中的社团结构将直接影响社会网络的优化和管理活动 近年来,针对网络中社团检测的方法和评价标准被学者专家广
11、泛研究,如模块化、标准化切割、结构密度等1.2边介数中心性(edge betweenness centrality,EBC)边介数中心性19 是基于最短路径的图中心性的一种度量,是指网络中所有最短路径中经过该条边的路径数目占最短路径总数的比例,也就是说网络中包含 e 的所有最短路径数占所有最短路径数的百分比 边介数刻画了该边的控制能力 如果这个边的介数中心性高,那么他对整个网络的影响很大,需要有更多的节点需要通过它与其他节点发生联系 对于给定的图 G,N 为节点数量,e 是 G 中任意一条边,s 和 t 分别是一条边的 2 个顶点,则 e 的边介数中心性如下:EBC=1(N 1)(N 2)s,
12、tG e,std(s,t)(e)d(s,t)(1)其中,d(s,t)表示从 s 到 t 的最短路径数量,d(s,t)(e)表示从 s 到 t 经过边 e 的最短路径的数量1.3粒子群优化算法(particle swarm optimization,PSO)Kennedy 和 Eberhart 第一次提出粒子群优化算法20,最初是一群鸟随机搜索这个区域里唯一的一块食物,所有的鸟都不知道食物在哪里,但是他们知道当前的位置离食物还有多远,最简单有效的就是搜寻离食物最近的鸟的周围区域 粒子群优化算法初始化为一群随机粒子,通过迭代找到最优解,在每 次 迭 代 中,粒 子 通 过 跟 踪 位 置 矢 量
13、Xi=xi,1,xi,2,xi,n 和 速 度 矢 量 Vi=vi,1,vi,2,vi,n 来更新自己 粒子通过不断更新自己的位置来寻找最优解,第一个是粒子本身找到的最优解,这个解叫做个体极值 pBest,另一个极值是整个种群找到的最优解,这个极值是全局极值gBest 通过跟踪这 2 个极值,粒子将朝全局最优解的方向移动 粒子根据公式(2)和(3)来更新:vi,d(t+1)=wvi,d+c1r1(pBest xi,d(t)+c2r2(gBest xi,d(t),(2)xi,d(t+1)=xi,d(t)+vi,d(t+1),(3)其中,t 表示第 t 次迭代,d 表示粒子的第 d 个维度,vi,
14、d表示速度矢量中的第 d 个维度,w 是惯性重63第 2 期张欣欣,等:社会网络中基于路径的社团划分方法量,c1和 c2是加速常数,r1和 r2是区间 0,1中随机分布的随机数2基于路径的社团划分方法社团划分的目标是识别高相似度的群体,并将它们划分到同一个社团结构 社团划分通常可以从2 个方面进行:第 1 种方法称为凝聚法,从原始图的节点集开始,边缘根据相似度值的递减顺序迭代地添加到相应的节点对中;第 2 种称为分裂方法,从原始图开始,根据相似度的递增顺序去删除边本节首先用分裂方法来进行社团划分,主要采用的是边介数中心性,接着设计了一种基于重要路径的社团更新方法来解决初步划分社团之后的碎片问题
15、,最后针对信息传播中用户态度发生变化的问题,提出基于 PSO 算法的社团动态更新方法2.1基于边介数中心性的社团划分对于任意一个社会网络可以抽象为一个图 G(V,E),采用边介数中心性来删除原始图的边来构造社团 因此,对任意一条边eE的介数中心性是通过e的其他节点之间的最短路径数 如果一个网络中包含社团之间稀疏边的连接,则不同社团之间的所有最短路径都必须沿着其中一条边,即连接社团之间的边具有较高的边介数中心性 通过移除这些边能够得到稳定的社团结构 具体步骤如下:(1)对于网络中的每条边,根据公式(1)计算他们的边介数中心性,并按照递减顺序进行排列;(2)按照递减顺序,移除边介数中心性最大的那条
16、;(3)移除之后重新计算边介数中心性,同样按照递减顺序进行排列;(4)重复步骤(2)和(3),直到没有稀疏边的存在2.2基于重要路径的社团融合经过社团划分,除得到理想的社团结构之外,还会生成一些非常小的碎片社团或者孤立节点,针对这一问题,提出了一个基于重要路径的社团更新法来将碎片和孤立点融入相应的社团 在社会网络中,用户之间的信息交互是通过传播路径实现的,本文将通过判断碎片社团和孤立点与大社团之间信息传播的重要路径来实现融合确定具有影响传播的路径需要从图中的任意节点开始搜索到其他节点的所有有效的无环路径 由于找到 2 个节点之间的所有可能的路径是非常耗时的,并且需要大量的存储空间,而且随着路径
17、长度的增加,信息传播的影响逐渐减小,需要限定一个路径长度的阈值来筛除影响力很小的路径,以此来保留有效路径 将节点 v 和节点 u 之间的有效路径集合定义为 p(uv)=p1,p2,pl,那么这条路径上影响传播路径的效果为有效路径影响扩散的乘积,将其定义为:uP(v)=pP(uv)ni=1w(Vi,Vi+1),p=V1,V2,Vn,n 2(4)其中,w(Vi,Vi+1)表示从 Vi到 Vi+1之间的权重对于初划分之后的碎片社团和孤立点,确定节点与其他社团之间的路径,社团融合的具体步骤如下:(1)首先筛选出距离社团中的边缘节点之间的跳数 h 3 的孤立节点 v 作为候选融合源节点;(2)根据公式(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 社会 网络 基于 路径 社团 划分 方法 欣欣
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。