［ ｓ ａｔ ｈｓｐ ｐｒｓ ｄｅ ｈ ｌｏ ｔｍ ｏ ｅｅｔ ｇｃｍｍｕ ｉ ｔ ｃｕｅｏ ｏ ｌｘｎ ｔ ｒ ａｅ ｎｃ ｓ ｒ ｇ ａａｙ ｅ ｅｓ ｌｒｙ Ａｂ ｔ ｃ］Ｔ ｉ ａ ｅ ｔ ｉｓｔｅａｇ ｒｈ ｆｒｄｔｃｉ ｏ ｒ ｕ ｉ ｎ ｎｔ ｓ ｕ ｔｒ ｆ ｍｐｅ ｅｗｏｋｂ ｓｄｏ ｌ ｔ ｉ ， ｎ ｌｚｓｔ ｉ ａ ｔ ｙ ｒ ｃ ｕ ｅｎ ｈ ｍｉ ｉ
法 ，将复杂 网络 中的结点转换为欧式空间中的向量。把结点
表示成 向量 的形式后 ，就可以使用传统的数据之 间的相似性 度量方法衡量结点之间的相 似程度 。
２ 社 团结构 的定义
近年来 ，虽然很 多研究者对社 团结构及其发现算法进行
了研究 ，但是仍然没有对社 团结构 的统一定义方法。文献【］ ４ 给 出了社 团结构 的定义 。 假设 网络 Ｇ的邻 接矩 阵 Ｗ， ｗ Ｗ是
的向量表示 形式
初 始化 Ｘｏ （，…１ ） 结点具有一 个单位 的信 息， ０ ＝ ｏ …０ ，Ｓ
其他结 点没 有信 息
Ｓｅ ｌ计算 图的邻接矩阵 ｗ； ｔｐ
Ｓｅ ２计算度对角矩阵 Ｄ； ｔｐ
Ｓｅ ３计算 ＝Ｄ一 ； ｔｐ Ｗ
Ｓｅ ４ ｔｐ
的信息 ；
： ， ｔ 救 ＝１ 结点 每次 向外传递一个单位 ，
ｃ ｎ ｅ ｓｔ ｅ ｎ ｄ ｓ ｉ ｔ ｈ ａ ａ ｓ ｕ ｔ ｒ ｕ ｔ ｂ ｅ ｆ ｒｃ ｕｓｅ ｉ ｇ ａ ｇ ｒｔ ｍ ｓ Ｉ ｏ ｐ ｒ ｓ ｔ ｅ ｄｉ ｅ ｅ ｔ ｌ ｓ ｅ ｉ ｇ ａｇ ｒｔ ｍ ｓａ ｄ ｓｍｉ ｒｔ ａ ｕ ｅ ｏ ｖ ｒ ｈ ｏ ｅ ｎ ｏ ｔ ｅ ｄ ｔ ｔ ｃ ｕ ｅ ｓ ｉａ ｌ ｏ ｌ ｔ ｒｎ ｏ ｉ ｔ ｒ ｌ ｈ ． ｔｃ ｍ ａ ｅ ｈ ｆ ｒ ｎ ｕ ｔ ｒｎ ｌ ｏ ｈ ｎ ｉ ｌ ｉｙ ｍｅ ｓ ｒ ｃ ｉ ａ
ｍｅ ｓ ｒ ｔｏ ｅｗ ｅ ｅｔ ｅ ． ｔ ｒｐ ｓ ｓ ａ ｐｎ ｅ ｅ ｔ ｅ ｔｒ Ｖ ａｇ ｒ ｍ， ｈｃ ｏ ｖ ｒ ｌ ｖ ｒ ｃ ｓｉ ｎ ｔ ｒ ｔ ｅ ｔｒ． ｔ ａ ｕｅ ｍｅ ｄｂ ｔ ｅ ｎｖ ｒｉ ｓ Ｉ ｐｏ ｏ ｅ ｐ ｉｇ Ｖ ｒ ｘｉ ｏＶ ｃｏ （ Ｖ） ｌｏｉ ｈ ｃ Ｍ ｔ ｎ Ｍ ｈ ｔ ｗ ｉｈｃ ｎ ｅｔ ａｌ ｅ ｔ ｅ ｅｗｏｋ ｉ ｏ ｖ ｃｏ ｓ Ｉ ｓ ｉ ｎ ｎ
一
中的元素 ，结点 ｉ 的度 ｋ＝ 。考虑 网络 Ｇ的一个子网络 ∑
Ｊ
ＧｃＧ ，且该子 网络 Ｇ包含有结点 ｉ ’ 。 。可以认为 ，结点 ｉ 的 度包含 有 ２ 个分量 ，即：
ｋ（ ＝ （ ＋ ｉＧ） Ｇ） （ Ｇ）
其中 ， Ｇ） 表示结点 足（ ’ ＝∑ 连接子网络 Ｇ 中其他结点 的 ’
中 分 号 Ｔ３ 图 类 ： Ｐ１ １
基于 聚类的复杂 网络社 团发现 算法
王观玉
（ 黔南 民族师范学院计算机科学系 ，贵州 都匀 ５ ８０ ） ５ ００
摘
要： 对基于 聚类技术 的复杂 网络社 团发现算法进行研 究，分析 网络中结点问的相 似性 度量方法 ， 出把复杂 网络中的结点转化为向量 提
图 ２所 示 。
０－ ４５
表示 结点 Ｓ 网络的影响 ， 对 它就可 以作为结点 Ｓ 映射 到 Ⅳ维空 间中的向量 。 把网络中的每 个结点分 别作 为源结点 ，
按照 以上的步骤 向网络中的其他结点传递信息 ，可以得到每 个结 点在高维 空间中的 向量表示 。也就是说可 以得 到 Ⅳ 个 Ⅳ 维向量 。 Ⅳ个 向量就是 网络 中的 Ⅳ个结点映射 到 Ⅳ维空 这
为复杂网络中的聚类 ，因此，可 以探索使用数据挖掘的方法 和理论发现 复杂 网络 中的社团结构。 但是复杂 网络的数据结构与通常 的聚类技术所处理的数
可 以揭示某个具体的结点在复杂 网络中起的作用。本文提 出
一
种 顶点到 向量 映射（ ｐ ｉｇ Ｖ ｒ ｘ ｉｔ ｅｔｒ Ｍａｐｎ ｅｔ ｎｏ Ｖ ｃｏ，ＭＶＶ 算 ｅ ）
第３ 卷 ７
第 １ 期 ０
王观玉 ：基于聚类 的复杂 网络社 团发现算法 而又不会 导致信 息的溢 出。
５ ９
对于整个 网络 的影响可 以用一个 Ⅳ维向量来表示 ，向量中的
元素代表相应结点受结点 Ｓ的影响所具有 的信息 。通过这个 传递信息的过程 ，结点 Ｓ 映射为 Ⅳ维空 间中的一个向量。 就 这个传递过程可以按照 以下的步骤进行 ： 假设把结点 Ｓ映射为 向量空 间中的向量 ，首先设置 Ｓ 为
据的数据结构有很大的不同，并且数据之 间相似性的度量方 法在很大程度上影响着聚类的效果 。如果能把 网络转换成适
合聚类算法的数据结构并选择合适 的相似性度量方法 ，就可 以把大量 的已成熟的聚类技术应用在社 团的发现 上。因此 ， 在使 用数据挖掘中的聚类技术 发现 网络 中的社 团之前 ，应该 把 网络转化成适合聚类算法的数据结构 ，选择合适 的结点之
１ 概述
社 团是 网络 中结点组成 的分组…，组 内的边较多 ，而组 间的边 较少。复杂 网络 中的社 团结构具有重要意义 ，因为社 团结构通常对应于 网络中的某一功能单元 ，例如 ，万维 网中 具有相 同主题 的站点组成 的社 团１ ；生物 网络中具有相 同功 ２ １
能 的细胞单元组成 的社 团 ｊ 。发现复杂 网络 中社 团的过程可 以看作是对复杂 网络进行较粗 粒化 的过程。发现社 团结构也
法，它可以帮助 用户发现隐藏在大量数据中的规律和模式 ， 它融合 了人工智 能、统计、机器学 习、模 式识别 和数据库 等 多种学科 的理论 、方法和技术 ，已经在多种 不同的领 域获得 了广泛应用。在复杂 网络领域 中，社团结构是许多网络所 共 有的特性 ，也可 以作 为隐藏在 网络 中的一种模式 ，它又被称
Ｗ Ａ Ｎ Ｇ ｕａｎ－ ｕ Ｇ ｙ
（ ｐ ｒ ｎ ｆ ｏ ｕｅ ｃ ｎ ｅ Ｑｉｎ ａ ｒ ｌ ｏｌｇ ｒ ｔ ｎ ｌ ｉｓ Ｄ ｙ ｎ５ ８ ０ ， ｉａ Ｄｅ ａ ｍｅ ｔ ｍｐ ｔｒ ｉ ｃ ， ａ ｎ ｎＮｏ ｍａ Ｃ ｌ ｅ ｏ ｉ ａ ｔ ， ｕ ｕ ５ ０ ０ Ｃｈｎ ） ｔ ｏＣ Ｓｅ ｅ ｆ Ｎａ ｏ ｉ ｅ
ｊ Ｇ ｅ
邻结点传递信 息，并且也会接收来 自于其相邻结点的信息。 源结点的信息在经过了 次传递 后，它就 向整个网络发送 了 丁个单位 的信息 ，整个 网 中的结点都会受到源结点的影响 络 而拥有信息。这样对于一个具有 Ⅳ 个结点的网络 ，源结点 Ｓ
作者简 介 ：王观玉（９４ ，女 ，副教授 ，主研方 向：数据 挖掘 ， １６ 一）
ｍ ｅｈ ｄ， ｅｒ ｓ ｌ ｈ ｗ ａ ＶＶ ｌ ｏ ｔ ｍ ａ ｍｐ ｏ ｅｔ ｅ ａ ｌ ｙ ｏ ｅ ｅ ｔ ｇ ｃ ｍｐ ｅ ｅｗｏ ｋ ｏ ｍｕ ｉ ． ｔ ｏ ｔ ｅ ｕ ｔ ｓ ｏ ｔ ｔ ｈ ｓ ｈ Ｍ ａ ｇ ｒ ｈ ｃ ｎ ｉ ｒ ｖ ｂｉ ｔ ｆｄ ｔｃ ｉ ｏ ｌ ｘ ｎ ｔ ｒ ｓｃ ｍ ｉ ｈ ｉ ｎ ｎｔ ｙ
图 １ 结点正确捌分比例
可 以看到 ，在 Ｔ ３ ４时划分效果较好 ，而这个网络的直 ＝，
Ｓｅ ５如果传递 次数 ｔ ｔｐ 小于 ，返回 Ｓｅ４ ｔｐ ，否则输 出结
果 。
径为 ３ ，即把传递次数设置在 网络的直径附近是可行的。而 把传递次数设置过少或过高 都不能取得很好 的效果 。 为了进一步测试 取值在 网络直径附近的合理性 ，在 设 置 不 同 值 时使 用 层 次 聚 类 算 法 分 析 计 算机 生 成 网络 （ ０＝ ，直径为 ３ ，记录模块度的最大值 （ 块度越大 ，所能 Ｃ ２ ） 模 达到的分割效 果越好） 模块度最 大值 随传递次数 的变化如 。
复杂 网络
边 的条数 ； ｏ（ ） Ｇ’ ＝∑ｗ． ０ 表示 结点连接 子 网络 Ｇ 外其他结 ’
俺 Ｇ
点 的边 的条数 。
３ 复杂网络结点的相似性度量
数 据挖掘 是 用于大规 模数据 处理 的技术 手段和 思维 方
收稿 日 ：２ １一 ２ 期 ０１ 叭－ ０
Ｅｍａ ：ｗ ｎｇ ａｙｇｉ ｏ＠１３ ｏ － ｉ ａｇｕｎｕｕ ｈｕ ６． ｒ ｌ ｚ ｃｎ
的顶点到向量映射（ Ｖ） ＭＶ 算法 ，把 网络 中的结点转化成适合聚类算法 的数据结构形式 。对不 同聚类算法及相似性度量方法的性能进行比较
分析 ，结果表 明，ＭＶ Ｖ算法 可以提 高发现 复杂 网络中社 团的能力 。 关健词 ：复杂 网络 ；社 团结构 ；聚ｇ Ｃｏ ｍ ｕ ｉｙ ｇ ｒ ｔ ｍ ｆ ｒＤｅ ｅ ｔ ｍ ｎ ｎｔ ０ ｍ ｐ ｅ ｔ ｒ ｓ ｄ ０ ｕ ｔ ｒｎ ｆＣｏ ｌｘ Ｎｅ ｗｏ ｋ Ｂａ ｅ ｎ Ｃｌ ｓｅ ｉ ｇ
源 结点 ， 假设每次它都会 向外发送一个单位 的信息。开始时 ，
结点对网络没有影响 ， 表示为 ｘｏ ０ｏ …０ ， 就是 结点 ＝（，…１ ） 也
分别设置传递次数 ２ ３４ ８时，得到上面提到 的计算 ，，， 机 生成 网络中结点的向量表示 形式，然 后使 用层次聚类算法 并且使 用欧式距离作 为相 似度对这 个网络进行社 团划分 。当 连接结点 的边 中处于社 团之 间的边的平均数量 ｃ 变化时 ， ０ 这 个网络 的直径总是在 ３附近 。分别记 录当 ｃ 变化 时，７ 。 １ 取 不同的值 时结点正确划分 比例 ，结果如图 １ 所示 。
间的相似性度量方法。 在本文提 出的 ＭＶ 算法 中，将复杂 网络中的结点看作 Ｖ 是信息源 ，可 以发送和接收信息 。确定源结点 Ｓ ，每次 向外 发送一个单位的信息 ， 其他结 点没有任何信息。第 １ 次传递 ， 源结点 向其相邻结点传递信息 ，这样它的相邻结点就获得 了 部分信息 。第 ２次传递 ，所有具有信息的结点都会 向其相
［ ｙｗｏ ｄ ］ｃ ｍｐｅ ｅ ｒ； ｏ Ｋｅ ｒ ｓ ｏ ｌｘｎｔ ｋ ｃ ｍｍｕ ｉ ｔ ｃ ｒ；ｌｓ ｒ ｇ ｄ ｔ ｎｎ ｗｏ ｎｔ ｓ ｕｔ ｅ ｃ ｔ ｉ ； ａ ｍｉｉｇ ｙ ｒ ｕ ｕ ｅｎ ａ ＤＯｈ １．９ ９ｊｓｎ１０ ．４ ８２ １ ． ．１ ０３ ６ ／ｉ ．０ ０３ ２ ．０ １１ ０ ９ ．ｓ ０