基于R-C模型的多分区权值约简微博社区检测算法  

Microblog Community Detection Algorithm with Multi-partition Weight Reduction Based on R-C Model

作　　者：杨长春[1] 王巍巍[1] 叶施仁[1] 沈永梅[2] 

机构地区：[1]常州大学信息科学与工程学院,江苏常州213164 [2]常州大学怀德学院,江苏常州213164

出　　处：《计算机工程》2016年第11期43-49,56,共8页Computer Engineering

基　　金：国家自然科学基金(61272367);江苏省高校自然科学研究项目(14KJB520002)

摘　　要：传统社区检测算法直接引入第三方算法会降低计算效率。为此,基于R-C模型,设计多分区权值约简有限区间限定算法进行微博社区检测。研究微博社区发现R-C模型,分析参数加权约简曲线性质,借鉴凸优化问题解决方案,提出一种适用于多数参数值的最优分区求解算法。通过分区断点顺序搜索将参数范围限定在一组有限区间内,其中每个参数对应唯一的最优加权约简值,并且实现分区参数的同步优化,从而解决单一分区不利于更多信息均衡的问题。从新浪微博中获取数据集进行实验,结果表明,与基于主题与链接关系或基于标签传播的微博社区检测算法相比,该算法可更准确地检测用户微博社区。The traditional community detection algorithm directly introduces the third party algorithm,which reduces computation efficiency.Aiming at this problem,this paper proposes a microblog community detection method based on the finite interval limitation algorithm with multi-partition weight reduction.Firstly,the R-C model of the microblog community is studied and the properties of the weighted reduction curves of the parameters are analyzed.Then the optimal partition algorithm is proposed for most parameter values based on solution of convex optimization problem.Secondly,the parameter range can be defined in a set of finite interval by partitioned sequential search of breakpoints,and the synchronization optimization of partition parameters is implemented,which sloves the multi-information equilibrium problem of single partition.Finally,the data set obtained from Sina microblog is used for experiments,and results show that the proposed algorithm is more effective for user’s microblog community detection,compared with microblog detection algorithm based on relationship of theme and link or label propagation.

关 键 词：微博社区 多分区 顺序搜索 权值约简 凸优化 有限区间 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]