基于扩散小波的社会网络多尺度分析

doi:10.3969/j.issn.1000-436x.2014.01.011

摘要/Abstract

摘要：

针对社会网络中的同质性关系提出一个基于扩散小波的多尺度分析框架，通过局部相似性度量构造扩散算子，在统一的框架下对社会网络中的结构、内容、用户行为等进行多尺度分析。在合成和真实网络数据上进行实验，与典型算法的对比表明，本算法在无参数的条件下快速收敛并得到更好的结果。

关键词: 社会网络, 多尺度, 同质性, 扩散小波, 扩散算子

Abstract:

A new multi-scale framework based on diffusion wavelets was proposed to analyze the homogeneous relationships,which can be used to conduct multi-scale analysis on structures,contents and user behaviors.The diffusion operator of diffusion wavelet only considers the local similarity in this framework.The experiments on both synthetic and real-world networks show that the proposed algorithm outperforms the typical algorithms in multi-scale analysis without parameters.

Key words: social network, multi-scale, homogeneity, diffusion wavelets, diffusion operator

申国伟,杨武,黄文延,王巍,丁丽,于淼. 基于扩散小波的社会网络多尺度分析[J]. 通信学报, 2014, 35(1): 89-98.

Guo-wei SHEN,Wu YANG,Wen-ting HUANG,Wei WANG,Li DING,Miao YU. Multi-scale analysis of social network based on diffusion wavelets[J]. Journal on Communications, 2014, 35(1): 89-98.

图/表 10

图1

表1

图2

表2

图3

图4

表3

表4

图5

图6

参考文献 28

[1]	MILLER M , LYNN S L , JAMES M C . Birds of a feather:homophily in social networks[J]. Annual Review of Sociology, 2011,27(2001): 415-444.
[2]	SANTO F . Community detection in graphs[J]. Physics Reports, 2010,486(2010): 75-174.
[3]	NEWMAN M E J , GIRVAN M . Finding and evaluating community structure in networks[J]. Phys Rev E, 2004,69(2):026113.
[4]	NEWMAN M E J . Modularity and community structure in networks[J]. Proceeding of the National Academy Sciences, 2006,103(23): 8577-8582.
[5]	FORTUNTO S , BARTHELEMY M . Resolution limit in community detection[J]. Proceeding of the National Academy Sciences, 2007,104(1): 36-41.
[6]	PETER J M , THOMAS R , KEVIN M ,et al. Community structure in time-dependent,multiscale,and multiplex networks[J]. Science, 2010,328(5980): 876-878.
[7]	AHN Y Y , BAGROW J P , LEHMANN S . Link communities reveal multiscale complexity in networks[J]. Nature, 2010,466: 761-764.
[8]	MARTELOT E L , HANKIN C . Fast multi-scale detection of relevant communities in large-scale networks[J]. The Computer Journal, 2013,56(9): 1136-1150.
[9]	CHEN X Q , SHEN H W . Uncovering the community structure associated with the diffusion dynamics on networks[J].Journal of Statistical Mechanics:Theory and Experiment,2010,(2010):P04024. Journal of Statistical Mechanics:Theory and Experiment, 2010,(2010):P04024.
[10]	SHEN H W , CHEN X Q , WANG Y Z ,et al. A dimensionality reduction framework for detection of multiscale structure in heterogeneous networks[J]. Journal of Computer Science and Technology, 2012,27(2): 341-357.
[11]	LU L Y , ZHOU T . Link prediction in complex network:a survey[J]. Physical A, 2011,390(2011): 1150-1170.
[12]	DAVID M B , ANDREW Y N , MICHAEL I J . Latent dirichlet allocation[J]. Journal of Machine Learning Research, 2003,3: 993-1022.
[13]	ZHAO W X , JIANG J , WENG J S ,et al. Comparing twitter and traditional media using topic models[A]. The 33rd European Conference on Information Retrieval[C]. 2011. 338-349.
[14]	HONG L J , DAVISON B D . Empirical study of topic modeling in twitter[A]. Proceedings of the First Workshop on Social Media Analytics[C]. 2010. 80-88.
[15]	WANG C , MAHADEVAN S . Multiscale analysis of document corpora based on diffusion models[A]. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence[C]. 2009. 1592-1597.
[16]	GYARMATI L , TRINH T A . Measuring user behavior in online social networks[J]. Network, 2010,24(6): 26-31.
[17]	FLAVIO C , RAVI K , PRABHAKAR R ,et al. Are Web users really markovian?[A]. Proceedings of the 21st International Conference World Wide Web[C]. 2012. 609-618.
[18]	WALTER W , REZA R , MAURO M . Research on social networks:time to face the real challenges[J]. ACM SIGMETRICS Performance Evaluation Review, 2009,37(3): 49-54.
[19]	HERVE A , LYNNE J W . Principal component analysis[J]. WIRE Computational Statistics, 2010,2(4): 433-459.
[20]	TENENBAUM J B , SILVA V , LANGFORD J C . A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000,290: 2319-2323.
[21]	MIKHAIL B , PARTHA N . Laplacian eigenmaps for dimensionality reduction and data representation[J]. Neural Computation, 2003,15: 1373-1396.
[22]	RONALD R C , MAURO M . Diffusion wavelets[J]. Applied and Computational Harmonic Analysis, 2006,21: 53-94.
[23]	WANG C , MAHADEVAN S . Multiscale dimensionality reduction based on diffusion wavelets[EB/OL]. .
[24]	刘旭, 易东云 . 基于局部相似性的复杂网络社区发现方法[J]. 自动化学报, 2011,37(12): 1520-1529. LIU X , YI D Y . Complex network community detection by local similarity[J]. Acta Automatica Sinica, 2011,37(12): 1520-1529.
[25]	XIANG R J , NEVILLE J , ROGATI M . Modeling relationship strength in online social networks[A]. Proceedings of the 19th International Conference on World Wide Web[C]. 2010. 981-990.
[26]	LANCICHINETTI A , FORTUNATO S . Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J].Physical Review E,2009,80(1):016118. Physical Review E, 2009,80(1):016118.
[27]	JAEWON Y , LESKOVEC J . Defining and evaluating network communities based on ground-truth[A]. Proceedings of the 2012 IEEE 12th International Conference on Data Mining[C]. 2012. 745-754.
[28]	LI H J , ZHANG J H , LIU Z P ,et al. Identifying overlapping communities in social networks using multi-scale local information expansion[J]. The European Physical Journal B, 2012,85:190.

数据集	节点数	边数
Karate	34	78
Football	115	613
LiveJournal	5 000	33 278
Youtube	10 000	91 040

尺度j	话题数目
1	1 107
2	1 024
3	564
4	65
5	18
6	7
7	1

话题描述（j=6）	话题（j=5）
话题描述（j=6）	编号	话题描述词
	1 汽车丰田中国销量召回
“丰田汽车事件”	2 召回全球车窗电动故障
	3 生产班次置评放假停产
	1 总统辩论大选美国奥巴马
“美国总统大选电视辩论”	2 英语字幕视频罗姆尼口语
	3 钞票餐馆大款文汇报小吃店
“诺贝尔奖”	1 生理红细胞编程格登.约翰医学2 莫言文学奖诺贝尔获奖作家
	1 中国好声音卫视吴莫愁梁博决赛
“中国好声音总决赛”	2 参与投票发起表态心目
	3 大少爷螺丝灯天地-帼帼帼财经中国好声音