Please wait a minute...
Advanced Search
数据分析与知识发现  2020, Vol. 4 Issue (4): 119-128     https://doi.org/10.11925/infotech.2096-3467.2019.0674
  研究论文 本期目录 | 过刊浏览 | 高级检索 |
基于改进的Vicsek模型的社会网络同步聚类算法*
杨旭1,钱晓东2()
1 兰州交通大学电子与信息工程学院 兰州 730070
2 兰州交通大学经济与管理学院 兰州 730070
Synchronous Clustering Algorithm for Social Networks Based on Improved Vicsek Model
Yang Xu1,Qian Xiaodong2()
1 School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China
2 School of Economics and Management, Lanzhou Jiaotong University, Lanzhou 730070, China
全文: PDF (849 KB)   HTML ( 4
输出: BibTeX | EndNote (RIS)      
摘要 

【目的】 设计基于改进的Vicsek模型的同步聚类算法,研究社会网络的同步演化过程与簇结构。【方法】 针对原始Vicsek模型的个体运动速率恒定问题,引入速率自我调节规则调整个体演化速率;针对原始Vicsek模型的个体重要性相同问题,引入个体重要性控制个体演化方向。【结果】 利用金融网络数据集验证本文算法,F1-Score高于Sync算法和基于Vicsek模型的聚类算法。【局限】 算法时间复杂度与数据集规模成正相关关系,使得算法时间复杂度较高。【结论】 基于改进的Vicsek模型的同步聚类算法能较好地刻画复杂社会网络的演化与同步过程,准确发现社会网络中的簇结构。

服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
杨旭
钱晓东
关键词 Vicsek模型同步聚类    
Abstract

[Objective] The paper designs an algorithm based on the improved Vicsek model, aiming to study the synchronous evolution process and cluster structure of social networks. [Methods] First, we introduced a rate self-regulation rule to adjust the individual evolution rate of the original Vicsek model. Then, we used individual importance to control the direction of individual evolution of the Vicsek model. [Results] We examined our new algorithm with datasets of financial networks. The F1-Score for clustering results was higher than the Sync algorithm and clustering algorithm based on the original Vicsek model. [Limitations] The clustering time was very complex with large datasets. [Conclusions] The proposed algorithm could effectively describe the evolution and synchronization of complex social networks, and then accurately discover their cluster structures.

Key wordsVicsek Model    Synchronize    Clustering
收稿日期: 2019-06-11      出版日期: 2020-06-01
ZTFLH:  TP311.1  
基金资助:*本文系国家自然科学基金项目“基于复杂网络的商务大数据聚类与关联应用研究”的研究成果之一(71461017)
通讯作者: 钱晓东     E-mail: qianxd@mail.lzjtu.cn
引用本文:   
杨旭,钱晓东. 基于改进的Vicsek模型的社会网络同步聚类算法*[J]. 数据分析与知识发现, 2020, 4(4): 119-128.
Yang Xu,Qian Xiaodong. Synchronous Clustering Algorithm for Social Networks Based on Improved Vicsek Model. Data Analysis and Knowledge Discovery, 2020, 4(4): 119-128.
链接本文:  
https://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/10.11925/infotech.2096-3467.2019.0674      或      https://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/Y2020/V4/I4/119
Fig.1  Vicsek模型收敛时间
Fig.2  变速率Vicsek模型收敛时间
Fig.3  “风筝网络”拓扑结构
ID Di+ Di- Zi
1 0.531 7 0.000 0 0.000 0
2 0.234 3 0.340 2 0.565 0
3 0.046 3 0.522 5 0.918 5
4 0.202 6 0.346 2 0.630 8
5 0.202 6 0.346 2 0.630 8
6 0.508 0 0.090 4 0.151 1
7 0.368 8 0.217 3 0.370 7
8 0.508 0 0.090 4 0.151 1
9 0.473 5 0.126 2 0.210 4
10 0.473 5 0.126 2 0.210 4
Table 1  “风筝网络”多属性决策评价结果
无权重 1 2 3 4 5 6 7 8 9 10
t=0 0 0 0 1/4 1/4 1/2 1/2 1/2 3/4 3/4
t=1 0 0 13/100 2/5 21/50 50/27 11/20 11/20 3/5 57/100
t=5 11/100 21/100 19/50 47/100 47/100 49/100 49/100 49/100 49/100 49/100
t=10 31/100 7/20 21/50 23/50 23/50 47/100 23/50 23/50 23/50 23/50
t=13 9/25 39/100 43/100 9/20 9/20 23/50 23/50 23/50 23/50 23/50
t=20 21/50 43/100 11/25 9/20 9/20 9/20 9/20 9/20 9/20 9/20
Zi为权重 1 2 3 4 5 6 7 8 9 10
t=0 0 0 0 1/4 1/4 1/2 1/2 1/2 3/4 3/4
t=1 0 0 9/50 41/100 11/25 27/50 27/50 27/50 59/100 28/50
t=5 13/50 39/100 39/100 51/100 51/100 13/25 13/25 13/25 13/25 13/25
t=10 49/100 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2
t=13 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2
t=20 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2
Table 2  无权重和以贴近度为权重Vicsek模型的收敛速度(π省略
证券市场的股票分类 本文算法 基于Vicsek模型的同步聚类算法 SynC算法
Recall Precision F1 Recall Precision F1 Recall Precision F1
公用事业 0.732 0.923 0.816 0.737 0.854 0.791 0.737 0.823 0.778
基础材料 0.500 0.745 0.598 0.500 0.724 0.592 0.500 0.722 0.590
技术 0.690 0.677 0.691 0.699 0.662 0.680 0.697 0.653 0.674
工业品 0.450 0.468 0.477 0.480 0.462 0.471 0.480 0.462 0.471
消费品 0.324 0.351 0.337 0.244 0.455 0.318 0.244 0.413 0.306
服务业 0.463 0.447 0.459 0.500 0.417 0.455 0.494 0.411 0.448
金融业 0.730 0.481 0.580 0.707 0.402 0.513 0.701 0.400 0.509
卫生保健 0.522 0.187 0.275 0.541 0.166 0.254 0.522 0.166 0.251
综合企业 0.286 0.101 0.286 0.286 0.091 0.138 0.147 0.091 0.120
Table 3  三种聚类算法结果对比
Fig.4  聚类结果随k值的变化
[1] Böhm C, Plant C, Shao J, et al. Clustering by Synchronization[C]// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.New York:ACM, 2010: 583-592.
[2] Shao J, Plant C, Yang Q, et al. Detection of Arbitrarily Oriented Synchronized Clusters in High-Dimensional Data[C]// Proceedings of the IEEE 11th International Conference on Data Mining, Vancouver, BC, Canada.Piscataway:IEEE, 2011: 607-616.
[3] 应文豪, 许敏, 王士同 , 等. 在大规模数据集上进行快速自适应同步聚类[J]. 计算机研究与发展, 2014,51(4):707-720.
[3] ( Ying Wenhao, Xu Min, Wang Shitong , et al. Fast Adaptive Clustering by Synchronization on Large Scale Datasets[J]. Journal of Computer Research and Development, 2014,51(4):707-720.)
[4] 乔颖, 王士同 . 快速大样本同步聚类[J]. 计算机工程与应用, 2016,52(23):159-166.
[4] ( Qiao Ying, Wang Shitong . Fast Clustering by Synchronization on Large Sample[J]. Computer Engineering and Applications, 2016,52(23):159-166.)
[5] 黄健斌, 白杨, 康剑梅 , 等. 一种基于同步动力学模型的网络社团发现方法[J]. 计算机研究与发展, 2012,49(10):2198-2207.
[5] ( Huang Jianbin, Bai Yang, Kang Jianmei , et al. A Network Community Detection Method Based on Dynamic Model of Synchronization[J]. Journal of Computer Research and Development, 2012,49(10):2198-2207.)
[6] 董学文, 杨超, 盛立杰 , 等. ESYN:基于动态模型的高效同步聚类算法[J]. 通信学报, 2014,35(Z2):86-93.
[6] ( Dong Xuewen, Yang Chao, Sheng Lijie , et al. ESYN: Efficient Synchronization Clustering Algorithm Based on Dynamic Synchronization Model[J]. Journal on Communications, 2014,35(S2):86-93.)
[7] 黄健斌, 康剑梅, 齐俊杰 , 等. 一种基于同步动力学模型的层次聚类方法[J]. 中国科学:信息科学, 2013,43(5):599-610.
[7] ( Huang Jianbin, Kang Jianmei, Qi Junjie , et al. A Hierarchical Clustering Method Based on a Dynamic Synchronization Model[J]. Scientia Sinica: Informationis, 2013,43(5):599-610.)
[8] 麻景豪, 蔡世民 . 基于同步理论的股票网络社团识别研究[J]. 复杂系统与复杂性科学, 2014,11(4):48-53.
[8] ( Ma Jinghao, Cai Shimin . Study on Community Identification of Stock Network Based on Synchronization Theory[J]. Complex System and Complexity Science, 2014,11(4):48-53.)
[9] Ying W, Chung F L, Wang S . Scaling Up Synchronization-Inspired Partitioning Clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2013,26(8):2045-2057.
[10] Shao J, He X, Böhm C , et al. Synchronization-Inspired Partitioning and Hierarchical Clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2013,25(4):893-905.
[11] Chen L, Zhang J, Cai L , et al. Parallel Synchronization-Inspired Partitioning Clustering[J]. Journal of Computational and Theoretical Nanoscience, 2016,13(11):8709-8729.
[12] Chen X . An Effective Synchronization Clustering Algorithm[J]. Applied Intelligence, 2016,46(1):135-157.
[13] Chen X . Fast Synchronization Clustering Algorithms Based on Spatial Index Structures[J]. Expert Systems with Applications, 2018,94:276-290.
[14] Vicsek T, Czirok A, Ben-Jacob E , et al. Novel Type of Phase Transition in a System of Self-Driven Particles[J]. Physical Review Letters, 1995,75(6):1226-1229.
[15] Gregoire G, Chate H . Onset of Collective and Cohesive Motion[J]. Physical Review Letters, 2004,92(2):025702.
[16] Chen X . Clustering Based on a Near Neighbor Graph and a Grid Cell Graph[J]. Journal of Intelligent Information Systems, 2013,40(3):529-554.
[17] 于会, 刘尊, 李勇军 . 基于多属性决策的复杂网络节点重要性综合评价方法[J]. 物理学报, 2013,62(2):020204.
[17] ( Yu Hui, Liu Zun, Li Yongjun . Key Nodes in Complex Networks Identified by Multi-Attribute Decision-Making Method[J]. Acta Physica Sinica, 2013,62(2):020204.)
[18] 朱茵, 孟志勇, 阚叔愚 . 用层次分析法计算权重[J]. 北京交通大学学报, 1999,23(5):119-122.
[18] ( Zhu Yin, Meng Zhiyong, Kan Shuyu . Determination of Weight Value by AHP[J]. Journal of Northern Jiaotong University, 1999,23(5):119-122.)
[19] Tan P N, Steinbach M, Kumar V. 数据挖掘导论[M]. 范明, 范宏建译. 北京: 人民邮电出版社, 2011.
[19] ( Tan P N, Steinbach M, Kumar V. Introduction to Data Mining[M]. Translated by Fan Ming, Fan Hongjian. Beijing: Posts&Telecom Press, 2011.)
[20] Cai S M, Zhou T B, Zhou T , et al. Hierarchical Organization and Disassortative Mixing of Correlation-Based Weighted Financial Networks[J]. International Journal of Modern Physics C, 2010,21(3):433-441.
[1] 王若琳, 牛振东, 蔺奇卡, 朱一凡, 邱萍, 陆浩, 刘东磊. 基于异质信息嵌入与RNN聚类参数预测的作者姓名消歧方法*[J]. 数据分析与知识发现, 2021, 5(8): 13-24.
[2] 王晰巍,贾若男,韦雅楠,张柳. 多维度社交网络舆情用户群体聚类分析方法研究*[J]. 数据分析与知识发现, 2021, 5(6): 25-35.
[3] 卢利农,祝忠明,张旺强,王小春. 基于Lingo3G聚类算法的机构知识库跨库知识整合与知识指纹服务实现[J]. 数据分析与知识发现, 2021, 5(5): 127-132.
[4] 张梦瑶, 朱广丽, 张顺香, 张标. 基于情感分析的微博热点话题用户群体划分模型 *[J]. 数据分析与知识发现, 2021, 5(2): 43-49.
[5] 丁浩, 艾文华, 胡广伟, 李树青, 索炜. 融合用户兴趣波动时序的个性化推荐模型*[J]. 数据分析与知识发现, 2021, 5(11): 45-58.
[6] 杨辰, 陈晓虹, 王楚涵, 刘婷婷. 基于用户细粒度属性偏好聚类的推荐策略*[J]. 数据分析与知识发现, 2021, 5(10): 94-102.
[7] 于丰畅,程齐凯,陆伟. 基于几何对象聚类的学术文献图表定位研究[J]. 数据分析与知识发现, 2021, 5(1): 140-149.
[8] 邬金鸣,侯跃芳,崔雷. 基于医学主题词标引规则的词共现聚类分析结果自动判读和表达的研究[J]. 数据分析与知识发现, 2020, 4(9): 133-144.
[9] 温萍梅,叶志炜,丁文健,刘颖,徐健. 命名实体消歧研究进展综述*[J]. 数据分析与知识发现, 2020, 4(9): 15-25.
[10] 席运江, 杜蝶蝶, 廖晓, 仉学红. 基于超网络的企业微博用户聚类研究及特征分析*[J]. 数据分析与知识发现, 2020, 4(8): 107-118.
[11] 熊回香,李晓敏,李跃艳. 基于图书评论属性挖掘的群组推荐研究*[J]. 数据分析与知识发现, 2020, 4(2/3): 214-222.
[12] 魏家泽,董诚,何彦青,刘志辉,彭柯芸. 基于均衡段落和分话题向量的新闻热点话题检测研究*[J]. 数据分析与知识发现, 2020, 4(10): 70-79.
[13] 赵华茗,余丽,周强. 基于均值漂移算法的文本聚类数目优化研究 *[J]. 数据分析与知识发现, 2019, 3(9): 27-35.
[14] 李珊,姚叶慧,厉浩,刘洁,嘎玛白姆. 基于ISA联合聚类的组推荐算法研究 *[J]. 数据分析与知识发现, 2019, 3(8): 77-87.
[15] 李柯,佐々木勇和. 基于多维小波聚类的空间文本数据情感分布分析[J]. 数据分析与知识发现, 2019, 3(7): 14-22.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 2015 《数据分析与知识发现》编辑部
地址:北京市海淀区中关村北四环西路33号 邮编:100190
电话/传真:(010)82626611-6626,82624938
E-mail:jishu@mail.las.ac.cn