基于权邻域的代表性用户抽样算法

doi:10.3778/j.issn.1002-8331.2012-0554

摘要/Abstract

摘要： 代表性用户抽样方法在社会网络分析领域中得到广泛的应用，如何使其抽取的子集代表网络中所有用户具有重要的研究意义。现有方法较少关注网络拓扑结构中用户潜在的大量有用信息，通过对统计分层抽样模型进行优化，提出了一种基于权邻域的代表性用户抽样算法。为了从网络拓扑结构中获得用户更多有价值的内容，该算法使用权邻域对用户代表度计算方法进行改进，同时与用户属性相结合。之后根据用户属性值将用户分成不同属性组，计算用户在每个属性组的代表度。接着通过质量函数来衡量代表性用户的代表程度。采用启发式贪心算法抽取代表性用户。在4个数据集上与6种传统抽样算法进行实验比较，结果表明基于权邻域的代表性用户抽样算法在精确率、召回率和F1-Measure评价指标上均有提升。

关键词: 社交网络, 代表性用户抽样, 权邻域, 拓扑结构, 用户代表度

Abstract: The representative user sampling method is widely used in the field of social network analysis, how to make its subset represent all users in the network has great significance. The existing methods pay less attention to the large amount of useful information of potential users in the network topology, by optimizing the statistical stratified sampling model, the representative user sampling algorithm based on weighted neighborhood is proposed. In order to get more valuable content from the network topology, the algorithm uses the weighted neighborhood to improve the calculation method of user representation, and combines with user attributes. Then users are divided into different attribute groups according to their attribute values, and the representation of users in each attribute group is calculated. After that, the representation of representative users is measured by quality function. The heuristic greedy algorithm is used to extract representative users. By comparing with six traditional sampling algorithms on four data sets, the results show that the representative user sampling algorithm based on weighted neighborhood improves the accuracy rate, recall rate and F1-Measure evaluation index.

Key words: social network, representative user sampling, weighted neighborhood, topological structure, user representation

何水苗, 班志杰. 基于权邻域的代表性用户抽样算法[J]. 计算机工程与应用, 2022, 58(12): 94-101.

HE Shuimiao, BAN Zhijie. Representative User Sampling Algorithm Based on Weighted Neighborhood[J]. Computer Engineering and Applications, 2022, 58(12): 94-101.

参考文献

[1] SEMENKOVICH S A，TSUKANOVA O A.On the algorithms of identifying opinion leaders in social networks[J].Procedia Computer Science，2019，162：778-785.
[2] 刘子图，全紫薇，毛如柏，等.NT-EP：一种无拓扑结构的社交消息传播范围预测方法[J].计算机研究与发展，2020，57（6）：1312-1322.
LIU Z T，QUAN Z W，MAO R B，et al.NT-EP：a non-topology method for predicting the scope of social message propogation[J].Journal of Computer Research and Development，2020，57（6）：1312-1322.
[3] 刘井莲，王大玲，冯时，等.一种基于模糊相似关系的局部社区发现方法[J].软件学报，2020，31（11）：165-175.
LIU J L，WANG D L，FENG S，et al.Local community discovery approach based on fuzzy similarity relation[J].Journal of Software，2020，31（11）：165-175.
[4] 廖宇，朱福喜，刘世超.基于Skip-gram模型的社区查询算法[J].计算机工程与应用，2018，54（8）：143-148.
LIAO Y，ZHU F X，LIU S C.Community search based on skip-gram[J].Computer Engineering and Applications，2018，54（8）：143-148.
[5] NGUYEN H T，THAI M T，DINH T N.Stop-and-stare： optimal sampling algorithms for viral marketing in billion-scale networks[C]//Proceedings of the 2016 International Conference on Management of Data，San Francisco，Jun 26-Jul 1，2016.New York：ACM，2016：695-710.
[6] ZHANG M，WEI X，CHEN G.Maximizing the influence in social networks via holistic probability maximization[J].International Journal of Intelligent Systems，2017，33（10）：2038-2057.
[7] CHEN Y C，CHEN Y H，HSU C H，et al.Mining opinion leaders in big social network[C]//Proceedings of 2017 IEEE 31st International Conference on Advanced Information Networking and Applications，Taipei，China，Mar 27-29，2017.Los Alamitos：IEEE Computer Society，2017：1012-1018.
[8] ZHOU Y，HAN Y，LIU A，et al.Extracting representative user subset of social networks towards user characteristics and topological features[C]//LNCS 11233：Proceedings of Web Information Systems Engineering，Dubai，Nov 12-15，2018.Cham：Springer，2018：213-229.
[9] LESKOVEC J，FALOUTSOS C.Sampling from large graphs[C]//Proceedings of Knowledge Discovery and Data Mining，Philadelphia，Aug 20-23，2006.New York：ACM，2006：631-636.
[10] MAIYA A S，BERGERWOLF T Y.Sampling community structure[C]//Proceedings of the 19th International Conference on World Wide Web，Raleigh，Apr 26-30，2010.New York：ACM，2010：701-710.
[11] MAIYA A S，BERGERWOLF T Y.Benefits of bias：towards better characterization of network sampling[C]//Proceedings of Knowledge Discovery and Data mining，San Diego，Aug 21-24，2011.New York：ACM，2011：105-113.
[12] NATARAJAN D，RANU S.Resling：a scalable and generic framework to mine top-k representative sub-graph patterns[C]//International Conference on Data Mining，2016：123-149.
[13] MALL R，JUMUTC V，LANGONE R，et al.Representative subsets for big data learning using k-nn graphs[C]//IEEE International Conference on Big Data.Los Alamitos：IEEE Computer Society，2014：37-42.
[14] PAPAGELIS M，DAS G，KOUDA S N，et al.Sampling online social networks[J].IEEE Transactions on Knowledge and Data Engineering，2013，25（3）：662-676.
[15] YANG K，CAI Y，CAI Z，et al.Top k representative：a method to select representative samples based on k nearest neighbors[J].International Journal of Machine Learning and Cybernetics，2019，10（8）：2119-2129.
[16] SUN K，MORRISON D，BRUNO E，et al.Learning representative nodes in social networks[C]//LNCS 7819：Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining，Gold Coast，Apr 14-17，2013.Berlin，Heidelberg：Springer，2013：25-36.
[17] TANG J，ZHANGE C，CAI K，et al.Sampling representative users from large social networks[C]//Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence.Palo Alto：AAAI Press，2015：304-310.
[18] ZHAO X，GUO S，WANG Y.The node influence analysis in social networks based on structural holes and degree centrality[C]//IEEE International Conference on Computational Science and Engineering and IEEE International Conference on Embedded and Ubiquitous Computing，Guangzhou，Jul 21-24，2017.Los Alamitos：IEEE Computer Society，2017：708-711.
[19] BRIN S，PAGE L.Reprint of：the anatomy of a large-scale hyper textual web search engine[J].Computer Networks，2012，56（18）：3825-3833.
[20] KLEINBERG J M.Authoritative sources in a hyperlinked environment[J].Journal of the ACM，1999，46（5）：604-632.