多维图结构聚类的社交关系挖掘算法
作者:
作者单位:

作者简介:

李振军(1979-),男,广西柳州人,博士,工程师,主要研究领域为数据挖掘,深度学习;毛睿(1975-),男,博士,教授,CCF高级会员,主要研究领域为数据挖掘,数据库,统计方法,机器学习,计算生物;代强强(1992-),男,硕士,主要研究领域为社交数据挖掘,图算法;乔少杰(1981-),男,博士,教授,CCF高级会员,主要研究领域为轨迹数据挖掘,机器学习;李荣华(1985-),男,博士,讲师,主要研究领域为图数据挖掘,社交网络分析.

通讯作者:

代强强,E-mail:1134133685@qq.com

中图分类号:

TP311

基金项目:

国家自然科学基金(61402292,61772091);国家自然科学基金广东省联合基金(U1301252);教育部人文社会科学研究规划基金(15YJAZH058)


Social Relationship Mining Algorithm by Multi-Dimensional Graph Structural Clustering
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61402292, 61772091);National Natural Science Foundation of China Guangdong Joint Fund Project (U1301252);Planning Foundation for Humanities and Social Sciences of Ministry of Education of China (15YJAZH058)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    社交关系的数据挖掘一直是大图数据研究领域中的热门问题.图聚类算法如SCAN (structural clustering algorithm for network)虽然可以迅速地从海量图数据中获得关系紧密的社区结构,但这类社区往往只表示了社交对象的聚集,无法反馈对象间的真实社交关系,如家庭成员、同事、同学等.要获取对象间真实的社交关系,需要更多维度地挖掘现实中社交对象间复杂的交互关系.对象间的交互维度很多,例如通话、见面、微信、电子邮件等,而传统SCAN等聚类算法仅能够挖掘单维度的交互数据.在研究社交对象间的多维社交关系图数据与传统图结构聚类算法的基础上,提出了一种有效的子空间聚类算法SCA (subspace cluster algorithm),对多维度下子空间的图结构聚类进行研究,目的是探索如何通过图数据挖掘发现对象间真实的社交关系.SCA算法遵循自底向上的原则,能够发现社交图数据中所有子空间的聚类集.为提升SCA的运行速度,利用其子空间聚类的单调性进行了性能优化,进而提出了剪枝算法SCA+.最后进行了大规模的性能测试实验以及真实数据的案例研究,其结果验证了算法的效率和效用.

    Abstract:

    Social relationship mining is a hot topic in the area of massive graph analysis. Graph clustering algorithms such as SCAN (structural clustering algorithm for networks) can quickly discover the communities from the massive graph data. However, relationships in these communities fail to reflect the ‘real’ social information such as family, colleagues and classmates. In reality, social data is very complex, and there are many types of interaction among each individual, such as calling, meeting, chatting in WeChat, and sending emails. However, traditional SCAN algorithm can only handle single dimensional graph data. Based on the study of multidimensional social graph data and traditional clustering algorithms, this paper first proposes an efficient subspace clustering algorithm named SCA by mining multi-dimensional clusters in subspaces as a mean to explore real social relationships. SCA follows the bottom-up principle and can discover the set of clusters from the social graph data in all dimensions. To improve the efficiency of SCA, the paper also develops a pruning algorithm called SCA+ based on the monotonicity of subspace clustering. Extensive experiments on several real-world multi-dimensional graph data demonstrate the efficiency and effectiveness of the proposed algorithms.

    参考文献
    相似文献
    引证文献
引用本文

李振军,代强强,李荣华,毛睿,乔少杰.多维图结构聚类的社交关系挖掘算法.软件学报,2018,29(3):839-852

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-08-02
  • 最后修改日期:2017-09-05
  • 录用日期:
  • 在线发布日期: 2017-12-05
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号