Please wait a minute...
Data Analysis and Knowledge Discovery  2020, Vol. 4 Issue (4): 119-128    DOI: 10.11925/infotech.2096-3467.2019.0674
Current Issue | Archive | Adv Search |
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
Download: PDF(849 KB)   HTML ( 2
Export: BibTeX | EndNote (RIS)      
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     
Received: 11 June 2019      Published: 01 June 2020
ZTFLH:  TP311.1  
Corresponding Authors: Qian Xiaodong     E-mail: qianxd@mail.lzjtu.cn

Cite this article:

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.

URL:

http://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.2096-3467.2019.0674     OR     http://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/Y2020/V4/I4/119

Convergence Time of Vicsek Model
Convergence Time of Variable Rate Vicsek Model
“Kite Network” Topology
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
“Kite Network” Multi-attribute Decision Evaluation Results
无权重 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
Convergence Speed of Vicsek Model Without Weight and Vicsek Model with closeness as Weight (π omitted)
证券市场的股票分类 本文算法 基于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
Comparison of the Results of Three Clustering Algorithms
Variation of Clustering Results with 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] Xiong Huixiang,Li Xiaomin,Li Yueyan. Group Recommendation Based on Attribute Mining of Book Reviews[J]. 数据分析与知识发现, 2020, 4(2/3): 214-222.
[2] Huaming Zhao,Li Yu,Qiang Zhou. Determining Best Text Clustering Number with Mean Shift Algorithm[J]. 数据分析与知识发现, 2019, 3(9): 27-35.
[3] Shan Li,Yehui Yao,Hao Li,Jie Liu,Karmapemo. ISA Biclustering Algorithm for Group Recommendation[J]. 数据分析与知识发现, 2019, 3(8): 77-87.
[4] Ke Li,Yuya Sasaki. Analyzing Sentiment Distribution with Spatial-textual Data of Multi-dimensional Clustering[J]. 数据分析与知识发现, 2019, 3(7): 14-22.
[5] Cheng Zhou,Hongqin Wei. Evaluating and Classifying Patent Values Based on Self-Organizing Maps and Support Vector Machine[J]. 数据分析与知识发现, 2019, 3(5): 117-124.
[6] Quan Lu,Anqi Zhu,Jiyue Zhang,Jing Chen. Research on User Information Requirement in Chinese Network Health Community: Taking Tumor-forum Data of Qiuyi as an Example[J]. 数据分析与知识发现, 2019, 3(4): 22-32.
[7] Jiang Wu,Yinghui Zhao,Jiahui Gao. Research on Weibo Opinion Leaders Identification and Analysis in Medical Public Opinion Incidents[J]. 数据分析与知识发现, 2019, 3(4): 53-62.
[8] Lianjie Xiao,Mengrui Gao,Xinning Su. An Under-sampling Ensemble Classification Algorithm Based on Fuzzy C-Means Clustering for Imbalanced Data[J]. 数据分析与知识发现, 2019, 3(4): 90-96.
[9] Jiaxin Ye,Huixiang Xiong. Recommending Personalized Contents from Cross-Domain Resources Based on Tags[J]. 数据分析与知识发现, 2019, 3(2): 21-32.
[10] Chongwu Bi,Guanghui Ye,Mingqian Li,Jieyan Zeng. Discovering City Profile Based on Tag Semantic Mining[J]. 数据分析与知识发现, 2019, 3(12): 41-51.
[11] Junzhi Jia,Zhuangzhuang Ye. Clustering Wikidata’s Organizational Entities with Latent Semantic Index[J]. 数据分析与知识发现, 2019, 3(10): 56-65.
[12] Huiying Gao,Tian Wei,Jiawei Liu. Friend Recommendation Based on User Clustering and Dynamic Interaction Trust Relationship[J]. 数据分析与知识发现, 2019, 3(10): 66-77.
[13] Tao Zhang,Haiqun Ma. Clustering Policy Texts Based on LDA Topic Model[J]. 数据分析与知识发现, 2018, 2(9): 59-65.
[14] Xiangdong Li,Fan Gao,Youhai Li. Categorizing Documents Automatically within Common Semantic Space[J]. 数据分析与知识发现, 2018, 2(9): 66-73.
[15] Xiufang Wang,Shu Sheng,Yan Lu. Analyzing Public Opinion from Microblog with Topic Clustering and Sentiment Intensity[J]. 数据分析与知识发现, 2018, 2(6): 37-47.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626,82624938   E-mail:jishu@mail.las.ac.cn