Please wait a minute...
Advanced Search
数据分析与知识发现  2020, Vol. 4 Issue (4): 119-128    DOI: 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 ( 3
输出: 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     
中图分类号:  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, DOI:10.11925/infotech.2096-3467.2019.0674.
链接本文:  
http://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/10.11925/infotech.2096-3467.2019.0674
图1  Vicsek模型收敛时间
图2  变速率Vicsek模型收敛时间
图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
表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
表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
表3  三种聚类算法结果对比
图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.
( 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.
( 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.
( 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.
( 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.
( 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.
( 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.
( 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.
( 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.
( 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] 熊回香,李晓敏,李跃艳. 基于图书评论属性挖掘的群组推荐研究*[J]. 数据分析与知识发现, 2020, 4(2/3): 214-222.
[2] 赵华茗,余丽,周强. 基于均值漂移算法的文本聚类数目优化研究 *[J]. 数据分析与知识发现, 2019, 3(9): 27-35.
[3] 李珊,姚叶慧,厉浩,刘洁,嘎玛白姆. 基于ISA联合聚类的组推荐算法研究 *[J]. 数据分析与知识发现, 2019, 3(8): 77-87.
[4] 李柯,佐々木勇和. 基于多维小波聚类的空间文本数据情感分布分析[J]. 数据分析与知识发现, 2019, 3(7): 14-22.
[5] 周成,魏红芹. 专利价值评估与分类研究*——基于自组织映射支持向量机[J]. 数据分析与知识发现, 2019, 3(5): 117-124.
[6] 陆泉,朱安琪,张霁月,陈静. 中文网络健康社区中的用户信息需求挖掘研究*——以求医网肿瘤板块数据为例[J]. 数据分析与知识发现, 2019, 3(4): 22-32.
[7] 吴江,赵颖慧,高嘉慧. 医疗舆情事件的微博意见领袖识别与分析研究*[J]. 数据分析与知识发现, 2019, 3(4): 53-62.
[8] 肖连杰,郜梦蕊,苏新宁. 一种基于模糊C-均值聚类的欠采样集成不平衡数据分类算法*[J]. 数据分析与知识发现, 2019, 3(4): 90-96.
[9] 叶佳鑫,熊回香. 基于标签的跨领域资源个性化推荐研究*[J]. 数据分析与知识发现, 2019, 3(2): 21-32.
[10] 毕崇武,叶光辉,李明倩,曾杰妍. 基于标签语义挖掘的城市画像感知研究 *[J]. 数据分析与知识发现, 2019, 3(12): 41-51.
[11] 贾君枝,叶壮壮. 基于潜在语义索引的Wikidata机构实体聚类研究 *[J]. 数据分析与知识发现, 2019, 3(10): 56-65.
[12] 高慧颖,魏甜,刘嘉唯. 基于用户聚类与动态交互信任关系的好友推荐方法研究 *[J]. 数据分析与知识发现, 2019, 3(10): 66-77.
[13] 张涛,马海群. 一种基于LDA主题模型的政策文本聚类方法研究*[J]. 数据分析与知识发现, 2018, 2(9): 59-65.
[14] 李湘东,高凡,李悠海. 共通语义空间下的跨文献类型文本自动分类研究*[J]. 数据分析与知识发现, 2018, 2(9): 66-73.
[15] 牟冬梅,金姗,琚沅红. 基于文献数据的疾病与基因关联关系研究*[J]. 数据分析与知识发现, 2018, 2(8): 98-106.
Viewed
Full text


Abstract

Cited

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