积分商城

最新搜索： 解压缩软件 UCD3138 iar Smith 购买积分 注册表
您现在的位置是：首页 > 技术资料 > 基于加权内容-结构网络和随机游走的社团划分算法
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

基于加权内容-结构网络和随机游走的社团划分算法

更新时间：2019-12-24 08:09:27 大小：1M 上传用户：zhiyao6查看TA发布的资源 标签：社团划分算法 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

针对传统模块优化社团划分算法仅能利用网络的结构信息,而无法利用同样丰富的内容信息,导致划分精度较低的问题,提出一种结合内容属性并通过给连边加权来全面优化网络拓扑结构的社团划分算法CCSRW(Classification with Content-Structure and Random Walk).设计利用随机游走理论计算结构节点与内容节点间的相似性关系矩阵,并将结构节点映射到内容属性空间上,最终把社团划分问题转化为多维无监督聚类问题.通过在真实数据集上进行的全面实验分析,展示了相比于传统社团划分算法,本文的算法能更准确的描述网络结构,显著提高划分性能,并有效解决小社团不敏感问题,更适用于大规模复杂信息网络的社团划分.


部分文件列表

文件名 大小
基于加权内容-结构网络和随机游走的社团划分算法.pdf 1M

【关注B站账户领20积分】

部分页面预览

（完整内容请下载后查看）
9
Vol． 45 No． 9  
Sep． 2017  
第
期
电
子
学
报
2017  
9
ACTA ELECTRONICA SINICA  
年
月
-
基于加权内容 结构网络和  
随机游走的社团划分算法  
1
2
3
4
，
，
，
牛新征 牛嘉郡 苏大壮 佘 堃  
( 1．  
，
611731; 2．  
，
611731;  
电子科技大学计算机科学与工程学院 四川成都  
电子科技大学计算机科学与工程学院 四川成都  
， 611731)  
电子科技大学信息与软件工程学院 四川成都  
3．  
，
200050; 4．  
大众点评网 上海  
:
， ，  
针对传统模块优化社团划分算法仅能利用网络的结构信息 而无法利用同样丰富的内容信息 导致划  
摘
要
，
CCSRW  
分精度较低的问题 提出一种结合内容属性并通过给连边加权来全面优化网络拓扑结构的社团划分算法  
( Classification with Content-Structure and Random Walk) ．  
设计利用随机游走理论计算结构节点与内容节点间的相似性  
，
，
．
关系矩阵 并将结构节点映射到内容属性空间上 最终把社团划分问题转化为多维无监督聚类问题 通过在真实数据  
，
，
，
集上进行的全面实验分析 展示了相比于传统社团划分算法 本文的算法能更准确的描述网络结构 显著提高划分性  
， ，  
能 并有效解决小社团不敏感问题 更适用于大规模复杂信息网络的社团划分  
．
:
;
-
;
;
关键词  
中图分类号  
URL: http: / /www． ejournal． org． cn  
社团划分 加权内容 结构网络 随机游走 模块优化  
:
TP391  
:
A
:
文章编号  
0372-2112 ( 2017) 09-2135- 08  
文献标识码  
DOI: 10． 3969 /j． issn． 0372-2112． 2017． 09． 012  
电子学报  
Community Detection Based on Weighted  
Content-Structural Network and Random Walks  
1
2
3
4
NIU Xin-zheng ，NIU Jia-jun ，SU Da-zhuang ，SHE Kun  
( 1． School of Computer Science and Engineering，University of Electronic Science and Technology of China，Chengdu，Sichuan 611731，China;  
2． School of Computer Science and Engineering，University of Electronic Science and Technology of China，Chengdu，Sichuan 611731，China;  
3． Dianping，Shanghai 200050，China;  
4． School of Software Engineering，University of Electronic Science and Technology of China，Chengdu，Sichuan 611731，China)  
Abstract: For the traditional module optimization community partition algorithms can only use the structure informa-  
tion of network，and cannot use the rich content information，leading to low precision problem． A community partition algo-  
rithm that is combined with the content attribute and empowers the edge to fully optimize the topology of the network，called  
CCSRW ( Classification with Content-Structure and Random Walk) is proposed． We use random walk theory to calculate the  
similarity relationship matrix between structure nodes and content nodes，and map structure nodes onto the content attribute  
space，finally divide the community partition problems into multidimensional unsupervised clustering problems． Comprehen-  
sive experimental analysis on the real data sets shows that compared to the traditional community partition algorithms，this al-  
gorithm can describe the network structure more accurately，improve the classification performance significantly，and solve  
the problem that is not sensitive to small community effectively，and it is more suitable for the large-scale complex informa-  
tion network community partition．  
Key words: community detection; weighted content-structure network; random walking; modularity optimization．  
: 2016-04-11 ;  
: 2016-07-31;  
:
收稿日期  
修回日期  
责任编辑 梅志强  
国家自然科学基金  
( No． 2015GZ0102) ;  
:
( No． 2013BAH33F02) ;  
( No． 61300192) ;  
( No．  
基金项目 国家科技支撑计划  
ZYGX2014J052) ; 2015  
中央高校基本科研业务费电子科技大学项目  
四川省自贡市公安局 基于智能视频分析的交通流量监控与事故预测系统的研  
( No． 2015-RK00-00247-ZF)  
成都市科学技术局软科学研究项目  
-
年省科技厅支持计划  
( No． 2015SCYYCX06) ;  
;
究与实现 四川省公安厅科研项目  
2136  
2017  
电
子
学
报
年
．
容节点表征结构节点的社团划分新思路  
( 3)  
1
引言  
利用网络中节点的相对关系来计算其绝对属  
，
在关于网络拓扑结构的科学研究中 为进一步理  
，
，
性 通过多个属性的组合将其映射到多维坐标空间中  
，
解网络的构成和演变 社团划分问题得到越来越多的  
，
并用较成熟的聚类技术解决社团划分问题 克服了模  
关注［1］ 社团划分是根据网络的内部功能属性 将其中  
．
，
，
块化算法低准确度的同时 避免了非模块化方法高复  
，
具有相似特征的节点划分到同一社团 使得社团内部  
．
杂度的缺陷  
，
．
节点间联系紧密 外部节点间联系稀疏  
( 4)  
，
从多个角度不同层面构建实验 与同类型的多  
大部分社团划分算法仅根据结构是否紧凑划分社  
，
个算法进行对比 验证了本文社团划分的准确性和处  
团［2］ 随着互联网的发展 人们积累了网络文档 博客  
．
，
、
．
理大规模数据的有效性 同时设计实验获得令聚类效  
，
等形式的大量信息 从而产生了很多与传统网络大不  
，
果最优的转移步数 并用主成分分析得到步数对聚类  
，
，
相同的 新兴的社交网络和信息网络 具有更丰富的内  
．
的重要影响  
． ，  
容信息 在对具有内容属性的网络进行划分时 节点的  
2
算法原理  
，
内容相似 意味着它们所代表的个体具有相似的社会  
，
行为 即使不属于同一个密集区域也应被划分到同个  
2． 1  
-
加权内容 结构网络模型  
． ，  
社团 因此不能只考虑单一的结构信息 而应该同时根  
本文提出一种能够有效融合内容和结构信息的加  
，
据结构和内容双重属性进行社团划分 才能保证划分  
．
权网络模型  
．
1
- : 1 ，  
加权内容 结构网络模型 如图 所示 将  
结果的全面性和有效性  
定义  
， ，  
网络划分成一个具有二分类的偶图 包含两类节点 一  
目前社团划分的研究可分为模块优化和非模块优  
．
化两大类 非模块优化方法未能将社团划分问题从  
NP  
， ，  
是结构节点 该部分节点由原始网络节点组成 且有边  
，
，
N;  
相连 设为 二是内容节点 由所有节点的内容属性去  
，
难题中简化出来 因此模块优化算法是当前最流行的  
社团划分算法［4］  
利用社团结构的模块化系数作为判断标准 并认为社  
． Clauset  
和
教授在文献  
中
． Newman Girvan  
［5］  
，
重后得到 设为  
M．  
，
结构节点之间的连边 结构节点和内  
，
，
容节点间的连边都赋有权值 用来区分节点间相互作  
［6］在  
用的强弱程度  
．
团内部边密度较高而社团之间边密度较低  
Newman  
、
的研究基础上提出使用最大堆 模块度增量矩  
，
通过这样的部署 能真实反映现实特征的同时又  
，
．
阵等数据结构存储数据 有效缩减了时间复杂度 但其  
摒弃了在社团划分过程中内容节点间可能存在的毫无  
，
方法过分偏重大规模社团 导致在实际应用中容易陷  
．
意义的间接结构信息  
． Schuetz  
［7］  
在文献 中对  
Clauset  
2
W
入最坏的时间复杂度  
定义  
结构节点间连边的权重  
结构节点之  
s
．
，
，
的算法做了进一步改进 每次同时融合多个社团 有效  
间交互的频次  
． ［8］  
改善了大规模社团的情况 文献 的算法基于贪心策  
3
W
定义  
结构节点与内容节点间连边的权重  
c
．
，
略 使初始社团的构建始于一个具有最高强度的节点  
，
结构节点中出现该内容属性的频次  
-
我们将构建加权内容 结构网络分成三步  
:
．
然后通过不断的添加节点来扩展社团 但以上基于模  
( 1)  
n
n
，
在原始网络中相连 则在  
，
块优化的方法并不能准确评价社团结构 尤其对小社  
若结构节点  
和
i
j
-
，
．
加权内容 结构网络中 两节点依然相连 根据两节点间  
，
团不敏感 即算法无法判断一个子网应该是一个大社  
，
．
交互的频次 设置连边的权重 结构节点之间的边集合  
．
团还是多个小社团组合而成 并且忽视了连接社团之  
，
W ．  
sij  
，
间的边所包含的信息 只根据网络节点间的连接关系  
用实线表示 权重为  
( 2)  
n
p，  
-
，
．
判断紧密性 导致其在实际应用中效果并不理想 从信  
若结构节点 存在内容属性 则在内容 结构  
i
，
n
m
，
息论的角度来看 以模块方法来表示的复杂结构所含  
网络中 结构节点 与表示该内容属性的内容节点  
i
p
．
p
n
，
．
相连 根据内容属性 在节点 中出现的次数 设置内  
有的信息熵并不足以准确判断网络结构  
i
m
n
．
，
由于模块优化算法有着以上缺陷 本文提出一种  
容节点  
点和内容节点的边为虚线 权重为  
( 3)  
和结构节点 之间连边的权重 连接结构节  
p
i
，
W ．  
cip  
，
:
社团划分新思路 主要有以下四个方面的贡献  
( 1)  
，
由于不同连边的权重差异较大 为了方便处  
-
采用改进的加权内容 结构网络模型有效融合  
， ．  
理 需要对权重进行数据规范化处理 本文采用线性比  
，
内容和结构信息 能真实体现节点间关系强弱的同时  
，
，
例变换法对数据进行标准化 设原值为  
W ，  
标准化后的  
．
避免了建立复杂的统一模型  
( 2)  
ij  
a ， :  
则
值为  
- ，  
基于加权内容 结构网络模型 改进传统的随  
ij  
W
，
机游走算法使其充分利用网络的边权信息 更精确地  
ij  
a =  
ij  
( 1  
i
≤ ≤  
n，1  
j
≤ ≤  
m)  
( 1)  
maxW  
，
计算节点间的相似度 创新性地提出了以网络中的内  
ij  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号