３８ ２０１３，４９（１７） ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 复杂网络局部社区挖掘的节点接近度算法 方平１，３，４李芝棠２，３，４涂浩 一，郭正彪 ＦＡＮＧ Ｐｉｎｇ ＇ 一，ＬＩ Ｚｈｉｔａｎｇ ， 。。，ＴＵ Ｈａｏ ，ＧＵＯ Ｚｈｅｎｇｂｉａｏ ， １．海军航空工程学院青岛校区，山东青岛２６６０４１ ２．华中科技大学网络与计算中心，武汉４３００７４ ３．华中科技大学计算机科学与技术学院，武汉４３００７４ ４．华中科技大学下一代互联网接入系统国家工程实验室，武汉４３００７４ １．Ｑｉｎｇｄａｏ Ｂｒａｎｃｈ，Ｎａｖａｌ Ａｅｒｏｎａｕｔｉｃａｌ ａｎｄ Ａｓｔｒｏｎａｕｔｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｑｉｎｇｄａｏ，Ｓｈａｎｄｏｎｇ ２６６０４ １，Ｃｈｉｎａ ２．Ｎｅｔｗｏｒｋ Ｃｅｎｔｅｒ，Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ ４３００７４，Ｃｈｉｎａ ３．Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ ４３００７４，Ｃｈｉｎａ ４。Ｎａｔｉｏｎａｌ Ｅｎｇｉｎｅｅｒｉｎｇ Ｌａｂｏｒａｔｏｒｙ ｆｏｒ Ｎｅｘｔ Ｇｅｎｅｒａｔｉｏｎ Ｉｎｔｅｒｎｅｔ Ａｃｃｅｓｓ Ｓｙｓｔｅｍ，Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｗｕｈａｎ ４３００７４，Ｃｈｉｎａ ＦＡＮＧ Ｐｉｎｇ，ＬＩ Ｚｈｉｔａｎｇ，ＴＵ Ｈａｏ，ｅｔ ａ１．Ｃｌｏｓｅｎｅｓｓ ｄｅｇｒｅｅ ｏｆ ｎｏｄｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｉｎｉｎｇ ｌｏｃａｌ ｃｏｍｍｕｎｉｔｙ ｆｒｏｍ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ，Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２０１３，４９（１７）：３８－４２． Ａｂｓｔｒａｃｔ：Ｔｏ ｍａｋｅ ｔｈｅ ｌｏｃａｌ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｆａｓｔｅｒ ａｎｄ ｍｏｒｅ ａｃｃｕｒａｔｅ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｌｏｃａｌ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅｓ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｂａｓｅｄ ｏｎ ｃｌｏｓｅｎｅｓｓ ｄｅｇｒｅｅ ｏｆ ｎｏｄｅ．Ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ，ｗｈｉｃｈ ｕｓｅｓ ｔｈｅ ｍａｘｉｍａｌ ｃｌｏｓｅｎｅｓｓ ｄｅｇｒｅｅ ｏｆ ｎｏｄｅ ａｎｄ ｔｈｅ ｌｏｃａｌ ｃｏｍｍｕｎｉｔｙ’Ｓ Ｑ ｖａｌｕｅ，ｓｔａｒｔｓ ｆｒｏｍ ｔｈｅ ｍａｘｉｍｕｍ ｄｅｇｒｅｅ ｎｏｄｅ ｏｆ ｔｈｅ ｎｅｔｗｏｒｋ ａｎｄ ｄｅｔｅｃｔｓ ｔｈｅ ｃｏｍｍｕｎｉｔｙ ｉｔ ｂｅｌｏｎｇｓ ｔｏ ｂｙ ｓｅａｒｃｈｉｎｇ ｔｈｅ ｎｅｉｇｈｂｏｒ ｎｏｄｅｓ．Ｉｔ ｉｓ ａｌｓｏ ａｐｐｌｉｃａｂｌｅ ｆｏｒ ｇｌｏｂａｌ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｄｅｔｅｃｔｉｎｇ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｏｎ ｔｗｏ ｔｙｐｉｃａｌ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ｍｉｎｅ ｔｈｅ ｉｎｔｒｉｎｓｉｃ ｌｏｃａｌ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃ— ｔｕｒｅ ｉｎ ｎｅｔｗｏｒｋｓ．Ｔｈｅ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ Ｏ（ｎｌｏｇ（ｎ））ｏｎ ａ ｓｐａｒｓｅ ｇｒａｐｈ，ｗｈｅｒｅ，２ ｉｓ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｎｏｄｅｓ． Ｋｅｙ ｗｏｒｄｓ：ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ；ｌｏｃａｌ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ；ｃｌｏｓｅｎｅｓｓ ｄｅｇｒｅｅ ｏｆ ｎｏｄｅ 摘 要：为了准确、快速地发现大规模复杂网络中的局部社区，提出了一种基于节点接近度的局部社区发现算法。该算法 以最大度节点作为起始节点，利用节点接近度和局部社区Ｑ值不断搜索其邻居节点，将接近度最大的节点加入初始社区 形成新的初始社区；同时，该算法也可以应用于复杂网络全局社区结构的划分。对２个典型复杂网络进行了局部社区挖掘分 析，实验结果表明，该算法能够有效识别隐藏在实验网络中的局部社区。针对稀疏网络，该算法的时间复杂度为Ｏ（ｎｌｏｇ（ｎ））， ｎ为网络节点数。 关键词：复杂网络；局部社区发现；节点接近度 文献标志码：Ａ ｌＩ｜图分类号：ＴＰ３１１ ｄｏｉ：１Ｏ．３７７８￣．ｉｓｓｎ．１００２—８３３１．１２０４—０３１６ ｌ 引言 近年来复杂网络已经得到了广泛的应用，如在线社会 够在大型复杂网络中快速发现“社区”具有重要的实际应 用价值，如在线社会网络中的社区可能代表的是根据共同 网络、科学家合作关系网等，但目前复杂网络还没有精确 严格的定义。随着对复杂网络性质的物理意义和数学特 性的深入研究，发现很多实际网络中存在社区结构，即整 个网络由若干个社区构成，每个社区内部节点之间的连接 相对紧密，但各个社区之间的连接相对来说比较稀疏。能 爱好而形成的真实的社会团体。 如何在复杂网络中进行正确的社区划分成为当前复 杂网络研究中的一个热点。为了寻找复杂网络中的社区 结构，研究人员提出了多种全网络的社区划分算法，例如 ＷＨ算法 、ＦＮ算法 、ＧＡ算法 等。然而，当网络规模过 金项Ｈ：高校基本科研业务费专项资金资助（Ｎｏ．２０１ｌＪＣ０６７）；中匡ｌ下一代互联网示范工程（Ｎｏ．ＣＮＧＩ２００８—１２２）。 作者简介：方平（１９８Ｏ一），男，硕士研究生，研究方向为网络安全；李芝棠（１９５１－－），男，教授，博士生导师，主要研究领域为计算机网络、网 络安全等；涂浩（１９７７一），男，博士，讲师，主要研究领域为计算机网络、网络安全等；郭正彪（１９８３一），男，博士，研究方向为在 线社会网络、复杂网络、Ｐ２Ｐ系统、网络安全等。Ｅ—ｍａｉｌ：ｐｉｎｇ＠ｈｕｓｔ．ｅｄｕ．ｃｎ 收稿ｎ期：２０１２—０４—１８ 修回日期：２０１２－０８—３１ 文章编号：１００２ ８３３１（２０１３）１７－００３８—０５ ＣＮＫＩ山版Ｉ＿＿１期：２０１２—０９—１８ ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／１１．２１２７．ＴＰ．２０１２０９１８．１０２６．００３．ｈｔｍｌ 方平，李芝棠，涂浩，等：复杂网络局部社区挖掘的节点接近度算法 Ｑ（Ｃ）＝ Ｅ （Ｃ） Ｅ （Ｃ一｛ｆ）） Ｅ （Ｃ）＋Ｅ。 （Ｃ） Ｅ （Ｃ一｛ ｝）＋Ｅ。 （Ｃ一｛ｆ｝） ｆ４） 于庞大时，获得全局信息非常困难，特别是不断动态变化 的网络，如互联网，另外，在很多情况下，研究人员关注的 是网络的局部社区结构，例如，在社会网络中搜索时通常 只关心某些具有重大影响力的人所在的社区，而不需要了 解整个社会网络的社区结构，在这种情况下，就不需要耗 时划分网络的全局社区结构，而只需搜索网络中某个局部 社区。 其中ｉ为最后加入社区ｃ的节点或节点集， ｃ１为２时，令Ｑ（Ｃ）＝１。 （ｃ）为社区 ｃ与社区ｃ外部的连接数，Ｅ （ｃ）为社区ｃ内部的边数；当 ３算法描述 本文算法以最大度节点为起始节点，计算其邻居节 近期，研究者提出了多种局部社区发现算法，例如文 献［４】提出了一种基于Ｈｕｂ的挖掘社区结构的方法，该算法 点，找到与最大度节点拥有最多共同邻居节点的节点，以 需要事先知道网络社区的数目，而在现实网络中很难事先 知道网络社区的数目；文献［５］提出了寻找某个节点所在社 区结构的局部方法，称为ＢＢ算法，该算法缺陷在于它把社 区整个一层邻居节点全部加入或全部排除在社区之外。 ２００５年，Ａａｒｏｎ Ｃｌａｕｓｅｔ提出“局部模块度”概念 ，即以最大 化模块度为目标来搜索局部社区。文献［７］提出了最大节 点接近度定义，通过不断聚集邻居节点，直到找到所期望 的尼个社区成员；文献［８］定义了连接相关度△ｃ，提出了一 种基于节点聚集系数性质的局部社区划分算法。 本文提出一种局部社区划分的新算法，通过网络中最 大度节点开始寻找其所在社区，搜索其邻居找到与其共享 邻居最多的节点形成初始局部社区，再搜索局部社区的邻 居节点，选择与局部社区接近度最大的节点加入局部社 区，最终根据社区Ｑ值得到结果局部社区。该算法也可用 于全局社区划分，即利用该算法寻找剩余网络节点中的局 部社区，重复此过程，即可得到网络的全局社区结构。 ２ 定义 令Ｇ＝（ ，Ｅ）表示具有ｎ个节点、ｍ条边的无向无权复 杂网络。其中， 表示网络节点的集合，Ｅ表示网络连接 的集合，Ｃ为一局部社区网络节点的集合，ＩＣｌ为Ｃ的节点 数，以下列出与本文算法相关的概念及定义： 定义１（邻居节点集）节点ｉ的邻居节点集定义为： Ｎ（ｉ）＝ 节点，与节点ｉ直接相连｝。 具有ｎ个节点的局部社区Ｃ的邻居节点集定义为： ｎ ｎ Ⅳ（ｃ）＝ＵＮ（ｉ）一Ｕｆ （１） ｆ＝１ ｆ＝１ 定义２（共享邻居数）对于Ｇ中的节点 和其邻居节点 ，的共享邻居数定义如下： Ｗ（ｉ， ＝ＩＮ（ｆ）ｎⅣ（ （２） 定义３（节点接近度）节点接近度是指节点ｉＮ局部社 区ｃ的接近程度。节点ｉ的接近度定义如下： Ｆ（ｉ，Ｃ）＝ － ∑ｄ （３） ｉＥＮＩｃ），ｊ∈Ｃ 其中ｉ∈Ⅳ（ｃ），Ｋ 表示节点ｉ的度数， “表示节点ｉ与社 区Ｃ内部节点的连接数，ｄ 表示节点ｉ与节点Ｊ之间的最 短路径。Ｆ（ｉ，Ｃ）值越大，表示节点ｉ与社区Ｃ连接越紧密。 定义４（社区Ｑ值） 此２个节点组成初始社区，再计算初始社区的各邻居节点 接近度，取接近度最大的节点加入初始社区形成新的初始 社区，同时计算新的初始社区的Ｑ值，循环以上过程，直到 形成新的初始社区Ｑ值大于０。 算法描述如下： 输入网络Ｇ：＜Ｖ，Ｅ＞ 输出网络Ｇ的一个局部社区结构 步骤１找到 中度最大的节点ｖ 及其邻居节点集Ｎ（ｖ ）， ＝Ｖ—Ｖ。。 步骤２利用公式（２），在Ｎ（ｖ ）中找到与最大度节点ｖ 共享邻居最多的节点ｖ ，令初始局部社区ｃ＝ｖ ＋ｖ ， ＝ 一ｖ ，Ｑ（Ｃ）＝１。 步骤３利用公式（１），得到Ⅳ（ｃ），利用公式（３），计算 Ｎ（Ｃ）中每一节点的接近度，加入接近度最大的节点ｖ 到 社区Ｃ，Ｃ＝ｃ＋Ｖ ， ＝ —ｖ ，利用公式（４），计算Ｑ（Ｃ）；循 环此步骤，直至Ｑ（ｃ）＞０或 为空。 步骤４输出结果。 由式（３）可以看出，节点接近度的计算与新加入节点 的连接数以及节点间的最短路径有关，本文采用ＤＯｋｓ￣ａ 算法计算节点间的最短路径，该算法计算单源节点最短路 径的时间复杂度为Ｏ（ｍ ｌｏｇ（ｎ）），ｍ为网络的总边数，ｎ为网 络的节点数，因此，计算节点接近度的时间复杂度为 Ｏ（ｄｍ ｌｏｇ（ｎ）），ｄ为节点的平均度；在式（４）中，Ｑ（ｃ）的计算 只与社区内外部的连接数有关，计算Ｑ（Ｃ）的时间复杂度为 Ｏ（ｄ），因此，本文算法的时间复杂度是Ｏ（ｄｍｌｏｇ（ｎ））＋ Ｏ（ｄ）＝Ｏ（ｄｍｌｏｇ（ｎ））。现实世界中的网络通常是稀疏网络， 即ｍ＝ｐ（ ），因而本文算法在识别稀疏网络局部社区时的 时间复杂度为Ｏ（ｎ ｌｏｇ（ｎ）１。 ４算法应用及结果分析 ４．１ Ｚａｃｈａｒｙ空手道俱乐部网络 在１９７０至１９７２年问，社会学家ｗ．Ｗ．Ｚａｃｈａｒｙ观察研究 了美国一所大学的非官方空手道俱乐部，并根据其成员问 的相互交往密切程度构建了相应的社会关系网络 ，网络 中的节点表示俱乐部成员，节点间有连接表示相应的两成 员交往密切；该网络有３４个节点、７８条边，如图１所示；在 研究期间，该俱乐部的主管与校长之间因是否抬高俱乐部 收费问题产生了争执，并导致整个俱乐部成两个分别 以主管和校长为核心的小团体。图１中的节点３４和节点１
