电子学报 ›› 2017, Vol. 45 ›› Issue (9): 2135-2142.DOI: 10.3969/j.issn.0372-2112.2017.09.012

• 学术论文 • 上一篇    下一篇

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

牛新征1, 牛嘉郡2, 苏大壮3, 佘堃4   

  1. 1. 电子科技大学计算机科学与工程学院, 四川成都 611731;
    2. 电子科技大学计算机科学与工程学院, 四川成都 611731;
    3. 大众点评网, 上海 200050;
    4. 电子科技大学信息与软件工程学院, 四川成都 611731
  • 收稿日期:2016-04-11 修回日期:2016-07-31 出版日期:2017-09-25
    • 作者简介:
    • 牛新征,男,1978年生于贵州贵阳,电子科技大学计算机科学与工程学院副教授.研究方向为数据挖掘和网络计算.E-mail:xinzhengniu@uestc.edu.cn;牛嘉郡,女,1994年生于山西忻州,电子科技大学计算机科学与工程学院研究生在读,研究方向为数据库与数据挖掘.E-mail:janetniu@126.com;苏大壮,男,1989年生于辽宁阜新,大众点评网大数据平台工程师,研究方向为数据挖掘和网络计算.E-mail:905533181@qq.com;佘堃,男,1968年生于湖北武汉,电子科技大学信息与软件工程学院教授,主要研究领域为网络计算、人工智能.E-mail:kunshe@126.com
    • 基金资助:
    • 国家科技支撑计划 (No.2013BAH33F02); 国家自然科学基金 (No.61300192); 中央高校基本科研业务费电子科技大学项目 (No.ZYGX2014J052); 2015年省科技厅支持计划 (No.2015GZ0102); 四川省自贡市公安局-基于智能视频分析的交通流量监控与事故预测系统的研究与实现; 四川省公安厅科研项目 (No.2015SCYYCX06); 成都市科学技术局软科学研究项目 (No.2015-RK00-00247-ZF)

Community Detection Based on Weighted Content-Structural Network and Random Walks

NIU Xin-zheng1, NIU Jia-jun2, SU Da-zhuang3, SHE Kun4   

  1. 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
  • Received:2016-04-11 Revised:2016-07-31 Online:2017-09-25 Published:2017-09-25
    • Supported by:
    • National Key Technology Research and Development Program of the Ministry of Science and Technology (No.2013BAH33F02); National Natural Science Foundation of China (No.61300192); Project of University of Electronic Science and Technology of China of Fundamental Research Funds for the Central Universities (No.ZYGX2014J052); Supported by Provincial Science and Technology Department in 2015 (No.2015GZ0102); Research and Implementation of Traffic Flow Monitoring and Accident Prediction System Based on Intelligent Video Analysis of Public Security Bureau of Zigong,  Sichuan Province; Scientific Research Project of Sichuan Public Security Department (No.2015SCYYCX06); Soft Science Research Project for Chengdu Science and Technology Bureau (No.2015-RK00-00247-ZF)

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

关键词: 社团划分, 加权内容-结构网络, 随机游走, 模块优化

Abstract: For the traditional module optimization community partition algorithms can only use the structure information of network,and cannot use the rich content information,leading to low precision problem.A community partition algorithm 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.Comprehensive experimental analysis on the real data sets shows that compared to the traditional community partition algorithms,this algorithm 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 information network community partition.

Key words: community detection, weighted content-structure network, random walking, modularity optimization

中图分类号: