基于梯度的重叠式层次社区检测
作者:

Gradient-Based Overlapping Hierarchical Community Detection
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [17]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    社区检测(community detection)任务一直是数据挖掘领域的一个研究热点, 近年来, 深度学习和图链接数据呈现出多样化和复杂化的发展趋势, 层次(Hierarchical)社区检测逐渐成为研究的焦点. 层次社区检测任务的目标是, 在将同质图中相似的节点聚集到社区中的同时, 学习社区之间的层次结构关系, 以更好的理解图数据结构. 社区间层次关系的引入给社区检测算法带来了更复杂的建模挑战. 针对该任务, 已经有一些有效的启发式的方法被提出, 但是受限于社区分布形态的简单假设和离散的优化学习方式, 它们无法描述更复杂的图链路数据, 也无法和其它有效的连续优化算法组合获得更好的结果. 为了解决这个问题, 本文首次尝试建模复杂的重叠式(overlapping)层次社区结构, 提出简洁的节点嵌入和社区检测双任务优化模型, 通过梯度更新的方式来灵活地探索节点和重叠式层次社区的隶属关系. 在学习过程中, 我们可以分别获得节点和社区的嵌入表示, 以应用于丰富的下游任务.

    Abstract:

    Community detection task is a hotspot in data mining. In recent years, deep learning and graph data have been increasingly diverse and complex, and the task of hierarchical community detection has gradually become a focus of research. The goal of this task is to learn the hierarchical relationship between communities while gathering similar nodes in homogeneous graphs to better understand the graph data structure. The introduction of this relationship poses a higher modeling challenge to community detection algorithms. For this task, some effective heuristic methods have been proposed. However, limited by the simple assumptions of community distribution and discrete optimization learning methods, these methods cannot describe more complex graph data, nor can they be combined with other effective continuous optimization algorithms. To solve this issue, we first attempt to model a complex overlapping hierarchical community structure and propose a simple dual-task optimization model of node embedding and community detection. The relationship of nodes and overlapping hierarchical communities can be flexibly explored through gradient updates. In the learning process, we can also obtain the embedding representations of nodes and communities to apply to rich downstream tasks.

    参考文献
    [1] Sun FY, Qu M, Hoffmann J, et al. vGraph:A generative model for joint community detection and node representation learning. 33rd Conference on Neural Information Processing Systems. Vancouver, BC, Canada. 2019. 514-524.
    [2] Cavallari S, Zheng VW, Cai HY, et al. Learning community embedding with community detection and node embedding on graphs. Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. Singapore. 2017. 377-386.
    [3] Xie JR, Szymanski BK, Liu XM. SLPA:Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. 2011 IEEE 11th International Conference on Data Mining Workshops. Vancouver, BC, Canada. 2011. 344-349.
    [4] Xie JR, Kelley S, Szymanski BK. Overlapping community detection in networks:The state-of-the-art and comparative study. ACM Computing Surveys, 2013, 45(4):43
    [5] Liu FZ, Xue S, Wu J, et al. Deep learning for community detection:Progress, challenges and opportunities. arXiv:2005.08225, 2020.
    [6] Faust K. Using correspondence analysis for joint displays of affiliation networks. In:Carrington PJ, Scott J, Wasserman S, eds. Models and Methods in Social Network Analysis. Oxford, UK:Cambridge University Press, 2005. 117-147.
    [7] Wang X, Cui P, Wang J, et al. Community preserving network embedding. Thirty-First AAAI Conference on Artificial Intelligence. San Francisco, CA, USA. 2017. 203-209.
    [8] Clauset A, Moore C, Newman MEJ. Structural inference of hierarchies in networks. ICML Workshop on Statistical Network Analysis. Pittsburgh, PA, USA. 2007. 1-13.
    [9] Bhowmick AK, Meneni K, Danisch M, et al. LouvainNE:Hierarchical louvain method for high quality and scalable network embedding. Proceedings of the 13th International Conference on Web Search and Data Mining. Houston, TX, USA. 2020. 43-51.
    [10] Škrlj B, Kralj J, Lavrač N. Embedding-based Silhouette community detection. arXiv:1908.02556, 2019.
    [11] Blondel VD, Guillaume JL, Lambiotte R, et al. Fast unfolding of communities in large networks. Journal of Statistical Mechanics:Theory and Experiment, 2008, 2008(10):P10008.[doi:10.1088/1742-5468/2008/10/P10008
    [12] Šíma J, Schaeffer SE. On the NP-completeness of some graph cluster measures. 32nd Conference on Current Trends in Theory and Practice of Computer Science. Merin, Czech Republic. 2006. 530-537.
    [13] Perozzi B, Al-Rfou R, Skiena S. DeepWalk:Online learning of social representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. East Lansing, MI, USA. 2014. 701-710.
    [14] Tang J, Qu M, Wang MZ, et al. LINE:Large-scale information network embedding. Proceedings of the 24th International Conference on World Wide Web. Florence, Italy. 2015. 1067-1077.
    [15] Tang J, Zhang J, Yao LM, et al. Arnetminer:Extraction and mining of academic social networks. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. East Lansing, MI, USA. 2008. 990-998.
    [16] Kingma D, Ba J. Adam:A method for stochastic optimization. arXiv:1412.6980, 2014.
    [17] van der Maaten L, Hinton G. Visualizing data using t-SNE. Journal of Machine Learning Research, 2008, 9:2579-2605
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

王寒蕊,丁岱宗,张谧.基于梯度的重叠式层次社区检测.计算机系统应用,2021,30(8):207-212

复制
分享
文章指标
  • 点击次数:901
  • 下载次数: 1669
  • HTML阅读次数: 1496
  • 引用次数: 0
历史
  • 收稿日期:2020-11-11
  • 最后修改日期:2020-12-12
  • 在线发布日期: 2021-08-03
文章二维码
您是第12825878位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号