一种基于社区结构的内外比度量方法及社区发现方法

技术领域

本发明涉及社会网络中社区发现方法,特别是一种基于社区结构的内外 比度量方法及社区发现方法。

背景技术

社会网络(SocialNetwork)可以抽象为，由节点和线段构成的集合，节 点是社会网络中的个体，线段则是个体与个体之间的某种联系关系。社会网 络具有一种社区特性，即网络中的一个子网络结构，该结构内部点与点之间 的联系紧密程度较高，而该结构与其外部邻节点的联系比较松散。社区发现 (CommunityDetection)就是找出网络中这些内部联系紧密的子网络结构。 社区发现技术有很多重要的作用，比如能用在推荐系统中，找出具有相同兴 趣爱好的人，并推荐他们可能感兴趣的产品。

传统的网络社区发现方法，需要整个网络的全局信息，即网络中所有的 点和边，再通过较复杂的计算公式得出该子网络结构的社区紧密程度。而且 对社区结构的判断，要么侧重于边与边之间的联系程度，要么侧重于点与点 之间的联系程度，没有同时平衡考虑到边和点两个方面。

社会网络的一个特点是网络会处于动态变化中，网络中节点和线段的数 量会不停变动，即网络的全局信息会动态变化，如果判断社区结构时需要全 局网络信息，那就只能在某一时刻的静态网络结构中进行计算，而不能适用 于动态社会网络。

近年来，图形处理单元GPU作为一种可适用于科学计算的并行处理硬件 平台，在并行计算方面得到了较多的应用。相对于CPU，GPU是一个高度并 行化的多线程、多核心处理器。CPU处理器把较多的硬件资源用于控制、存 储单元，擅长有复杂控制逻辑的计算，而GPU则把更多的硬件资源用于并行 计算单元，能以大量线程对大规模数据进行并行计算，适合处理计算密度高、 逻辑分支简单的计算。所以GPU更适合用来做数据规模大、数据类型统一、 数据间依赖程度低的并行计算。

如果采用传统的社区发现方法，需要先知道网络的全局信息，再进行逻 辑较复杂的计算，这样会使得整个社区发现过程的计算数据规模很大，导致 计算时间长，方法的效率不高。但是因为传统方法中数据间依赖程度高，不 适合用来在GPU并行处理平台上进行计算。

传统的社区度量标准，有中间度、模块化、传导性几种，但是这些社区 度量标准在计算时需要网络全局信息，使得计算中的通信代价较高。而且， 有些标准只是侧重于对网络中点或线一个方面的测量，因此可能导致测量不 够准确。

传统的社区度量标准中，中间度是用来间接度量社区，先计算网络中经 过某边的最短路径数量，再统计子网络结构中每个边的中间度，如果一个子 网络结构的边中间度较高，那么说明该子网络结构和外界的联系程度也比较 高，因此不是社区。可以看出，该度量标准需要全局信息，主要侧重于边的 计算，且计算逻辑较复杂。

模块化、传导性则是能直接的社区度量标准。模块化度量标准计算过程 如式2所示：

$Q=\underset{C\in c}{\Sigma }(\frac{m_c}{M}-\frac{d_c^2}{4M^2})---\left(2\right)$

M是网络中所有边的数量，m_c是社区内部中边的数量，d_c是社区中所有 点的度数。可以看出，该度量标准需要全局信息，且计算量较大。

传导性度量标准计算过程如式3所示：

$C=\frac{e_{AA}}{e_{AA}+e_{AB}}-\frac{e_A{e}_A}{e_A{e}_A+e_A{e}_B}---\left(3\right)$

该度量标准原理是把网络中的边分为三个部分，e_AA是社区内部的边，e_AB是社区的邻边，e_BB则是整个网络中剩下的未与社区有联系的边。且定义了 e_A＝e_AA+e_BB，e_B＝e_BB+e_AB。可以看出，该度量标准需要全局信息，且主要侧重 于边的计算。

传统的社区发现方法有两种类型，一种是从大的网络开始，不断进行分 割，形成小的子网络，并判断是否为社区结构。另一种是从点或小的子网络 开始，不断进行聚合，形成新的子网络，并判断是否为社区结构。

目前的社区发现方法都是基于传统的社区度量标准，因为传统的度量标 准计算逻辑较复杂，使得方法的计算效率不高，同时也不适用于快速并行计 算平台。

发明内容

本发明所要解决的技术问题是，针对现有技术不足，提供一种基于社区 结构的内外比度量方法及社区发现方法。为解决上述技术问题，本发明所采 用的技术方案是：一种基于社区结构的内外比度量方法，其特征在于，包括 以下步骤：

1)输入子网络结构G＝(V,E)，V和E分别为子网络中的点和边的 集合；定义该子网络结构的内点、内边、外点、外边；其中， 内点数量>＝4；内边的数量大于0；外边、外点的数量均大于 0；

2)定义内外比：内比InnerRatio＝内边/内点，外比 OuterRatio＝外边/外比，内外比IOR＝内比/外比；

3)根据内外比判断所述子网络结构是否为社区：因为一个子网 络结构中内边与内点的比值能反应出该子网络结构内部联系 的紧密程度，把相邻的外边与外点看成另一个子网络结构， 如果内外比IOR值大于1，即内比大于外比，可推出该子网络 结构内部的联系紧密程度大于另一个子网络结构的联系紧密 程度，得出该子网络结构内部联系紧密程度大于相邻的外部， 可以判断出该子网络结构是社区。IOR比值越大，说明社区内 部的紧密程度越高。

本发明还提供了一种基于上述度量方法的社区发现方法，包括以下步 骤：

1)输入整个网络结构N＝(V’,E’)，V’和E’分别为网络中的 点和边的集合；

2)对于所述网络结构N＝(V’,E’)中的所有节点，使用邻节点比 较方法生成一组初始子网络结构；

3)对于步骤2)生成的第一个子网络结构G＝(V,E)，利用权利要 求1所述方法计算该子网络结构的内外比IOR值，如果所述 内外比<＝1，判断出该子网络结构不是社区，记录到已检查子 网络结构的集合中，检测下一个子网络结构；

4)如果内外比>1，判断出是社区，先记录到已发现的社区集合 中，再采用双向迭代方法，一个方向是通过依次增加外点来 构成新的子网络结构，即对于该社区，如果有n个外点，则 生成n个新的子网络结构，再进入步骤5)。另一个方向是依 次减少内点来生成新的子网络结构，即依次去掉每个内点， 如果该社区有m个内点，则生成m个新的子网络结构，再进 入步骤5)；

5)对于上述一组新的子网络结构，先去掉与已检查子网络结构 集合中重复的部分，再判断是否有新的社区生成；

6)重复步骤4)和步骤5)，直到没有新的子网络结构和社区产 生；

7)对产生的所有社区按内外比IOR值大小进行倒序排序，把内 部联系紧密程度最高的社区排在最前面。

使用邻节点比较方法生成一组初始子网络结构的具体过程包括：

1)计算网络结构N＝(V’,E’)中每个节点的邻节点数量，把网络 结构N＝(V’,E’)中的所有节点，按照其邻节点数量从多到少 进行倒序排列；

2)依次对每一个节点，都加入其邻节点，组成一个子网络结构， 即网络中每一个节点都会对应生成一个子网络结构，形成一 组子网络结构；对初始化生成的这一组子网络结构进行去重， 再对每个子网络结构中的内点，按邻节点数量进行倒序排序。

与现有技术相比，本发明所具有的有益效果为：相对于传统社区结构度 量标准，本发明不需要全局网络信息，只用相邻的局部网络信息就能计算出 社区内部的紧密程度，能降低计算数据间的依赖程度，可适用于图形处理单 元并行计算硬件；本发明的邻节点比较双向迭代方法，具有更广的覆盖面， 能更快地发现内部紧密程度高的社区。

附图说明

图1是社区内外比度量标准；

图2是比邻双向迭代方法流程图；

图3是双向迭代示意图；

图4(a)是海豚社会网络拓扑图；图4(b)是社区发现示意图；

图5(a)是空手道俱乐部社会网络数据；图5(b)海豚社会网络数据；

图6是最早发现最好社区的时间占总时间的比例；

图7是社区发现搜索覆盖率。

具体实施方式

社会网络由节点和节点之间的关系构成，可以将这一场景抽象为一个无 向图，用G＝(V,E)表示，V和E分别为网络中的点和边的集合。社区发现就是 找出网络中一些内部联系比较紧密的子网络结构。

传统的社区度量标准和社区发现方法需要网络的全局信息，即判断一个 子网络结构是否为社区时，要使用整个网络的结构信息，导致计算量大，计 算逻辑复杂，不适用于快速并行计算。

因此，我们要解决的问题是给出一种不需要全局网络信息的社区度量标 准，使得数据之间的依赖程度降低，同时基于该标准提出一种适用于并行计 算的社区发现方法，提高社区发现的效率。

我们对这一问题从两个方面进行求解，首先是设计社区度量标准，然后 设计社区发现方法。

1.社区度量标准

本发明度量标准的挑战在于设计的社区度量方法，计算数据之间的依赖 程度要低，应该不再需要全局网络信息，同时又能平衡考虑网络中边和点两 种因素的关系，并能体现出社区内部联系相对紧密、外部联系相对松散的特 点。

本发明提出的内外比社区度量标准的原理如参照图1，内点是社区结构中 的所有点，最小社区的内点应该要大于4。内边是社区网络结构中的所有边， 特点是该边的两个端点都在社区内。外点是社区内点的所有邻节点。外边是 社区的所有邻边，特点是该边仅有一个端点在社区内。内比(InnerRatio)＝内 边/内点，外比(OuterRatio)＝外边/外比，内外比(IOR)＝内比/外比。

如果内外比>1，则说明内比>外比，可以反映出该子网络结构的内部联系 比外部联系紧密，并且内外比值越大，说明内部联系越紧密。

内外比社区度量标准的特点是：只需要局部网络信息，能平衡考虑点和 边的关系，计算量小，数据间依赖程度低，适合并行计算。

性能比较，内外比社区度量标准与其它度量标准的比较如表1：

表1参照图1中社区的几种度量标准结果

因为中间度是间接度量，所以不在准确度结果比较中。可以看出，参照 图1中的社区有12个点，16条边，(A，B，C，D)应为一个社区结构，但 是用模块化和传导性度量标准计算，结果都为负值，不算是社区，因为这两 种判断标准会受全局网络信息、或者偏重边或点的影响，而出现了准确度降 低的问题。但是内外比度量标准结果为1.5，仍然保持了对社区判断的正确性。

2.社区发现方法

本发明在社区发现方法的挑战，在于设计适用于快速并行计算的方法， 并且需要提高子网络结构的搜索覆盖率。

本社区发现方法发明的原理如参照图2，流程是从一组子网络结构开始， 不断迭代生成新的子网络结构并发现社区。本发明在社区发现方法的特点是 比邻排序初始化和双向迭代搜索。

本发明方法用的的社会网络数据都是公开的数据源，有空手道俱乐部数 据集，来自“Aninformationflowmodelforconflictandfissioninsmallgroups”； 有海豚数据集，来自“Thebottlenosedolphincommunityofdoubtfulsound featuresalargeproportionoflong-lastingassociations”；还有词汇关系数据集， 来自“Findingcommunitystructureinnetworksusingtheeigenvectorsof matrices”。

本发明方法的初始化部分，主要考虑把内部联系程度高的子网络结构排 在搜索队列前，这样能较早发现好的社区结构。采用比邻排序方法完成生成 一组子网络结构的初始化步骤如下：

步骤1，计算网络中每个节点的邻节点数量，把网络中的所有节点，按照 其邻节点数量从多到少进行倒序排列。

步骤2，依次对每一个节点，都把其邻节点加入组成一个子网络结构。

步骤3，对这组子网络结构进行去重，对每个子网络中的节点，按邻节点 数量进行倒序排序，初始化完成。

如参照图6，采用比邻排序方法相对于传统的随机方法，在最早发现最好 社区的时间占总运行时间的比例上，平均能提高39.64％。

方法的社区发现部分，主要考虑使用双向迭代方法，相比于传统的分割 或聚合单向搜索，能提高搜索的覆盖面，如参考图3。因为一个网络的子网络 结构组合种类太多，例如100个节点，任取50个节点构成网络，则其数量会 达到1.00891E+29，而计算机中64位无符号整数的表示范围才到 1.84467E+19，超出了10个数量级。使用完全搜索方法将会产生巨大的运算 量，而且大部分是无效搜索，所以社会网络的发现方法一般都是用不完全搜 索方法，如果能尽量提高搜索覆盖面，就更可能找出好的社区。

同时该方法基于提出的内外比的度量标准，能够有效地进行并行计算， 利用硬件平台的高效性更快地找出社区结构。步骤如下：

步骤4，对初始化后的这组子网络结构，可采用并行线程执行计算。对每 一个子网络结构，计算内外比，判断该结构是否为社区，如果不是社区则记 录到已检查结构的集合中，去检测下一个子网络结构；

步骤5，如果是社区，先记录到已发现的社区集合中，再采用双向迭代方 法，一个方向是通过依次增加邻边来构成新的子网络结构，另一个方向是依 次减少内边来构成新的子网络结构，生成一组新的子网络结构。

步骤6，对于新产生的一组子网络结构，先去掉与已检查结构集合中有重 复的部分，再判断是否有新的社区生成，重复迭代判断的过程，直到没有新 的子网络结构和社区产生。

步骤7，最后对产生的所有社区按内外比值大小进行倒序排序，定义一个 内外比阈值，找出内部联系紧密程度高的社区。

本发明方法的性能比较：

图4(a)是海豚社会网络拓扑图；图4(b)是经过本发明的社区发现方法后， 找出的内外比最高的社区。

图5(a)和图5(b)是比较不同社区发现方法，看是否能发现社区内外比最高 的社区，也能从侧面验证是否有更高的搜索覆盖率，图5(a)是空手道俱乐部 社会网络数据，图5(b)海豚社会网络数据，可以看出，比邻双向迭代方法相 比传统方法，能够发现有最高内外比的社区。

图7是比较几种搜索方法，在不同社会网络数据中，社区发现搜索覆盖 率，覆盖率越高，表示搜索的子网络结构越多，结果也就越准确，计算得到 双向迭代方法的搜索覆盖面最高，平均能提高12.67％。

本发明提出的内外比度量标准，实现了在只需要部分相邻网络信息的情 况下，更准确、更平衡地度量社区的连接程度特性，并且计算数据间依赖程 度低，适合并行计算；同时提出的比邻双向迭代社区发现方法，能够更快、 更全面地发现更好的社区，在最早发现最好社区的时间占总运行时间的比例 上，平均能提高39.64％；在子网络结构搜索覆盖面上，平均能提高12.67％。