基于结构熵的注意力流网络异构性研究

doi:10.3778/j.issn.1002-8331.2011-0058

摘要/Abstract

摘要：

结构熵作为复杂网络无序程度度量的重要手段，反映了网络内结构的异质性。传统结构熵在刻画复杂网络异构性时只关注网络结构中的“点”和“边”，表征注意力流网络结构的异构性特征时存在不足。对此，基于在线点击行为数据构建注意力流网络，在传统网络结构熵的基础上，综合考虑站点的边权重、站点的总停留时长等网络特征属性，定义了结构熵模型。进而，从站点的流强度、吸引注意力的能力等指标计算站点综合力，提出了注意力流网络异构性度量算法ANSE。实验结果表明，提出的结构熵可以有效地反映注意力流网络的结构特征，准确地度量注意力流网络中站点之间的差异性，分析站点重要性排序，通过和传统经典算法对比，在站点影响力排名上证明了该算法的优越性和有效性。

关键词: 复杂网络, 注意力流网络, 结构熵, 网络异构性, 站点重要性

Abstract:

Structural entropy, as an important measure of the disorder degree of complex networks, reflects the heterogeneity of the structure within the network. Traditional structural entropy only pays attention to the “node” and “edge” in the network structure when describing the heterogeneity of complex networks, and there are deficiencies in characterizing the heterogeneity of the attention flow network structure. In this regard, this paper constructs an attention flow network based on online click behavior data. On the basis of the traditional network structure entropy, with the website’s edge weight, the total stay time of the website and other network characteristics comprehensively considered, the structure entropy model is defined. Furthermore, the comprehensive power of the website is calculated from the website’s flow intensity, the ability to attract attention and other indicators, and an attention flow network heterogeneity measurement algorithm ANSE is proposed. Experimental results show that the structural entropy proposed in this paper can effectively reflect the structural characteristics of the attention flow network, accurately measure the differences between websites in the attention flow network, analyze the importance of the websites.?The influence ranking proves the superiority and effectiveness of this algorithm by comparing it with traditional classic algorithms.

Key words: complex network, attention flow network, structural entropy, network heterogeneity, website importance

马满福，郭晨彪，李勇，张钟颖，张强，王常青. 基于结构熵的注意力流网络异构性研究[J]. 计算机工程与应用, 2021, 57(23): 98-105.

MA Manfu, GUO Chenbiao, LI Yong, ZHANG Zhongying, ZHANG Qiang, WANG Changqing. Research on Heterogeneity of Attention Flow Network Based on Structural Entropy[J]. Computer Engineering and Applications, 2021, 57(23): 98-105.

参考文献

[1] BARABASI A L.Network science：luck or reason[J].Nature，2012，489（27）：507-508.
[2] BOCCALETTI S，LATORA V，MORENO Y，et al.Complex networks：structure and dynamics[J].Physics Reports，2006：175-308.
[3] VAZQUEZ A，DOBRIN R，SERGI D，et al.The topological relationship between the large-scale attributes and local interaction patterns of complex networks[J].Proceedings of the National Academy of Sciences of the United States of America，2004，101（52）：17940-17945.
[4] 马剑，许素梅，范文博，等.大规模人群网络流瓶颈识别方法研究[J].系统工程理论与实践，2016，36（1）：164-173.
MA J，XU S M，FAN W B，et al.Method of bottlenenk identification for massive crowd circulating network[J].Systems Engineering-Theory ＆ Practice，2016，36（1）：164-173.
[5] 黄春林，刘兴武，邓明华，等.复杂网络上疾病传播溯源算法综述[J].计算机学报，2018，41（6）：1376-1399.
HUANG C L，LIU X W，DENG M H，et al.A survey on algorithms for epidemic source identification on complex networks[J].Chinese Journal of Computers，2018，41（6）：1376-1399.
[6] LERMANSINKOFF D B，DEANNA M.Network community structure alterations in adult schizophrenia：identification and localization of alterations[J].NeuroImage：Clinical，2016：96-106.
[7] 钱珺，王朝坤，郭高扬.基于社区的动态网络节点介数中心度更新算法[J].软件学报，2018，29（3）：853-868.
QIAN J，WANG C K，GUO G Y.Community based node betweenness centrality updating algorithms in dynamic networks[J].Journal of Software，2018，29（3）：853-868.
[8] AI X.Node importance ranking of complex networks with entropy variation[J].Entropy，2017，19（7）：303.
[9] ZHOU A，SUN Q，YANG G.An entropy-based self-adaptive node importance evaluation method for complex networks[J].Complexity，2020，10：1-13.
[10] 曹玖新，闵绘宇，王浩然，等.竞争环境中基于主题偏好的利己信息影响力最大化算法[J].计算机学报，2019，42（7）：1495-1510.
CAO J X，MIN H Y，WANG H R，et al.Self-interest influence maximization algorithm based on subject preference in competitive environment[J].Chinese Journal of Computers，2019，42（7）：1495-1510.
[11] 宋玉蓉，蒋国平.具有非均匀传输和抗攻击差异的网络病毒传播模型[J].物理学报，2010，59（11）：7546-7551.
SONG Y R，JIANG G P.Epidemic-spreading model for networks with different anti-attack abilities of nodes and nonuniform transmission of edges[J].Acta Physica Sinica，2010，59（11）：7546-7551.
[12] SANDHU R，GEORGIOU T，REZNIK E，et al.Graph curvature for differentiating cancer networks[J].Scientific Reports，2015（5）：12323.
[13] LI Angsheng，PAN Yicheng.Structural information and dynamical complexity of networks[J].IEEE Transactions on Information Theory，2016，62（6）：3290-3339.
[14] 黄丽亚，霍宥良，王青，等.基于K-阶结构熵的网络异构性研究[J].物理学报，2019，68（1）：347-359.
HUANG L Y，HUO Y L，WANG Q，et al.Network heterogeneity based on K-order structure entropy[J].Acta Physica Sinica，2019，68（1）：347-359.
[15] SOLé R V，VALVERDE S.Information theory of complex networks：on evolution and architectural constraints[M]//Complex networks.Berlin：Springer-Verlag，2004：189-207.
[16] 吴俊，谭跃进，邓宏钟，等.无标度网络拓扑结构非均匀性研究[J].系统工程理论与实践，2007，27（5）：101-105.
WU J，TAN Y J，DENG H Z，et al.Heterogeneity of scale-free network topology[J].System Engineering-Theory & Practice，2007，27（5）：101-105.
[17] 蔡萌，杜海峰，任义科，等.一种基于点和边差异性的网络结构熵[J].物理学报，2011，60（11）：157-165.
CAI M，DU H F，REN Y K，et al.A new network structure entropy based node difference and edge difference[J].Acta Physica Sinica，2011，60（11）：157-165.
[18] 蔡萌，杜海峰，费尔德曼.一种基于最大流的网络结构熵[J].物理学报，2014，63（6）：102-112.
CAI M，DU H F，FELDMAN M W.A new network structure entropy based on maximum flow[J].Acta Physica Sinica，2014，63（6）：102-112.
[19] 蔡萌，杜海峰，费尔德曼.Caveman网络及其在复杂网络熵分析中的应用[J].系统工程理论与实践，2017，37（9）：2403-2412.
CAI M，DU H F，FELDMAN M W.Caveman network and its application in analysis of complex network entropy[J].Systems Engineering-Theory & Practice，2017，37（9）：2403-2412.
[20] LI Y，MENG X F，ZHANG Q，et al.Common patterns of online collective attention flow[J].Science China Information Sciences，2017，60（5）：59102.
[21] 李勇，孟小峰，刘继，等.基于小数据的在线用户兴趣长程演化研究[J].计算机研究与发展，2015，52（4）：779-788.
LI Y，MENG X F，LIU J，et al.Study of the long-range evolution of online human-interest based on small data[J].Computer Research and Development，2015，52（4）：779-788.
[22] LOU X，LI Y，GU W，et al.The atlas of Chinese world wide web ecosystem shaped by the collective attention flows[J].PloS ONE，2016，11（11）：e0165240.
[23] LI Y，ZHANG J，MENG X F，et al.Quantifying the influence of websites based on online collective attention flow[J].Journal of Computer Science and Technology，2015，30（6）：1175-1187.
[24] SHI P，HUANG X，WANG J，et al.A geometric representation of collective attention flows[J].PloS ONE，2015，10（9）：e0136243.
[25] KUMAR R，TOMKINS A.A characterization of online browsing behavior[C]//Proceedings of the 19st World Wide Web Conference（WWW 2010），Raleigh，North Carolina，USA.New York：ACM，2010：561-570.
[26] STOJMIROVIC A，YU Y.Information flow in interaction networks II：channels，path lengths，and potentials[J].Journal of Computational Biology，2012，19（4）：379-403.
[27] KEMENY J，SNELL J.Finite Markov chains[M].Berlin：Springer-Verlag，1976：45-49.