节点qq发布网

——QQ群超网络特性分析作者刘猛,胡枫机构青海师范大学计算机学院基金项目国家自然科学基金资助项目(61663041);青海科技计划资助项目(2015-ZJ-723)预排期卷《计算机应用研究》2018年第35卷第11期摘要基于超图理论构建了QQ群用户关联关系的超网络模型,并将该模型应用到QQ群真实数据.
通过矩阵理论和超网络方法对所构建的模型进行了分析,得到了该QQ群超网络的超度分布、度分布、聚集系数、子图中心度和平均路径长度等拓扑指标的值.
结果表明,QQ群超网络的超度分布服从幂律分布,且具有较高的聚集系数和较小的平均路径长度,最终揭示了QQ群超网络所具有的"小世界特性".
关键词超网络;超图;QQ群;小世界作者简介刘猛,(1991-),男,河南商丘人,硕士,主要研究方向为超网络理论及应用;胡枫(通信作者),(1970-),女,教授,主要研究方向为复杂网络和超网络理论及应用(qhhuf@163.
com).
中图分类号TP391访问地址http://www.
arocmag.
com/article/02-2018-11-038.
html发布日期2017年11月10日引用格式刘猛,胡枫.
QQ群超网络特性分析[J/OL].
2018,35(11).
[2017-11-10].
http://www.
arocmag.
com/article/02-2018-11-038.
html.
第35卷第11期计算机应用研究Vol.
35No.
11优先出版ApplicationResearchofComputersOnlinePublication基金项目:国家自然科学基金资助项目(61663041);青海科技计划资助项目(2015-ZJ-723)作者简介:刘猛,(1991-),男,河南商丘人,硕士,主要研究方向为超网络理论及应用;胡枫(通信作者),(1970-),女,教授,主要研究方向为复杂网络和超网络理论及应用(qhhuf@163.
com).
QQ群超网络特性分析*刘猛,胡枫(青海师范大学计算机学院,西宁810008)摘要:基于超图理论构建了QQ群用户关联关系的超网络模型,并将该模型应用到QQ群真实数据.
通过矩阵理论和超网络方法对所构建的模型进行了分析,得到了该QQ群超网络的超度分布、度分布、聚集系数、子图中心度和平均路径长度等拓扑指标的值.
结果表明,QQ群超网络的超度分布服从幂律分布,且具有较高的聚集系数和较小的平均路径长度,最终揭示了QQ群超网络所具有的"小世界特性".
关键词:超网络;超图;QQ群;小世界中图分类号:TP391AnalysisofcharacteristicsofQQgrouphypernetworkLiuMeng,HuFeng(SchoolofComputerScienceQinghaiNormalUniversity,Xining810008,China)Abstract:AhypernetworkmodelofQQgroupbasedonhypergraphtheorywasestablishedinthiswork,whichhasbeenappliedtoQQpracticaldataset.
Bothmatrixtheoryandhypernetworkapproacheswereusedtocalculatefewtopologicalindicesofthehypernetwork,suchashyperdegreedistribution,degreedistribution,clusteringcoefficient,subhypergraphcentralityandaveragedistance.
ResultsshowthatthehyperdegreedistributionofQQgroupfollowspower-lawdistribution.
Andthehighclusteringcoefficientandsmallaveragedistanceofthehypernetworkrevealsthecharacteristicsof'small-world'ofQQgroup.
KeyWords:hypernetwork;hypergraph;QQgroup;smallworld0引言现实世界中存在着大量的复杂网络,例如Internet网、电力网络、交通网络、社会网络、新陈代谢网络、引文网络等等.
20世纪末,在Watts和Strogatz提出WS模型[1]以及Barabási和Albert提出BA无标度模型[2]之后,复杂网络的研究受到众多学者的关注.
人们从不同的角度出发提出了各种各样的网络演化模型,在此基础上研究网络功能和特点,并取得丰硕的成果[1-10].
通常所定义的复杂网络是基于普通图的拓扑结构,其中节点表示个体,边表示个体之间存在某种关系.
但是,这种网络结构无法全面准确地描述现实网络的特征[11].
例如,在科研合作网络中,对于两个以上作者是否存在合作关系,直接观察普通网络结构模型是无法得知的,但采用基于超图的超网络结构进行描述,该问题就可以迎刃而解.
因为超网络的超边可以包含两个及以上的节点,所以超网络方法能够准确、全面地描述网络中任意多个节点之间的相互作用和影响.
又如当用基于超图的超网络方法描述食物网络时,不仅可以了解两个物种是否存在食物竞争关系,而且可以获得两者需要竞争的食物种类的数量.
由此可见,超网络结构更加契合与现实网络结构.
迄今为止,众多学者对超网络的理论和建模等方面进行了深入的研究,并得到了一些有价值的结果.
Estrada等人[11]研究了超网络子图中心性和聚类系数等问题,并给出了相应的计算公式.
王建伟等[12]构建了一种基于超图的超网络动态演化模型,该模型采用增长和优先连接机制逐步生成超网络,每次将新增加的若干个节点和超网络中已有的一个节点结合生成超边.
胡枫等人[13,14]构建了BA无标度网络的扩展超网络演化模型,将BA网络视为其特例模型,并对科研合作超网络进行了建模及分析.
索琪等[15-17]对基于超网络模型的电视节目竞争关系、舆情传播模型以及超网络演化的内在驱动力等问题进行了分析.
郭进利等人[18-20]研究了非均匀超网络中标度率的涌现问题,以及构建了Bose-Einstein超网络演化模型,以此来研究超网络结构的超边基数的问题.
此外,他们还对欧洲航空运输超网络进行了实证分析.
张子柯等人[21]建立了一种基于用户背景知识和对象、标签双重优先连接机制的超图增长模型.
Zlatic等人[22]定义和分析了基于三部超图模型的统计特性.
随着互联网的发展和计算机的普及,为了满足跨区域交流的需求,在线社交软件应运而生.
随后,一些研究者开始利用复杂网络模型对在线社交网络的特性进行研究.
何静等人[23]研优先出版刘猛,等:QQ群超网络特性分析第35卷第11期究了微博关系网络模型.
樊鹏翼等人[24]对新浪微博网络的拓扑属性进行分析,并证明其具有小世界特性.
杨凯等[25]研究了微博用户网络的结构和聚类特性,并根据网络节点的不同属性使用K-means聚类算法将微博用户分成了三种类型.
索琪等人[26]构建了一种基于在线社交网络资源评论的超网络演化模型,并给出了度与超度的定义和计算方法.
QQ是集聊天、语音、游戏和网上支付等于一身的在线交友软件,凭借着其强大的交互功能使得人们的生活变得非常便捷.
由于工作和生活的需要,用户不断的加入不同的QQ群,在群间信息被便捷、快速的分享和传播,但是,它也引发了很多问题,例如垃圾信息的泛滥、网络病毒的快速传播.
这些问题时刻威胁着人们的财产安全和信息安全.
为了尽量杜绝这类事件的发生,需要了解QQ网络的结构特性,找出合适的应对策略.
由于用户加入的QQ群有多个,每个QQ群的成员也有多个,契合与用基于超图结构的超网络的"超边"表示多个节点之间的关系.
因此,本文以QQ用户为超网络节点,QQ群为"超边"构建了QQ群超网络模型,并对该模型的拓扑属性进行研究和分析.
1超网络概念及拓扑特性1.
1超网络的概念超网络的定义是由郭进利在文献[18]中给出的.
假设,G是从[0,+∞)到的映射,则对于任意给定的,是一个有限超图,表示到时刻t超图已发生变化的总次数.
如果是一个随机过程,对于充分大的时间t,本文称是一个超网络.
1.
2超网络拓扑特性1)度在超网络H中,超边内部节点之间采用全连接的方式.
节点i的度ki定义与i直接邻接的节点个数.
设H的邻接矩阵A=(aij),则节点i的度ki为2)超度节点i的超度表示包含该节点的超边数量.
设超网络H的关联矩阵C=(cij).
则节点i的超度为其中:cij是关联矩阵C的元素,如果超边j包含节i,则cij=1;否则cij=0.
3)聚集系数平均聚集系数是指在超网络中与同一节点连接的两个节点之间通过超边相互连接的平均概率.
该参数用于刻画超网络的局域结构特性.
Estrada等[11]给出了聚集系数的计算公式.
该公式为(3)其中:λs是邻接矩阵A对应的特征值,U=(uij)是一个正交矩阵,其中每一列表示λs对应的特征向量,这些特征向量构成了N维欧几里得空间的一个正交基.
参数t表示超网络H中伪超三角形的个数.
超三角形是指一个由三个不同的节点和三条不同的超边所组成的这种序列:,其中三个节点彼此相邻.
不满足上述条件的闭合序列被称为伪超三角形.
Estrada等[11]给出了计算伪超三角形的公式.
即(4)其中:,.
4)平均路径长度在超网络H中,节点i和节点j的距离dij是指连接i和j的最短路径上的超边数目,即i和j相连所需通过的最少超边数.
设超网络H的距离矩阵D=(dij),则平均路径长度的计算公式为(5)5)子图中心性节点i的子图中心性是指超网络中起止于该节点的不同长度的闭合路径之和.
由于子图中心性包含平凡的和非平凡的闭合游走,所以在计算该指标时必须考虑所有循环的和非循环的子图.
此外,短闭合路径比长闭合路径对于节点子图中心性的影响更大.
这个规则是基于对现实世界网络模型是小的子超图的观察.
Estrada等[11]给出了节点的子图中心性的计算公式.
即(6)其中:λk是超网络H的邻接矩阵的特征值,U=(uij)是一个正交矩阵,其中每一列表示λs对应的特征向量,这些特征向量构成了N维欧几里得空间的一个正交基.
在已知各节点的子图中心性之后,超网络H的子图中心性的计算公式为(7)根据式(7)可知,超网络子图中心性只与规模N和对应特征值λ有关.
2QQ群超网络模型在基于普通图的复杂网络中,节点表示个体,边表示个体与群中的其他个体连接,用户加入了多个QQ群,和每个群中的个体都要连接,在此情形下,无法确定节点所加入的群数量以及每个群所包含的节点数.
但在基于超图的超网络中,节点同样表示个体,不同个体加入的同一个群用超边来表示.
由于超边包含属于同一群的不同节点,所以节点的超度值即为该个体优先出版刘猛,等:QQ群超网络特性分析第35卷第11期所加入的群数量.
故采用基于超图的超网络方法研究QQ群网络更切合现实QQ网络.
2.
1超网络构建算法在QQ群超网络中,以QQ用户为节点,用户加入的QQ群为超边,构造超网络模型,构建算法如下:a)初始化超网络的节点为vi,其中.
b)递归执行如下操作:检查超网络中的所有节点,若节点vi和vj属于某一QQ群,那么将节点vi和vj放入表示该群的超边中.
c)直至所有节点全部检查完毕,算法结束.
2.
2超网络图本文通过网络咨询、发放调查问卷和当面询问的形式,收集了我校研究生QQ群数据.
这些数据包含103个学生,以及他们加入的45个QQ群.
依据3.
1中的构建算法,构建了我校研究生QQ群超网络,并采用LaTeX-TPX软件绘制出了QQ群超网络的结构图.
如图1所示.
通过图1可知,由于该超网络的每条超边的节点数并不相同,所以它是非均匀超网络.
该超网络是非连通的,由2个连通分支组成,其中主连通分支包含102个节点和44条超边,另一个连通分支仅包含1个节点和1条超边.
此外,在该超网络中,绝大部分节点所加入的超边数较少,即超度小的节点所占比例较大,而超度大的节点所占比例较小.
在此网络中节点103为核心节点,加入的QQ群数量达到了14个,现实网络中的节点103为作者本人,作者由于学习的需要以及兴趣广泛,除了加入专业课程及学院研究生群之外,还加入了家教信息、编程讨论、学生会等群.
3QQ群超网络特性分析3.
1超度分布与度分布超网络的超度分布和度分布是研究超网络特性的重要指标.
节点的超度是反映节点核心程度的指标,在QQ群超网络中节点的超度表示该个体所加入的群数量.
表1给出了QQ群超网络的超度分布情况表.
从表1中可知,绝大多数用户只加入了很少的群,个别用户拥有众多的群.
因为绝大多数用户通常属于某一院系或学习某一专业,所以这些用户通常会选择加入院系群和专业群,其中某些专业由于特殊原因可能没有创建专业群,而个别用户加入了大量的群,此类用户多为各院系的干部或者社交广泛的人.
所以通常认为此类用户为活跃用户.
结合表1和图1可知,节点103和节点94是该超网络的活跃用户,他们分别加入了14个群和6个群.
基于表1数据,图2给出QQ超网络的超度分布图,图中显示超度分布遵循幂律分布,通过双对数线性回归方法得到Slope=-4.
32,相关系数R2等于0.
918.
从超度分布看,用户加入QQ群的行为具有无标度特性,这与文献[25]的结论一致.
即大部分用户只加入了较少的QQ群,个别用户所加入的群数量众多.
该曲线的整体趋势与文献[17]的图3所示曲线是相似的.
说明驱动该超网络演化的因素既有择优机制,又有随机机制.
当新用户进入QQ群时会优先选择与一些具有较大超度的节点,即与超度值较大的用户形成择优关系.
但是,新用户也会根据自己的兴趣和需求加入某些群,与超网络中的老用户随机连边.
这两个混合机制共同驱动了QQ超网络的演化.
在QQ群超网络中,节点i的度表示与节点i相邻接的节点数量.
节点的度的大小不仅取决于包含该节点的超边的数量,还与这些超边的秩(即超边中节点的数量)有关,例如以上构建的QQ群超网络中节点8的超度值小于节点94,但两者的度值却一样大.
表2给出了该超网络度分布情况.
由表2可知,度为7的节点数所占的比例最高.
通过与表1进行对比不难发现,超网络的度分布较为发散;各度值的节点数所占比例都很小.
此外,结合图1可知,若根据节点的度值大小判断超网络的核心节点,则节点103、节点8和节点94是该超网络的核心节点,其度值分别为99,28,28.
图1QQ群超网络图表1超度分布表超度数量/个比例/%1280.
27182500.
48543150.
1456470.
0680510.
0097610.
00971410.
0097图2超度分布图优先出版刘猛,等:QQ群超网络特性分析第35卷第11期基于表2数据,图3给出了QQ群超网络的度分布的情况.
度分布曲线并不完全服从于幂律分布.
从整体上看,分布曲线的下降速度随度的增大而加快.
主要原因是度小的节点所占比例差别较小,而度大的节点所占比例差别较大.
图3中的插图为度大于14的节点度分布,具有幂律特性.
通过度分布分析,节点103具有最大的度值,其度值为99,由于该节点加入了14个QQ群,并且这些群的成员数较多,导致该节点的度值很大.
此外,节点94也具有较高的度值,值为28,该节点加入了6个群.
这说明这两个节点对超网络的影响力较大,原因是超网络中的绝大多数节点都与该节点属于某个相同的群.
为对比超度与度的分布特性,图4给出了QQ群超网络各节点的度与超度的相对度的对比关系,其中i为节点序号,RDi为相对度的值,绿色表示超度,红色表示度.
相对度是指节点的超度(度)值除以整个超网络的最大超度(度)值.
由图4可知,在节点103处,两条曲线同时达到最大值,这表明节点103具有最高的相对值,其次是节点94.
此外,在该超网络中,超度值排在前十位的大部分节点,其度值也排在前十位.
这与在文献[11]中对于"生成图"合作网络的描述恰恰相反.
主要原因是节点超度的大小取决于超边(即群)的数量,但节点度的大小不仅取决于超边的数量,还与这些超边的秩有关.
例如某些节点加入的群个数较少,但当群中的成员较多时,节点的度值也会很大.
综上所述,节点103和节点94是该超网络的核心节点.
3.
2子图中心性仅依据超网络的度分布和超度分布是无法全面地描述QQ群超网络中心性特性,子图中心性也是反映超网络中心性特性的重要指标.
图5描述了在超网络和其对应的复杂网络中各节点的相对子图中心性的情况,其中i为节点序号,RCi为相对子图中心性的值,红色代表在超网络中,蓝色代表在复杂网络中.
由图5可知,两条曲线基本重合,这说明在超网络和对应复杂网络中各节点的子图中心性的值基本保持不变,因为超边内部的节点之间的连接方式是全连接.
此外,节点103子图中心性最高,其次是节点8和94.
由此可知,无论根据度分布、超度分布或子图中心性来判断,节点103和节点94都是该超网络的核心节点.
由式(5)计算可知,该超网络的平均子图中心性为.
4QQ群超网络的小世界特性4.
1聚集系数在复杂网络中,聚集系数是度量某节点的两个邻居节点也互为邻居的平均概率.
在超网络中,聚集系数度量的是节点的邻居节点在同一个群中的平均概率,即超网络中群间构成三角形结构的密度.
经过式(3)计算可得,本文构建的QQ群超网络的平均聚集系数为0.
8142,表明该超网络的三角形密度较大,即节点的邻接节点之间存在同一个群中的可能性较高.
这种网络结构有利于信息在超网络中的快速传播.
4.
2平均路径长度衡量超网络小世界特性的另一指标是平均路径长度.
因为QQ群超网络并非是一个连通的网络且其中一个分支仅包含1表2度分布表度数量/个比例/%度数量/个比例/%270.
06791670.
0679320.
01941760.
0582430.
02911910.
0097550.
04852060.
0582620.
01942110.
00977140.
13592230.
0291820.
01942320.
01949100.
09702430.
02911070.
06792520.
01941120.
01942820.
01941260.
05839910.
00971490.
0874图3度分布图图4节点的相对度对比图图5节点的相对子图中心性对比图优先出版刘猛,等:QQ群超网络特性分析第35卷第11期个节点,所以超网络的平均路径长度表示为主连通分支中节点之间的距离.
由式(4)计算可知该超网络的平均路径长度为2.
38.
也就是说如果从起始节点向目标节点发送信息,则该信息平均只需要经过2到3个节点的转发就能达到目标节点.
综上分析,该QQ群超网络具有较高的聚类系数和较短的路径长度,表明该网络具有小世界特性.
高的聚类系数表明信息在QQ群网络中易于传播,而较短的平均路径说明节点间信息传播速度较快.
5结束语本文以用户的QQ群数据为研究对象,将用户定义为节点,QQ群定义为超边,构建了QQ群超网络.
利用矩阵理论的方法,得到了该超网络的度分布、超度分布、聚集系数、平均路径长度等拓扑指标的值.
数据分析表明该超网络的超度分布服从幂律分布,而度分布不完全服从幂律分布.
该超网络具有较高的聚集系数和较小的平均路径长度.
这些结果表明,该超网络具有小世界特性.
此外,根据节点的超度值、度值以及子图中心性大小,找出了该超网络的核心节点,并且当核心节点因受到攻击而失效时,超网络的连通性将会迅速下降.
以上分析说明,在超图基础上研究QQ群网络的拓扑特性是可行的.
本文采用的指标和方法也可用于分析其他超网络.
参考文献:[1]WattsDJ,StrogatzSH.
Collectivedynamicof'small-world'networks[J].
Nature,1998,393(6684):440-442.
[2]BarabásiAL,AlbertR.
Emergenceofscalinginrandomnetworks[J].
Science,1999,286(5439):509-522.
[3]AlbertR,BarabásiAL.
Statisticalmechanicsofcomplexnetworks[J].
ReviewsofModernPhysics,2002,74(1):47-97.
[4]NewmanMEJ.
Thestructureofscientificcollaborationnetworks[J].
ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2001,98(2):404-409.
[5]DorogovtsevSN,MendesJFF.
Evolutionofnetworks[J].
AdvancesinPhysics,2002,51(4):1079-1187.
[6]LüLin-yuan,ZhangZi-ke,ZhouTao,etal.
Recommendersystems[J].
PhysicsReports,2012,519(1):1-49.
[7]ZhouTao,RenJie,MedoM,etal.
Bipartitenetworkprojectionandpersonalrecommendation[J].
PhysicalReviewE,2007,76(4):046115.
[8]LüLin-yuan,ZhouTao.
Linkpredictionincomplexnetworks:Asurvery[J].
PhysicaA:StatisticalMechanicsanditsApplications,2011,390(6):1150-1170.
[9]陈关荣,汪小帆.
Introductiontocomplexnetworks:models,sructures,anddynamics[M].
北京:高等教育出版社,2012.
[10]ZhouTao,YanGang,WangBing-hong.
Maximalplanarnetworkswithlargeclusteringcoefficientandpower-lawdegreedistribution[J].
PhysicalReviewE,2005,71(4):046141.
[11]EstradaE,Rodríguez-VelázquezJA.
Subgraphcentralityandclusteringincomplexhyper-networks[J].
PhysicaA:StatisticalMechanicsanditsApplications,2006,364:581-594.
[12]WangJian-wei,RongLi-li,DengQiu-hong,etal.
Evolvinghypernetworkmodel[J].
TheEuropeanPhysicalJournalB-CondensedMatterandComplexSystems,2010,77(4):493-498.
[13]胡枫,赵海兴,马秀娟.
一种超网络演化模型构建及特性分析[J].
中国科学:物理学力学天文学,2013,43(1):16-22.
[14]胡枫,赵海兴,张子柯,等.
基于超图结构的科研合作网络的演化模型[J].
物理学报,2013,62(19):198901.
[15]索琪,郭进利,王福红.
电视节目竞争关系的超网络分析[J].
复杂系统与复杂性科学,2016,13(3):33-39[16]索琪,郭进利.
超网络中的舆情传播模型及仿真研究[J].
计算机应用研究,2017,34(9).
[17]索琪,郭进利.
"随机"与"择优"—超网络演化的内在驱动力[J].
复杂系统与复杂性科学,2016,13(4):51-55.
[18]郭进利.
非均齐超网络中标度率的涌现—富者越富导致幂律分布[J].
物理学报,2014,63(20):208901.
[19]孙琳,郭进利,王福红,等.
欧洲航空超网络的实证分析[J].
数学理论与应用,2015,35(2):73-82.
[20]GuoJin-li,SuoQi,JeffreyF,etal.
TheEvolutionofHyperedgeCardianlitiesandBose-EinsteinCondensationinHypernetworks[J].
ScientificReports,2016,6:33651.
[21]ZhangZi-ke,LiuChuang.
Ahypergraphmodelofsocialtaggingnetworks[J].
JournalofStatisticalMechanics:TheoryandExperiment,2010,P10005.
[22]ZlaticV,GhoshalG,CaldarelliG.
Hypergraphtopologicalquantitiesfortaggedsocialnetworks[J].
PhysicalReviewE,2009,80(3):036118.
[23]何静,郭进利,徐雪娟.
微博关系网络模型研究[J].
计算机工程,2013,39(11):105-108.
[24]樊鹏翼,王晖,姜志宏,等.
微博网络测量研究[J].
计算机研究与发展,2012,49(4):691-699.
[25]杨凯,张宁.
微博用户关系网络的结构研究与聚类分析[J].
复杂系统与复杂性科学,2013,10(2):37-43.
[26]索琪,郭进利.
在线社交网络资源评论关系超网络演化模型[J].
系统管理学报,2016,25(5):852-857.