摘要： 传统社区检测算法直接引入第三方算法会降低计算效率。为此,基于R-C模型,设计多分区权值约简有限区间限定算法进行微博社区检测。研究微博社区发现R-C模型,分析参数加权约简曲线性质,借鉴凸优化问题解决方案,提出一种适用于多数参数值的最优分区求解算法。通过分区断点顺序搜索将参数范围限定在一组有限区间内,其中每个参数对应唯一的最优加权约简值,并且实现分区参数的同步优化,从而解决单一分区不利于更多信息均衡的问题。从新浪微博中获取数据集进行实验,结果表明,与基于主题与链接关系或基于标签传播的微博社区检测算法相比,该算法可更准确地检测用户微博社区。

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

Abstract: 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.

Key words: microblog community, multi-partition, sequential search, weight reduction, convex optimization, finite interval

中图分类号: 

• TP311