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 ( 3
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:

https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.2096-3467.2019.0674     OR     https://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] Wang Ruolin, Niu Zhendong, Lin Qika, Zhu Yifan, Qiu Ping, Lu Hao, Liu Donglei. Disambiguating Author Names with Embedding Heterogeneous Information and Attentive RNN Clustering Parameters[J]. 数据分析与知识发现, 2021, 5(8): 13-24.
[2] Wang Xiwei,Jia Ruonan,Wei Yanan,Zhang Liu. Clustering User Groups of Public Opinion Events from Multi-dimensional Social Network[J]. 数据分析与知识发现, 2021, 5(6): 25-35.
[3] Lu Linong,Zhu Zhongming,Zhang Wangqiang,Wang Xiaochun. Cross-database Knowledge Integration and Fingerprint of Institutional Repositories with Lingo3G Clustering Algorithm[J]. 数据分析与知识发现, 2021, 5(5): 127-132.
[4] Zhang Mengyao, Zhu Guangli, Zhang Shunxiang, Zhang Biao. Grouping Microblog Users of Trending Topics Based on Sentiment Analysis[J]. 数据分析与知识发现, 2021, 5(2): 43-49.
[5] Ding Hao, Ai Wenhua, Hu Guangwei, Li Shuqing, Suo Wei. A Personalized Recommendation Model with Time Series Fluctuation of User Interest[J]. 数据分析与知识发现, 2021, 5(11): 45-58.
[6] Yang Chen, Chen Xiaohong, Wang Chuhan, Liu Tingting. Recommendation Strategy Based on Users’ Preferences for Fine-Grained Attributes[J]. 数据分析与知识发现, 2021, 5(10): 94-102.
[7] Yu Fengchang,Cheng Qikai,Lu Wei. Locating Academic Literature Figures and Tables with Geometric Object Clustering[J]. 数据分析与知识发现, 2021, 5(1): 140-149.
[8] Wen Pingmei,Ye Zhiwei,Ding Wenjian,Liu Ying,Xu Jian. Developments of Named Entity Disambiguation[J]. 数据分析与知识发现, 2020, 4(9): 15-25.
[9] Wu Jinming,Hou Yuefang,Cui Lei. Automatic Expression of Co-occurrence Clustering Based on Indexing Rules of Medical Subject Headings[J]. 数据分析与知识发现, 2020, 4(9): 133-144.
[10] Xi Yunjiang, Du Diedie, Liao Xiao, Zhang Xuehong. Analyzing & Clustering Enterprise Microblog Users with Supernetwork[J]. 数据分析与知识发现, 2020, 4(8): 107-118.
[11] Xiong Huixiang,Li Xiaomin,Li Yueyan. Group Recommendation Based on Attribute Mining of Book Reviews[J]. 数据分析与知识发现, 2020, 4(2/3): 214-222.
[12] Wei Jiaze,Dong Cheng,He Yanqing,Liu Zhihui,Peng Keyun. Detecting News Topics Based on Equalized Paragraph and Sub-topic Vector[J]. 数据分析与知识发现, 2020, 4(10): 70-79.
[13] Huaming Zhao,Li Yu,Qiang Zhou. Determining Best Text Clustering Number with Mean Shift Algorithm[J]. 数据分析与知识发现, 2019, 3(9): 27-35.
[14] Shan Li,Yehui Yao,Hao Li,Jie Liu,Karmapemo. ISA Biclustering Algorithm for Group Recommendation[J]. 数据分析与知识发现, 2019, 3(8): 77-87.
[15] Ke Li,Yuya Sasaki. Analyzing Sentiment Distribution with Spatial-textual Data of Multi-dimensional Clustering[J]. 数据分析与知识发现, 2019, 3(7): 14-22.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626,82624938   E-mail:jishu@mail.las.ac.cn