基于博弈论的重叠社区发现

发布时间：2020-10-19 09:21

　　 近年来,复杂网络研究成为信息处理领域的研究热点。生活中的许多复杂系统,如城市道路交通网络、微博用户网等,都可以抽象为复杂网络。社区结构作为复杂网络的主要性质之一,对社区结构的检测成为复杂网络领域的研究重点。社区作为社区结构的组成部分,处于相同社区内的节点之间连接紧密,处于不同社区的节点之间连接较为稀疏。研究复杂网络的社区结构,有助于人们更全面地认识网络功能、更准确地预测网络的演化。博弈论是研究参与者之间策略相互作用的理论。博弈论可用于解释社区在复杂网络中自上而下的形成过程。近年来不少研究者将博弈论用于社区发现,将检测网络社区结构的过程建模为社区形成博弈。研究取得了良好效果,证明了博弈论用于社区发现的有效性和合理性。本文在分析现有社区发现算法及基于博弈论的社区发现算法的基础上,提出基于博弈论的重叠社区发现算法。主要完成以下内容:(1)本文提出基于节点属性的收益函数。为了得到更准确的社区划分结果,针对现有算法未考虑节点属性会影响节点策略选择的问题,本文加入节点度值与其所加入的社区中所有节点度值的比例,得到新的增益函数。由于节点加入新的社区会相应地付出代价,因此本文中节点的收益函数为节点增益函数和损失函数的差值。(2)本文提出基于节点重要度排序的社区发现博弈算法。针对节点属性对节点在网络中进行策略选择时顺序的影响,本文将节点按照重要度从大到小排序,并依次选择策略提高收益。本文算法中节点的策略为加入社区、离开社区和转换社区。最后将本文提出的算法与现有算法分别在不同的真实网络和人工网络上进行对比实验,结果表明本文的算法优于其它算法。
【学位单位】：天津科技大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5;O225
【部分图文】：

法都来自图论［６］。在数学和计算机科学中，网络被定义为由节点和连接节点的边所组??成的图。数学形式表达为：Ｇ?＝?（ｒ，Ｅ），其中节点集丨厂丨＝？，边集｜Ｅ｜＝ｍ，？为网络??中的节点数，ｍ为网络中的边数。图２－１所示的网络中的节点表示系统中的个体，边??表示个体之间的关系。网络的基本概念［７］有：??緲，．＿＇ｈ?．??■?ｍ２＊Ｕ?■■３７：；：?＾１８－?■＂：??■?Ｕ?．?—９１．．?＿２５?’?．趣?９３?鼸?２８??ｍ；＇－?ｍ?，??嶋ｎ．?＿的；．费１?■卜?■＇?？１０６??丨■?州?＿ｖｉ?＿１Ｕ?．麵ｆ?睡＞５?瞻处?ａｎｏ??■ｋ＿ｖ??■．?■外１Ｖ?署．．?．．．?吧，翻趣⑴??■－Ｕ－；?ａ＼ｍ＇ｎ＾ａ＾??＾?．?＾６：?禮１００??窗５２?■??图２－１复杂网络示意图??Ｆｉｇ．?２－１?Ｓｃｈｅｍａｔｉｃ?ｄｉａｇｒａｍ?ｏｆ?ａ?ｃｏｍｐｌｅｘ?ｎｅｔｗｏｒｋ??（１）

法都来自图论［６］。在数学和计算机科学中，网络被定义为由节点和连接节点的边所组??成的图。数学形式表达为：Ｇ?＝?（ｒ，Ｅ），其中节点集丨厂丨＝？，边集｜Ｅ｜＝ｍ，？为网络??中的节点数，ｍ为网络中的边数。图２－１所示的网络中的节点表示系统中的个体，边??表示个体之间的关系。网络的基本概念［７］有：??緲，．＿＇ｈ?．??■?ｍ２＊Ｕ?■■３７：；：?＾１８－?■＂：??■?Ｕ?．?—９１．．?＿２５?’?．趣?９３?鼸?２８??ｍ；＇－?ｍ?，??嶋ｎ．?＿的；．费１?■卜?■＇?？１０６??丨■?州?＿ｖｉ?＿１Ｕ?．麵ｆ?睡＞５?瞻处?ａｎｏ??■ｋ＿ｖ??■．?■外１Ｖ?署．．?．．．?吧，翻趣⑴??■－Ｕ－；?ａ＼ｍ＇ｎ＾ａ＾??＾?．?＾６：?禮１００??窗５２?■??图２－１复杂网络示意图??Ｆｉｇ．?２－１?Ｓｃｈｅｍａｔｉｃ?ｄｉａｇｒａｍ?ｏｆ?ａ?ｃｏｍｐｌｅｘ?ｎｅｔｗｏｒｋ??（１）

个普遍特征，整个网络是由许多个社区组成的；同一个社区内部的节点之间联系较为??密切，而社区之间的节点联系则较为松散。各社区之间没有重叠节点的社区称为非重??叠社区，如图２－５所示。有重叠节点的社区称为重疊社「Ｘ：，如图２－６所示。网络中包??含多个社区的现象称为网络的社区结构。给定一个网络，找出它的社区结构的过程称??为社区发现。??对社区结构的发现具有重要的意义，例如研究社会网络中的社区，可以发现有着??共同爱好或背景的一群人；研宄生化网络中的社区，可以发现某个复合体或某种功能。??因此，社Ｒ发现成为当前复杂网络领域研究的一个热点。研究者已经提出了多种方法，??如基于模块度的优化方法、随机游走方法、拉普拉斯特征值方法、极值优化方法、派??系过滤法、博弈演化方法等。除博弈演化外的其它对一个复杂网络进行社｜ｘ：发现的算??法，其实是把复杂网络按照某种标准进行了划分，然后对每个社区进行进－－？步挖掘。??而博弈演化算法是模拟复杂网络自上而下形成社区的过程。??９??
【相似文献】

相关期刊论文 前10条

1 周林洋;;博弈论与纳什均衡理论[J];金山企业管理;2004年02期

2 梅生伟;洪奕光;陈皓勇;刘锋;魏韡;;“工程博弈论”专刊前言[J];控制理论与应用;2018年05期

3 ;博弈论的魅力[J];金融博览;2018年09期

4 郭玮宏;;从博弈论角度分析相声创作和表演中的一些技巧[J];曲艺;2017年02期

5 司志本;张琪;;“帽子问题”及其衍生问题[J];中学数学杂志;2017年07期

6 辛琦媛;孟令军;;博弈论视角下大学课堂座位现象分析[J];文教资料;2017年04期

7 王开升;;浅析应用数学与金融学的关系[J];课程教育研究;2017年30期

8 胡静;;博弈论的成长历史和前景[J];中学课程资源;2008年06期

9 程代展;;《工程博弈论基础及电力系统应用》评介[J];控制理论与应用;2016年11期

10 孙雷;;从博弈论视角探索三小球项目击球落点的最佳组合[J];青少年体育;2017年08期

相关博士学位论文 前10条

1 邬锐;博弈论在戏剧冲突中的应用研究[D];上海戏剧学院;2013年

2 邢永杰;基于博弈论的虚拟组织理论研究[D];天津大学;2004年

3 马小琪;基于博弈论的资产评估机理与方法研究[D];哈尔滨工业大学;2006年

4 张国鹏;基于博弈论的无线网络资源竞争与协作机制研究[D];西安电子科技大学;2009年

5 孙连菊;基于博弈论的城市公共交通系统建模与算法研究[D];北京交通大学;2009年

6 Brima Fallah;基于博弈论的干扰通信系统的分布式框架设计与研究[D];华中科技大学;2012年

7 翁国富;经典博弈论中引入量子叠加与纠缠产生的一些新性质[D];南京大学;2014年

8 张艳娟;历史唯物主义视域下的博弈分析[D];山东大学;2011年

9 姜殿玉;管理科学中的带熵博弈论[D];大连海事大学;2008年

10 丁川;基于博弈论的营销渠道协作研究[D];西南财经大学;2009年

相关硕士学位论文 前10条

1 任静;基于博弈论的重叠社区发现[D];天津科技大学;2018年

2 陈明;基于博弈论的网联车路径选择算法研究[D];湖南大学;2018年

3 刘浩;面向车载云的车辆协作激励机制研究[D];北京交通大学;2018年

4 王大鹏;济南二手车交易市场效率的提升策略研究[D];山东师范大学;2018年

5 徐淑芸;基于博弈论的建筑施工安全利益相关方行为研究[D];河北工业大学;2016年

6 圣铭;基于博弈论的SAR干扰分析与对抗研究[D];西安电子科技大学;2018年

7 田思飞;基于博弈论的异构无线网络选择和资源分配算法研究[D];西南交通大学;2018年

8 刘晓玲;异构网络下基于博弈论的D2D网络接入算法的研究[D];辽宁工业大学;2018年

9 许金;基于博弈论的道路货运绿色发展及政府补贴分配研究[D];北京交通大学;2017年

10 张硕磊;基于博弈论的库存优化策略选择分析[D];昆明理工大学;2017年

本文编号：2847024