基于多维混合图和核心节点的社团发现算法
2019-07-08祝周石琳孔祥顺
祝周 石琳 孔祥顺
摘 要：社区发现和好友推荐算法一直是复杂网络的研究热点之一，在公安业务工作、网络舆情控制、电子商务等领域具有重要的意义。为解决公安工作中防范恐怖主义事件、打击易复发类犯罪、稳控重点群体等突出难题，论文提出了一种基于核心种子节点扩展的启发式社团发现算法。该算法通过有效融合多维信息形成混合图，以种子节点作为初始社区，综合考虑人物节点间不同交互行为和关联行为的权重，依托实战重点将协同过滤、Tanimoto系数、六度空间理论等算法相结合，最后把社区邻接节点中的活跃节点降序排列作为重点社团目标，得到了一种有核心节点的基于“人、事、地、网、组织”五维混合图的社团发现数据模型，为警务大数据及其他应用提供支撑。
关键词：混合图;核心节点;链接度;社团发现
中图分类号：TP391 文献标识码：A
Community detection method based on multidimensional mixed graph and core nodes
Zhu Zhou， Shi Lin， Kong Xiangshun
（Anshan Public Security Bureau of Liaoning， LiaoningAnshan 114000）
Abstract： Community detection and friend recommendation algorithms have always been one of the research hotspots in complex networks. It is of great significance in the field of public security business， network public opinion control， electronic commerce and other fields. To solve the problems of preventing counter-terrorism， combating the recurrence of crime and stabilizing key groups， this paper presents a heuristic community detection method based on core seed nodes extension. The method effectively fuses multidimensional mixed graph， and it considers user interaction and association behavior weight comprehensively. Seed nodes are used as the initial community. Relying on the actual combat， we focus on the combination of collaborative filtering， Tanimoto coefficient， Six Degrees of Separation and other algorithms. Finally， the active nodes in the neighboring nodes of the community are ranked in descending order as the key community targets. A data model of community detection based on five-dimensional mixed graph of people， events， places， networks and organizations with core nodes is obtained. It provides support for police big data and other applications.
Key words： mixed graph; core nodes; link degree; community detection
1 引言
近年來，以手机[1]、微信、微博等社交网络（Social Network）为代表的社会媒体逐渐成为人们日常生活中重要的交流平台，呈现出独特的网络特征[2]，现实与网络已难以分割。由于社交网络平台的多样性、隐匿性和开放性等原因，导致公安机关在解决防范恐怖主义事件、打击易复发类犯罪、稳控重点群体等突出问题时难上加难。如何充分利用互联网社交网络关系数据，虚实结合、挖掘目标、发现社团、获取情报、查找重心，已成为当前基层公安工作的一项非常重要的业务需求[3]。通过研究社团中已知人员目标，分析其多种社交网络工具产生的虚实数据，引入多维关系云图、核心节点、链接度等概念，重点将协同过滤[4，5]、Tanimoto系数等好友推荐及社团发现算法相结合，以期得到一种有核心节点的基于“人、事、地、网、组织”五维混合图的社团发现数据模型。
2 相关研究
在基层警务工作中，通过已知目标挖掘其重要关系人[6]，要面对多种社交网络工具产生的具有稀疏性和多样性的数据信息，分析过程极其复杂，受工作意识、技战术水平等制约，个人需求难以得到满足，因此如何利用多种社交网络信息快速发现潜在的工作目标成为巨大挑战。在传统的根据社交网络图计算用户相似度的方法中， 或直接计算目标相似度而较少考虑好友的影响，或者将所有好友赋予相同权重， 即考虑了关系数量却没有区分重要性。
目前，流行的推荐方法基于一个假设：两个用户越相似，则他们越有可能成为朋友。有三种主要的方法刻画用户的相似度：基于用户的属性特征、基于网络结构的局部特性和基于网络结构的全局特性。
（1）基于用户属性特征的方法进行朋友推荐[7]的思想是通过机器学习的手段，分析出不同类型的属性对用户的贡献度不同，将其分类处理。基于该分类，提出的算法可以在掌握用户基本资料以及近期行为的基础上，搜索出与之相关性更强的好友或能够引发其兴趣点的商品，用来快速、准确、全面地得到用户与其好友之间亲疏程度排序及分类的结果，如果两个用户具有相同的年龄、性别、学校或者地点等，则他们更加相似，也就更加可能成为朋友。
（2）基于网络结构的局部特征的方法利用用户朋友网络结构的局部结构信息。有很多局部相似性测量指标[8]，如共同邻居（Common Neighbor，CN）、Jaccard和Adamic/Adar等。CN也叫FOAF算法，被很多流行的OSNs所采用。它考虑两个顶点的共同邻居的数量，如果两个用户的共同朋友越多，则他们越可能形成链接。设N（x）表示顶点x的邻居的集合，则顶点x与y的相似性为：。Jaccard方法不仅考虑了共同邻居的数量，还考虑到两个用户拥有的邻居数量，即 。Adamic/Adar也考虑两顶点共同邻居的度信息，并且认为度小的共同邻居节点的贡献大于度大的共同邻居节点，根据共同邻居节点的度为每个顶点赋予一个权重值，该权重等于该顶点的度的对数的倒数，，一些研究表明，Adamic/Adar在局部特性指标中具有最好的性能[9]。
（3）基于网络全局特征方法侦测朋友社交网络的所有路径的结构，其中Google网页排序算法PageRank的拓展算法——重启动随机游走算法（Random Walk with Restart，RWR）吸引了很多研究领域学者的兴趣。RWR算法[10，11]是一个基于图的随机游走马尔科夫链模型。相比于其他的相似性算法，RWR方法具有捕捉图形全局结构以及顶点之间多侧面关系等优点。
上述方法仅利用社交网络中用户朋友网络信息，而在社交网络数据中常常包含多种对象和网络关系[12]。本文以推荐算法来挖掘重要关系人，扩展了单项网络关系，基于多子网复合复杂网络[10]，融合了多种关系，引入链接度[13，14]来描述目标的相似度，得到与核心节点的核心链接度来确定重点目标。
3 基于多子网复合复杂网络的社团发现算法
3.1 基本思想
社交关系网络是多维网络，包含多种对象与网络关系，对象之间的网络关系受多种因素的影响。本文将对象之间多种关联行为划分为交互类和关联类，构建各类型的单一关系网络，以关系人物为节点将多个子网复合成复杂的关系网络云图，借用了社团发现的局部节点模型[13]、好友推荐的共同邻居模型、文本分类的向量空间模型等数据模型，定义了关系云图、核心节点、链接度等概念[13，14]，结合实战对不同的边设置了不同权重，再使用协同过滤、Tanimoto系数、六度空间[15，16]等理论算法计算链接度，最后分析与核心种子节点社区相邻接的活跃节点链接度数值关系，锁定重点目标或划出社团。
3.2 多子网关系云图构建
基于社交网络全局特征来表达网络中所有可能的结构，定义一个以关系人物为节点的多子网关系云图[10]，融合多种对象和多种关系，使结果能够真实反映对象间的交互度和相似度，具体分为六个步骤。
（1）构建核心节点的社交网络数据仓库。从互联网多渠道抽取社交网络工具数据信息、从电信运营商若干电信通讯基站抽取通讯记录数据信息[1]、从公安管理以及其他方法获取的虚实数据信息，清洗后作为数据源。
（2）利用数据源中人物与人物之间的关联，组织与人物之间的关联，位置与人物之间的关联，考虑整个网络中各节点之间的联系，组建关系云图G，以G=（V，A，E）表示。
（3）V表示节点集合，包含四种类型节点Vu、Vc、Vp、Vt。其中，Vu为人物节点集合，Vc为人物参加的组织节点集合，Vp为位置节点集合，Vt为各类型顶点集合，即V=Vu∪Vc∪Vp∪Vt。因数据来源不一，人物使用的各类社交网络工具不具有唯一性，人物节点的各属性并非齐备完整，人物节点的唯一标识使用独立的唯一标识，而不使用身份证、社交网络工具ID等属性类标识。
（4）A是人物节点的属性集合，其中，AVi为人物节点Vi所拥有的属性集合。现主要包含六种类型顶点Ac、At、Asn、Aid、Axm、Asfz。其中，Ac为组织属性，At为手机号码属性，Asn为社交网络工具属性，Aid为人物唯一标识属性，Axm为姓名属性，Asfz为身份证号码属性。各人物节点的社交工具种类及号码、手机号码等可能有多个，因而其属性记录的数据也并非唯一值，假设人物节点Vi有Numx种社交工具及相应号码，有Numy个手机号碼，参加了Numz个组织或圈子，则Avi={Aid∪Asfz∪Axm∪Acz∪Asnx∪Aty，Numx |Asn|，Numy |At|，Numz |Ac | }。
（5）E是边的集合，主要边的类型有Esnj、Ecj、Etk、Ep。其中，Esnj为社交网络工具好友关系集合，如果人物Vu1和Vu2之间存在好友（含关注）联系，每增加一种社交网络工具好友则相应增加一条关系边。Ecj为关系人组织群体关系集合，如果人物Vu1和Vu2之间存在相同的组织群体（含圈子、群组）联系，每增加一个相同的组织群体，则相应在两个人物节点与组织节点之间分别增加一条关系边。Etk为关系人手机通讯关系集合，如果节点Vu1和Vu2之间存在手机通讯联系，每增加一种（非一次）手机通讯关系则相应增加一条关系边。Ep为关系人位置交互关系集合，如果人物节点Vu1和Vu2之间存在相同的位置联系，每增加一个相同的位置则相应分别增加一条关系边，Ep包含现实位置关系与虚拟位置关系两种情形。
（6）关系云图中有的关系边是有向的，有的是无向的，因此统一成一个有向图，将无向边表示为两条有向弧，各关系边都是带有权值的。
3.3 关联类相似度加权网络构建
关系云图的拓扑结构，仅表示个人在社会交往中的范围，连接节点的边越多表示这个人的交际范围越广，但是很难准确分析与其关系最密切的人是谁。现实中各种社交网络工具边上的权重具有非常重要的意义，亲密度不同的人物之间，所存在的社交网络工具边的数量及种类有很大区别，而边权越大关系越密切。本文构建了交互加权网络作为基础网络，主要方法如下。
（1）归一化处理每一条边上的权值，使其取值范围为（0，1）。
（2）结合工作实际，使用层次分析法创建各节点之间虚拟属性边的重要度矩阵，得出各虚拟边弧的权值。
（3）主要計算各类社交网络工具边权、各类手机通讯边权、各类组织圈子关系[17]边权等关联虚拟类边权。
（4）Wij代表两个人物节点Vi和Vj之间的各类虚拟边（非位置类边）的权重总值，即为两个人物节点间各类虚拟非位置边权的总和。
（5）位置类边权值因作用特殊另行计算。
3.4 交互类虚拟位置相似度计算
基于位置的社交网络服务是利用GPS、蜂窝网、WLAN等技术获得移动终端的地理位置信息，支持用户随时随地自由记录并分享地理位置等信息。而位置维度的社团发现，可根据社交网络服务或其他方法获取的地理位置信息，借用文本分类的向量空间模型[18]。即以位置向量来描述人物，将每个位置作为向量空间坐标系的一维，人物被形式化为多维空间向量中的一个向量。在多维向量空间模型中，使用TF-IDF权重计算方法计算某一维向量值，而人物节点的位置相似度用Tanimoto系数进行计算，主要方法如下。
（1）位置向量包含基站位置和IP地址两类数据，即以基站和IP地址作为核心数据。
（2）标准化处理的传统的TF，以nfiL表示人物i在位置L出现的频数，以Pi表示人物i的位置集合，以表示人物i在所有位置中频数的最大值，公式如下：
（3）修正并规范后的IDF，以表示人物i的位置集合中所有频数的和，fiL表示人物i的位置L在人物i位置集合中的频率，fjL表示人物j的位置L在人物j位置集合中的频率，公式如下：
（4）为解决数据稀疏及单一性问题，结合实战以提升位置频数对实际相似度的影响准确率，本文对fiL=1时的频数nfiL进行归一化处理以hiL表示，以WiL表示人物i向量在位置L维度上的向量值，也是人物节点i与位置节点L间边的权重，公式如下：
（5）使用Tanimoto系数计算人物节点i和j的虚拟位置相似度Psim （Vi，Vj），公式如下：
3.5 交互类现实位置相似度计算
如果关系云图中人物节点之间存在公安工作或其他方式获取的现实位置数据边Ep，要单独计算其现实位置相似度。现实位置相似度[19]是反映两个人物节点相似性最重要的指标，因为其代表了两个人物曾在同一时间、同一地点发生过极为亲密的行为。本文在此项计算中使用了指数函数，两个人物如果仅有几次交集，可能是偶然行为，但随着近期内现实交集行为的数量增多，就更有可能有着相似的工作生活圈，因此相似度应该随着交互行为数量的上升而上升，并且上升趋势是先慢后快。人物i和j的现实位置交集频数用Lij表示，将Lij+0.01作为分母视为收缩参数，对数据归一化处理，利用指数函数算法，常数e约为2.71828，则人物节点i和j的现实位置相似度Lsim （Vi，Vj），公式如下：
3.6 链接度的定义
在关系云图中，综合衡量拓扑结构和各节点之间边权，本文定义了两个人物节点Vi和Vj间的链接度Vsim （Vi，Vj），来描述各人物之间的相似度。由于社交网络具有小世界特性[20]，大部分节点可以从其他任一节点经少数几步到达。即使两个节点没有直接相连或者没有共同邻居节点，他们之间仍然存在某种联系，这种联系通过节点之间最短路径进行传递。因此，对于直接相连的人物，他们的相似度与彼此之间路径的权重以及与共同好友的权重相关;对于不直接相连的人物，他们的相似度为他们之间的最短路径上所有节点对的相似度的乘积，路径越长，相似度越低。当存在多条最短路径时，取乘积较大者作为他们的相似度。根据六度分隔理论[15，16]，世界上任意两人之间所间隔的人数平均不超过六人。因此，当两个人物节点之间路径长度大于 6 时，则认为他们的紧密程度近似为零。以Ni和Nj分别代表人物节点i和节点j的邻居节点集合，以pathij表示人物节点i和节点j之间的最短路径。用户节点之间的链接度Vsim （Vi，Vj）及用户节点Vi与其他节点Vx（非人物节点）之间的权值Vsim （Vi，Vx）算法定义如下：
（1）Vi，Vj相邻
（2）
（3）
（4）
3.7 总链接度和核心链接度的定义
根据警务实战，分别将人物节点i和j之间的位置等属性边权值与链接度赋予权重α进行计算，得到人物节点i和j的总链接度Tsim （Vi，Vj）。以Vk表示核心节点集，为获取以核心节点为中心的社团，用核心链接度Csim （Vi）表示人物节点i到各不同权重β的核心节点的总链接度之和，如暂无经验权重则默认取1，可通过机器学习，逐步获取各经验权重，具体公式如下：
（1）
（2）
3.8 算法设计
输入：关系云图G=（V=Vu∪Vc∪Vp∪Vt，A=Ac∪At∪Asn∪Aid∪Axm∪Asfz，E=Esnj∪Ecj∪Etk∪Ep），核心节点集Vk，各类案事件权重调节参数α和各核心节点的权重调节参数β。
输出：按核心链接度降序排名各关系人物列表。
方法：
（1）输入待分析的核心节点集Vk及其对应的关系云图G，并设定好相关权重参数;
（2）迭代计算每一个节点的相关属性的关联度，以增减节点;
（3）计算G中每一个人物节点的交互类虚拟位置相似度;
（4）计算G中每一个人物节点的交互类现实位置相似度;
（5）计算G中每一个人物节点的链接度;
（6）根据（3）（4）（5）的结果计算各人物节点的总链接度;
（7）根据（6）的总链接度计算各人物节点的核心链接度;
（8）将各节点的核心链接度降序排列，据此确定各人物节点与核心节点间的相互关系，划分重点目标与社团。
3.9 算法实验
本文对社交网络工具数据、通讯记录数据以及其他方法获取的虚实数据信息进行了模拟，建立实验数据集来测试算法的准确性和可操作性。实验在Windows Server 2008 R2的环境下使用Python语言运行。
（1）實验构建了四次某犯罪团伙三个已知目标的社交网络虚实数据仓库。
（2）利用层次分析法确定了社交网络工具微信边权Wsnwx=0.34，社交网络工具微博边权Wsnwb=0.16，手机通讯记录边权Wt1=0.34等。
（3）将数据仓库内的数据输入算法形成关系云图，并将权重调节参数α1、α2、α3、β均赋值为1。
（4）利用本文中多维混合图和核心节点的社团发现算法对四次实验数据进行了分析挖掘，与人工分析出的犯罪组织重点人员为参照，均成功的按核心链接度的高低挖掘出犯罪团伙中的重点人员，准确程度在88%以上。
4 总结与展望
本文算法的实现包括模型构建和算法设计。在阐述各个模块构建过程中，详细介绍了关系云图的构建和各类权重计算及设置方法，在云图的构建中为了充分反映人物多种社交网络工具的关系特征，精准预测其关联性，综合考虑了多种类虚实边关系。在权重设置中，根据云图中顶点的关联度和交互度，借用好友推荐的共同邻居模型、文本分类的向量空间模型等赋予人物社会化行为相应的权重。最后利用核心链接度准确计算关系云图中各人物节点的与初始核心节点间的关联相似度，得出最终人物推荐列表以锁定团伙目标。
此模型研究是将多种传统警务技战法及大数据社会网络分析研究领域进行深度融合的一种尝试，需要紧紧依托于公安大数据的发展，存在不足之处。首先，混合图中的节点包括人物、位置、圈子等多种类型，算法的空间消耗很高。其次，本文提出的基于混合图的各综合算法仍赋予了链接度大的人物过大的挖掘推荐强度，对于某些链接度小但更为重点的特殊人物节点挖掘多样性不高。在今后的研究中，应当从数据挖掘角度进一步在发现社团、研究社团内部交互模式以及预测社团的模型上进行深入广泛的分析和探讨，逐步探索扩展六度空间理论的多层次关系，积累各类案事件不同的权值，特别要提高一些链接度小的特殊关键目标人物推荐强度，提高算法的准确性。
5 结束语
针对目前社会网络环境及各类个性化通讯服务现状，结合警务工作实际，本文提出基于社交网络及通讯痕迹中人物关联关系视角下的分析模式，参考OSNs中主流的推荐算法，设计了一种基于复杂混合图的社团挖掘算法模型，将各种社交网络及通讯痕迹中的人物关系网络和位置等社会化交互行为融入模型，更有效地解决了公安工作中快速挖掘重点目标和社团问题。
参考文献
[1] 高建强，谭剑，崔永发.一种基于通讯痕迹的社会网络团伙分析模型[J].计算机应用与软件，2012，29（3）：206-208.
[2] 刘小玲，谭宗颖.复杂网络社团结构划分算法的情报学应用研究[J].图书馆学研究，2011，（8）：20-25.
[3] 杨莉莉，杨永川.基于社会网络的犯罪组织关系挖掘[J].计算机工程，2009，35（15）：91-93.
[4] Das A， Datar M， Garg A， et al. Google News Personalization： Scalable Online Collaborative Filtering[C].In： Proceedings of the 16th International World Wide Web Conference. New York： ACMPress， 2007， 272-280.
[5] Linden G， Smith B， York J. Amazon.com Recommendation： Item-to-Item Collaborative Filtering[J]. IEEE Internet Computing， 2003， 7（1）：76-80.
[6] 樊梦佳，钮艳，杜翠兰，等.一种基于聚集系数的社区发现算法[J].计算机工程与科学，2016，38（2）：363-369.
[7] 过云燕，王宏志，张玮奇.社交网络中基于分类属性的好友推荐[J].计算机工程与应用，2015，51（12）：99-106.
[8] 施少怀.一种基于用户倾向的微博好友推荐算法[D].哈尔滨：哈尔滨工业大学，2013.
[9] Liben-Nowell D， Kleinberg J. The Link-Prediction Problem for Social Networks [M]. John Wiley & Sons， Inc. 2007， 58， 1019-1031.
[10] 俞琰，邱广华，陈爱萍.基于混合图的在线社交网络朋友推荐算法[J].现代图书情报技术，2011，（11）：54-59.
[11] Tong Hanghang， Faloutsos Christos， Pan Jiayu. Fast Random Walk with Restart and Its Applications[C]. In： Proceedings of the 6th International Conference on Data Mining （ICDM06）. 2006， Washington， DC. USA： IEEE Computer Society， 2006： 613-622.
[12] 吕润桃，赵金考，李钰，等.异质社交网络中多通道特征融合的好友推荐模型[J].激光杂志，2014，35（12）：107-111.
[13] 张瑜，蔡国永.基于局部思想的在线社区划分算法[J].微型机与应用，2013，32（13）：76-79.
[14] 解，汪小帆.复杂网络的一种快速局部社团划分算法[J].计算机仿真，2007，24（11）：82-85.
[15] 朱亚丽.“六度分离”假说的信息学意义[J].图书情报工作，2005，49（6）：59-61.
[16] 刘宏杰，陆浩，张楠，等.基于微博的六度空间理论研究[J].计算机应用研究，2012，29（8）：2826-2829.
[17] 王玙，高琳.基于社交圈的在线社交网络朋友推荐算法[J].计算机学报，2014，37（4）：801-808.
[18] 贺超波，汤庸，陈国华，等.面向大规模社交网络的潜在好友推荐方法[J].合肥工业大学学报，2013，36（4）：420-424.
[19] 符饶.基于位置服务的潜在好友推荐方法[J].软件，2015，36（1）：62-66.
[20] 许为，林柏钢，林思娟，等.一种基于用户交互行为和相似度的社交网络社区发现方法研究[J].信息网络安全，2015，（7）：77-83.
