深圳大学学报理工版

评述基于链接的同质社会网络社区发现方法,介绍基于多维链接关系和多模信息属性的异质网络社区发现方法,指出社会网络个体间不仅存在多种相互联系,其本身还存在描述自身特性的多种特征信息属性; 对社会网络认识的逐渐深入,需融合多方面信息协同处理.根据链接关系矩阵,选取博客平台BlogCatalog,在协同训练框架下融合用户特征信息并进行仿真,模拟异质多模社会网络社区发现.结果表明,对多种链接信息和内容属性信息的融合研究和协同处理可为社会网络社区发现提供准确丰富的信息.

The analysis of social networks, in particular, the discovery of communities within a network, has been a focus of recent research with diverse applications in several fields. In many social networks, there exist different link relations between users while attributes or content information and factors such as demographic details or user-generated content may be associated with those users. In this paper, we outline the state-of-the-art community detection methods based on linked homogeneous social networks. Then, we emphasize community detection in a heterogeneous social network either with multimodal information for each user in the network or with multidimensional relations between users. For the heterogeneous multimode social network, a new community detection method is proposed in the framework of co-training to combine both links and content analysis. Experimental simulations on a real heterogeneous multimode social network dataset were performed and the results have shown that integration of links information and content attributes provided richer and more accurate information for detecting social network community structures.

引言
1 基于链接的同质社会网络社区发现
2 异质社会网络社区发现
3 基于协同训练的异质社会网络社区发现
4 结语

图1 异质多模网络示意图<br/>Fig.1 Multi-mode network

图1 异质多模网络示意图
Fig.1 Multi-mode network

图2 异质多维网络示意图<br/>Fig.2 Multi-dimension network

图2 异质多维网络示意图
Fig.2 Multi-dimension network

图3 四种融合方法下的异质多模网络社区检测对比<br/>Fig.3 Community detection in heterogeneous multi-mode network with four integration methods

图3 四种融合方法下的异质多模网络社区检测对比
Fig.3 Community detection in heterogeneous multi-mode network with four integration methods

图4 基于协同训练和基于最大模块化的社区划分准确率比较<br/>Fig.4 Accuracy comparison of community detection with co-training and modularity maximization

图4 基于协同训练和基于最大模块化的社区划分准确率比较
Fig.4 Accuracy comparison of community detection with co-training and modularity maximization

图5 基于协同训练和基于朴素贝叶斯的社区划分准确率比较<br/>Fig.5 Accuracy comparison of community detection with co-training and Naive Bayesian

图5 基于协同训练和基于朴素贝叶斯的社区划分准确率比较
Fig.5 Accuracy comparison of community detection with co-training and Naive Bayesian

[1] Ferrara E,Fiumara G.Topological features of online social networks[J].Communications in Applied and Industrial Mathematics,2011,2(2):1-20.
[2] Comar P M,Tan P N,Jain A K.A framework for joint community detection across multiple related networks[J].Neurocomputing,2012,76(1):93-104.
[3] Lu Xiaoye,Chen wei.Key-nodes mining algorithm based on communities [J].Application of Computer System,2012,21(4):250-253.(in Chinese)
[4] Tian Jiatang,Wang Yitong,Feng Xiaojun.A new hybrid algorithm for influence maximization in social networks [J].Chinese Journal of Computers,2011,34(10):1956-1965.(in Chinese)
[5] Tang Jiliang,Wang Xufei,Liu Huan.Integrating social media data for community detection[C]// Modeling and Mining Ubiquitous Social Media.Berlin:Springer-Verlag,2011:1-20.
[6] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of the Sciences of the United States of America(PNAS),2002,99(12):7821-7826.
[7] Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E, 2004,69(2):026113-1-026113-13.
[8] Guimera R,Amaral L A N.Modeling the world-wide airport network[J].The European Physical Journal B,2004,38(2):381-385.
[9] Fortunato S, Barthdlemy M.Resolution limit in community detection[J].Proceedings of the National Academy of the Sciences of the United States of America(PNAS),2007,104(1):36-41.
[10] Nowicki K,Snijders T A B.Estimation and prediction for stochastic blockstructures[J].Journal of the American Statistical Association,2001,96(455):1077-1987.
[11] Airoldi E M,Blei D M,Fienberg S E,et al.Mixed membership stochastic block models[J].The Journal of Machine Learning Research,2008,9(6):1981-2014.
[12] Hofman J M,Wiggins C H. Bayesian approach to network modularity[J].Physical Review Letters,2008, 100(25):258701-1-2587-1-4.
[13] Yu K,Yu S P,Trespl V.Soft clustering on graphs[C]// Advances in Neural Information Processing Systems.Cambridge(USA):MIT Press,2005:1-5.
[14] Ren W,Yan G Y,Liao X P.Simple probabilistic algorithm for detecting community structure in social networks[J].Physical Review E,2009,79(3):036111-1-036111-9.
[15] Newman M E J E,Leicht E A A.Mixture models and exploratory analysis in networks[J].Proceedings of the National Academy of the Sciences of the United States of America(PNAS),2007,104(23):9564-9569.
[16] Lawrence P,Sergey B,Rajeev M,et al.The Pagerank citation ranking:bringing order to the web[R].SIDL-WP-1999-0120.Stanford University:Stanford Digital Library Technologies Project,1998.
[17] Kleinberg J M.Authoritative sources in a hyperlinked environment[J].Journal of the ACM,1999,46(5):604-632.
[18] Cohn D,Chang H.Learning to probabilistically identify authoritative documents[C]// In Proceedings of the 17th International Conference on Machine Learning.San Francisco(USA):Morgan Kaufmann Publishers Inc,2000:167-174.
[19] Hofmann T.Probabilistic latent semantic analysis[C]// Proceedings of the 22nd annual internal ACM SIGIR conferences on Research and development in information retrieval.New York:ACM,1999:50-57.
[20] Erosheva E,Fienberg S,Fafferty J.Mixed membership models of scientific publications[J].Proceedings of the National Academy of the Sciences of the United States of America(PNAS),2004,101(4):5220-5227.
[21] Blei D M,Ng A Y,Jordan M I.Latent Dirichlet allocation[J].Journal of Machine Learning Research,2003,3:993-1022.
[22] Nallapati R M,Ahmed A,Xing E P,et al.Joint latent topic models for text and citations[C]// Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2008:542-550.
[23] Airoldi E M,Blei D M,Fienberg S E,et al.Mixed membership stochastic blockmodels[J].The Journal of Machine Learning Research,2008,9:1981-2014.
[24] Tang L,Wang X F,Liu H.Community detection via heterogeneous interaction analysis[J].Data Mining and Knowledge Discovery, 2012,25(1): 1-33.
[25] White S, Smyth P.A spectral clustering approach to finding communities in graphs[C]// SIAM Conference on data mining.Newport Beach(USA): The Society for Industrial and Applied Mathematics. 2005:274-285.
[26] Papalexakis E E,Akoglu L,Ienco D.Do more views of a graph help? Community detection and clustering in multi-graphs[C]// The 16th International Conference on Information Fusion.Istanbul:[s.n.],2013: 899-905.
[27] Liu Y,Niculescu-Mizil A,Gryc W.Topic-link LDA:joint models of topic and author community[C]// Proceedings of the 26th Annual International Conference on Machine Learning.New York:ACM,2009:665-672.
[28] Cai Deng,Shao Zheng,He Shaofei.Community mining from multi-relational networks[C]// The 9th European Conference on Principles and Practice of Knowledge Discovery in Databases.Porto(Portugal):Springer-Verlag,2005,3721:445-452.
[29] Gollini I,Murphy T B.Joint modelling of multiple network views[J/OL].(2013-01-17).Ithaca(USA):Cornell University,2013:1-30.http://arxiv.org/abs/1301.3759.
[30] Cohn D,Hofmann T.The missing link-a probabilistic model of document content and hypertext connectivity[C]// Advances in Neural Information Processing Systems.Cambridge(USA):MIT Press,2000:1-7.
[31] Yang Tianbao,Jin Rong,Chi Yun,et al.Combining link and content for community detection:a discriminative approach[C]// ACM on Knowledge Discovery and Data Mining. New York:ACM,2009:927-936.
[32] Jin Long,Xu Congfu,Luo Guojing.Community mining with heterogeneous relation[J].Computer Applications,2007,27(12):3016-3018.(in Chinese)
[33] Zhu Shenghuo,Yu Kai,Chi Yun.Combining content and link for classification using matrix factorization[C]// Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York:ACM,2007:487-494.
[34] Yu S,Moor B De,Moreau Y.Clustering by heterogeneous data fusion:framework and applications[C]// Learning from Multiple Sources Workshop.Whistler(Canada):NIPS Workshop,2009:4007630-1-4007630-6.
[35] Sun Y,Tang J,Han J.Community evolution detection in dynamic heterogeneous information networks[C]// Proceedings of the Eighth Workshop on Mining and Learning with Graphs.New York:ACM,2010:137-146.
[36] Tang Lei,Liu Huan,Zhang Jianping.Community evolution in dynamic multimode networks[C]// Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2008:677-685.
[37] Tang Lei, Liu Huan, Zhang Jianping. Identifying evolving groups in dynamic multimode networks[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(1):72-85.
[38] Yang Yang,Tang Jie,Keomany J,et al.Mining competitive relationships by learning across heterogeneous networks [C]// Proceedings of the 21st ACM International Conference on Information and Knowledge Management.New York:ACM,2012:1432-1441.
[39] Wang Zhu,Zhou Xingshe,Zhang Daqing,et al.Cross-domain community detection in heterogeneous social networks[J].Personal and Ubiquitous Computing,2013,17(96):1-5.
[40] Comar P M,Tan P N,Jain A K.Simultaneous classification and community detection on heterogeneous network data[J].Data Mining and Knowledge Discovery,2012,25(3):420-449.
[41] Wang Xiang,Qian Buyue,Ye Jieping,et al.Multi-objective multi-view spectral clustering via pareto optimization[C]// The 13th SIAM International Conference on Data Mining.Dallas(USA):SDM,2013:234-242.
[42] Greene D,Cunningham P.Producing a unified graph representation from multiple social network views[C]// Proceedings of the 5th Annual ACM Web Science Conference.Paris:ACM,2013:118-121.
[43] Wang Na,Li Xia.Active semi-supervised spectral clustering based on pairwise constraints[J].Acta Electronic Sinca,2010,38(1):172-176.(in Chinese)

备注

引言

1 基于链接的同质社会网络社区发现

2 异质社会网络社区发现

3 基于协同训练的异质社会网络社区发现

4 结语

期刊信息

备注

引言

1 基于链接的同质社会网络社区发现

2 异质社会网络社区发现

3 基于协同训练的异质社会网络社区发现

4 结 语

期刊信息

4 结语