基于共邻节点的复杂网络社区划分算法研究
发布时间：2021-11-11 00:41
复杂网络作为研究现实世界复杂系统的理论模型,能抽象概括复杂系统的结构特征,将现实世界网络以直观具体的形式表现出来。复杂网络的社区结构是内部连接紧密、外部连接稀疏的簇。划分复杂网络中的社区结构可以揭示网络中存在的结构特征和关联信息、发现网络的内在属性,具有重要的实际应用价值。社区结构划分本质就是网络节点聚类,本文基于共邻节点展开对复杂网络的社区划分算法研究,主要工作如下:（1）为解决传统层次聚类算法划分非重叠社区存在时间复杂度高、社区划分准确率低等问题,提出基于共邻节点相似度的社区划分算法。算法考虑到共邻节点对节点间相似度的影响,新颖的提出共邻节点相似度模型,模型构建星型邻域网络,用星型邻域网络间的相似度度量节点间的相似度;并通过判断星型邻域网络间是否包含相同节点,若不包含相同节点则不进行相似度的计算,从而达到降低复杂度的目的;根据节点相似度和节点局部影响力对节点进行初步聚类,然后以模块度优化为目的对初步聚类得到的社区进行合并,从而获到更优的社区划分结果。（2）为体现出现实世界网络特征结构,符合实际网络情况,提出基于节点从属度的加权网络重叠社区划分算法。该算法构建加权网络模型,通过模型将...
【文章来源】：西安科技大学陕西省
【文章页数】：60 页
【学位级别】：硕士
【部分图文】：
非重叠社区结构示例图
西安科技大学全日制工程硕士学位论文2话题讨论平台，识别出具有相似主题的热点讨论话题，通过发现用户集中讨论的话题来把握网络中的热点主题，把握话题的发展动向；针对淘宝、京东等购物平台，根据相似的消费喜好和消费水平的用户进行社区划分，能更加有效的针对特定的用户以及群体进行相应的广告定位投放，推荐相应类别的商品，提高平台的销售量；在传染性疾病以及病毒传播方面，根据病人接触关系网以及活动轨迹，查找密切接触者，可以在最短的时间内采取最有效的措施控制疾病的传播，对预防和治疗传染性疾病具有重大意义；在交通运输方面，划分出交通事故高发路段以及易堵塞路段，采取交通管制措施，从而保障整个交通网络的畅通以及降低事故发生率。社区划分算法的研究早已成为复杂网络领域的研究热点之一，通过对复杂网络社区结构进行深入的发现和研究，可以更清楚、准确的认识真实网络，帮助人们更好的应对网络化生活。图1.1非重叠社区结构示例图图1.2重叠社区结构示意图1.2国内外研究现状自2002年Newman和Girvan提出网络的社区特征以来，关于社区划分的算法就层出不荆当前的社区划分算法依据社区中是否存在重叠节点，将社区划分为重叠社区和非重叠社区。重叠节点被定义为在进行社区划分时，该节点被同时划分到两个或多个社区中，不独立存在于单独的社区中。近年来，关于社区划分算法主要围绕非重叠社区和重叠社区展开，进行大量算法论证。1.2.1非重叠社区划分算法非重叠社区划分算法，是完成社区划分后的节点只属于一个社区。有关划分非重叠
西安科技大学全日制工程硕士学位论文16图3.1无向网络图3.2星型邻域网络对图3.2中两个星型邻域网络中所有节点的网络归属情况进行描述：111100111nX,YiiinX,YiiinX,YiiiaXYbXYcXY(3.1)在公式(3.1)中，0表示节点不属于这个星型邻域网络，1表示节点属于这个星型邻域网络;X,Ya表示属于星型邻域网络X且不属于星型邻域网络Y的节点总数，X,Yb表示属于星型邻域网络Y且不属于星型邻域网络X的节点总数；如果0X,Yc，则表示星型邻域网络X和星型邻域网络Y没有共同邻居节点。将图3.2星型邻域网络用图3.3星型邻域网络关系度量图来表示。图3.3星型邻域网络关系度量图图3.3中的星型邻域网络间的度量关系可描述为公式(3.2)和公式(3.3):HXIX,YHX|YHYIX,YHY|XHX,YHXHY|XHX,YHYHX|Y(3.2)
【参考文献】：
期刊论文
[1]基于Jaccard和LPA的社团划分算法[J]. 崔海涛,李玲娟. 南京邮电大学学报(自然科学版). 2019(06)
[2]基于拓扑结构的密度峰值重叠社区发现算法[J]. 封云飞,陈红梅. 计算机科学. 2019(10)
[3]A Link-Based Similarity for Improving Community Detection Based on Label Propagation Algorithm[J]. BERAHMAND Kamal,BOUYER Asgarali. Journal of Systems Science & Complexity. 2019(03)
[4]基于谱聚类的二分网络社区发现算法[J]. 张晓琴,安晓丹,曹付元. 计算机科学. 2019(04)
[5]结合概率矩阵的改进谱聚类社区发现算法[J]. 张书博,任淑霞,吴涛. 西安电子科技大学学报. 2019(03)
[6]基于邻居节点相异性的社团发现新算法[J]. 张思源,覃森,张智丰. 杭州电子科技大学学报(自然科学版). 2018(05)
[7]进化谱分算法检测动态网络社团结构[J]. 付立冬,马小科,聂靖靖. 西安电子科技大学学报. 2018(02)
[8]基于相似度指标的社团划分算法[J]. 丁明珠,马英红,李云. 计算机工程. 2019(02)
[9]基于共邻节点相似度的加权网络社区发现方法[J]. 刘苗苗,郭景峰,马晓阳,陈晶. 四川大学学报(自然科学版). 2018(01)
[10]一种新的基于局部相似度的社区发现算法[J]. 顾亦然,陈雨晴. 南京邮电大学学报(自然科学版). 2017(05)
本文编号：3488265
【文章来源】：西安科技大学陕西省
【文章页数】：60 页
【学位级别】：硕士
【部分图文】：
非重叠社区结构示例图
西安科技大学全日制工程硕士学位论文2话题讨论平台，识别出具有相似主题的热点讨论话题，通过发现用户集中讨论的话题来把握网络中的热点主题，把握话题的发展动向；针对淘宝、京东等购物平台，根据相似的消费喜好和消费水平的用户进行社区划分，能更加有效的针对特定的用户以及群体进行相应的广告定位投放，推荐相应类别的商品，提高平台的销售量；在传染性疾病以及病毒传播方面，根据病人接触关系网以及活动轨迹，查找密切接触者，可以在最短的时间内采取最有效的措施控制疾病的传播，对预防和治疗传染性疾病具有重大意义；在交通运输方面，划分出交通事故高发路段以及易堵塞路段，采取交通管制措施，从而保障整个交通网络的畅通以及降低事故发生率。社区划分算法的研究早已成为复杂网络领域的研究热点之一，通过对复杂网络社区结构进行深入的发现和研究，可以更清楚、准确的认识真实网络，帮助人们更好的应对网络化生活。图1.1非重叠社区结构示例图图1.2重叠社区结构示意图1.2国内外研究现状自2002年Newman和Girvan提出网络的社区特征以来，关于社区划分的算法就层出不荆当前的社区划分算法依据社区中是否存在重叠节点，将社区划分为重叠社区和非重叠社区。重叠节点被定义为在进行社区划分时，该节点被同时划分到两个或多个社区中，不独立存在于单独的社区中。近年来，关于社区划分算法主要围绕非重叠社区和重叠社区展开，进行大量算法论证。1.2.1非重叠社区划分算法非重叠社区划分算法，是完成社区划分后的节点只属于一个社区。有关划分非重叠
西安科技大学全日制工程硕士学位论文16图3.1无向网络图3.2星型邻域网络对图3.2中两个星型邻域网络中所有节点的网络归属情况进行描述：111100111nX,YiiinX,YiiinX,YiiiaXYbXYcXY(3.1)在公式(3.1)中，0表示节点不属于这个星型邻域网络，1表示节点属于这个星型邻域网络;X,Ya表示属于星型邻域网络X且不属于星型邻域网络Y的节点总数，X,Yb表示属于星型邻域网络Y且不属于星型邻域网络X的节点总数；如果0X,Yc，则表示星型邻域网络X和星型邻域网络Y没有共同邻居节点。将图3.2星型邻域网络用图3.3星型邻域网络关系度量图来表示。图3.3星型邻域网络关系度量图图3.3中的星型邻域网络间的度量关系可描述为公式(3.2)和公式(3.3):HXIX,YHX|YHYIX,YHY|XHX,YHXHY|XHX,YHYHX|Y(3.2)
【参考文献】：
期刊论文
[1]基于Jaccard和LPA的社团划分算法[J]. 崔海涛,李玲娟. 南京邮电大学学报(自然科学版). 2019(06)
[2]基于拓扑结构的密度峰值重叠社区发现算法[J]. 封云飞,陈红梅. 计算机科学. 2019(10)
[3]A Link-Based Similarity for Improving Community Detection Based on Label Propagation Algorithm[J]. BERAHMAND Kamal,BOUYER Asgarali. Journal of Systems Science & Complexity. 2019(03)
[4]基于谱聚类的二分网络社区发现算法[J]. 张晓琴,安晓丹,曹付元. 计算机科学. 2019(04)
[5]结合概率矩阵的改进谱聚类社区发现算法[J]. 张书博,任淑霞,吴涛. 西安电子科技大学学报. 2019(03)
[6]基于邻居节点相异性的社团发现新算法[J]. 张思源,覃森,张智丰. 杭州电子科技大学学报(自然科学版). 2018(05)
[7]进化谱分算法检测动态网络社团结构[J]. 付立冬,马小科,聂靖靖. 西安电子科技大学学报. 2018(02)
[8]基于相似度指标的社团划分算法[J]. 丁明珠,马英红,李云. 计算机工程. 2019(02)
[9]基于共邻节点相似度的加权网络社区发现方法[J]. 刘苗苗,郭景峰,马晓阳,陈晶. 四川大学学报(自然科学版). 2018(01)
[10]一种新的基于局部相似度的社区发现算法[J]. 顾亦然,陈雨晴. 南京邮电大学学报(自然科学版). 2017(05)
本文编号：3488265
本文链接：https://www.wllwen.com/kejilunwen/yysx/3488265.html
