基于核心节点的网络社区发现方法研究.pdf

1引言 随着信息技术的飞速发展 各种开放式的电子商务应用 平台不断涌现 人们之间的沟通越来越多地依赖于虚拟的交 互平台和现代技术手段 虚拟的社会网络开始走进人们的生 活 并诞生了网络社区的新生事物 对网络社区的数据进行 分析 挖掘 揭示数据背后的规律 知识 作为各种不同应用的 决策支撑成为许多研究人员关注的领域 虚拟的网络社区不 同于真实世界的社会 网络社区的成员通常存在许多交集 而 且一个成员可能归属于不同的社区 从而存在重叠的现象 匈 牙利的社会科学家Palla通过大量的实验证明重叠社区现象存 在的普遍性 可以用贴标签的方式来形象地描述重叠社区与 非重叠社区的区别 非重叠社区就是社区中的节点只能贴上 一个标签 表示该节点只能归属于这一个社区 而重叠社区则 没有这个限制 社区中任意一个都可以贴上多个标签 表示这 个节点同时属于这些社区 就好比我们同时加入好多个兴趣 圈子 里面有音乐圈子 篮球圈子 运动养生圈子等等 基于 Palla的派系过滤理论的方法有 T S Evans的Clique Graph 1 CPM算法 2 基于极大子团合并的EAGLE算法 3 由于网络规模呈不断增加的趋势 在进行社区发现过程 中 难以获得网络的全局信息 因此 研究人员提出从网络的 局部信息入手进行研究 并设计了基于局部社区的算法 实 验证明采用局部社区进行计算的算法能成功获得社区结构 同时 也可以使用在重叠社区与非重叠社区发现工作中 具 有重要的实践意义和价值 具有代表性的算法主要包括 基 于极大子团扩张的GCE算法 4 Clauset的Local Modularity方 法 5 等 本文将针对传统社区发现算法的不足之处 提出一种基 于核心节点的局部社区扩张算法EALCN Expansion Algo rithm based on Local Community Core Nodes 并对算法的时 间复杂度进行分析 最后通过仿真实验证明该算法在大多数 高度重叠的社区发现上具有一定的优势 具有一定的可行性 2问题定义 在本文中 网络都被定义成多个局部社区的集合 而局 部社区则是由核心节点以及围绕这个核心节点的一系列的 节点组成 一个节点是否被纳入到一个社区中则是由适应 度函数F来决定 一个局部社区S包含节点n 当且仅当n满 足F n 0 局部社区都是从一个初始节点开始 通过适应 度函数不断判断社区外的节点是否加入到社区中 从而不断 壮大社区规模 直到没有合适的节点可以加入社区中 经过 多次的迭代之后 网络中所有节点便都分配到不同的社区 中 如图1所示 是一个局部社区的例子 图中的网络由几个 结构非常明显的局部社区构成 红色节点表示核心节点 其 具有极大的度数 黑色的节点则是普通成员节点 从图中我 们可以很清晰看到重叠社区重叠部分高度重叠的特征 重叠 的程度通常都是跟初始节点以及适应度函数相关 图1一个局部社区的例子 基于核心节点的网络社区发现方法研究 张拥华 湖南工业职业技术学院 湖南长沙410208 摘要 本文充分利用社会网络中存在普适幂律分布的特性 提出了基于核心节点的局部社区发现算法 EALCN 利 用改进的PageRank进行节点排序 然后利用网络中的局部信息对局部目标函数进行优化 从初始的种子节点不断优化后获得 目标函数 最终获取局部社区 仿真实验表明 该算法利用少量的局部信息便能够比较快速的找出社区结构 具有较高的执行 效率 关键字 社区发现 重叠社区 局部社区 中图分类号 TP393文献标识码 A文章编号 1008 6609 2015 07 0039 04 作者简介 张拥华 女 湖南宁乡人 硕士 讲师 研究方向 大数据 云计算 基金项目 湖南省教育厅科学研究项目 题名 云计算环境下的精准营销团购网站关键技术研究 项目编号 12C1032 2015年第7期 学术探讨基金项目 39 3基于核心节点的局部社区发现算法 局部社区的发现大体都是由一个种子节点开始 然后经 过不断地扩张 最终形成一个社区 诸如LFM这些传统的 社区发现算法 通常都是采用随机的方式选取初始节点 这 样选出来的节点往往都不是核心节点 这样就会造成算法的 准确性极低 GCE算法尝试使用网络中的极大子团替代节 点作为种子扩张 但是极大子团的获取需要大量的计算 这 就使得算法的效率大幅度降低 根据网络节点度的分布特 征我们知道 网络中度数很大的节点是少量的 大多数节点 度是很小的 而这些度数很大的节点往往也是社区的核心 所有我们完全可以通过找出这类节点作为种子节点来进行 扩张 考虑到权重对种子节点的影响 我们在选取种子节点 时 将权重也加入影响因素中 基于此 本文提出了一种基 于核心节点的社区发现算法 该算法首先发现网络中的一系 列核心节点 然后将他们的跟随者加入到社区中 从而形成 社区结构 具体流程如图2所示 图2算法流程图 3 1种子节点的选取 在现实生活中 每个人都有自己的兴趣圈子 在这些圈 子里每个人都扮演者不同的角色 比如你关注的某个网络主 播要开始主播 你可能就会去加入到这个圈子中去 但是这 个主播是这个圈子的核心 起着引导作用 而大多数的关注 只是一个普通的参与者 这个就清晰地反映出在一个社交 圈中 每个人的影响力是不同的 他对这个社交圈所起到的 作用也就不一样 换句话说就是他在这个社交圈中的重要性 不一样 上文提到过 我们认为局部社区就是核心节点及其 跟随者所构成的群体结构 因此 最快找出这个社区的方法 就是先找出其核心节点 然后再围绕核心节点进行社区扩 张 由无标度网络模型 我们知道网络中的节点大多数度数 是很小的 只有少量的节点的度数很大 那么假设网络中的 每一个节点都至少归属于一个社区 独立节点自成一个社 区 则社区中必定会存在着这样一个核心节点 首先 本文对PageRank算法进行改进 使其能够适应无 向图的节点排序 以找出网络中的潜在核心节点 G 是一个无向加权网络 w表示权重 则任意节 点i的PR值为 Cen i c j iPRCen j wij k Aikwik 1 c Si N 1 其中 N是网络G中节点总数 wij为边ij的权重 c为调 节因子 为一个常数 通常设置为0 85左右 Si即为节点的 度 上述定义是基于递归定义的 可以看出 每个节点的 PR值都依赖于其邻接节点的PR值 而且后者会按照自身权 值与前者所有邻接节点权值之和之比来将自身的PR值分配 给前者 具体的PR值计算请看下列中的伪代码 经过排序后的节点 排名靠前的都有成为核心节点的潜 质了 但是 初始化是非常关键的 选择一个正确的节点作 为初始节点进行扩张可以快速地得到一个正确的社区结构 然而从一个错误初始节点开始那么结果往往是很糟糕的 为了避免先后选出的节点都位于同一个社区中 本文采取了 更少的邻居节点的方法 即在选择核心节点时 先判断此节 点与先前的核心节点的共同邻居数 当这个数大于阈值时 则弃置它 即核心节点之间的共同邻居数必须小于阈值 3 2局部社区的扩张 本算法定义了一个适应度函数 只有选取了适当的种子 节点 便可以通过贪婪算法来不断扩大适应度函数 从而获 取得到一个最优的社区结构 该适应度函数可以计算出任 意子图的适应度 子图的适应度反映出了子图内部与外部的 连接密度情况 对子图做任何的修改都会引起适应度的变 2015年第7期 学术探讨基金项目 40 化 通过不断修改子图的成员 添加或者删除 使得子图的 适应度不断增大 直到子图的适应度不在发生变化为止 此 时便得到了最优的社区结构 对于一个给定的社区S 那么S的适应度为 f S Kin S Kin S Kout S 2 其中 in s 是社区S的内部节点度数和 out s 是社区S 与外部的连接数之和 为一个可控制社区规模大小的参数 节点适应度是指一个节点对于社区适应度的贡献 所以 对于一个给定的节点A 那么其对于社区S的节点适应度为 F A f S A f S 3 其中 S A表示将节点A加入社区S后的社区 局部社区发现算法通常都是由一个初始节点开始 然后 不断进行社区扩张 从而形成完整的社区结构 但是 算法 的结果受到算法扩张模式的影响是极大的 一般地 算法中 都出现节点震荡 重复计算和畸形生长的问题 因此 本文定 义的社区发现流程如算法2所示 经过上述过程 便可以由一个初始核心节点得到一个社 区结构 3 3局部社区的优化 合并冗余社区 几乎所有的重叠社区发现算法都无可避免地会遇到 过 渡重叠 的问题 这类社区也被称为冗余社区 虽然我们在 极力地提高种子节点的选择精准度 以及优化社区的扩张模 式 但是网络本身的不确定性以及算法本身在参数的控制上 存在的不确定性 会造成社区与社区之间出现严重的交叉现 象 为了检测出社区间的冗余情况 以及合并冗余社区 本 文定义了一个重叠度来定量地刻画社区的冗余情况 给定两个社区C1和C2 则他们之间的重叠度为 Ov C1 C2 min C1 C2 4 当社区的重叠程度超过阈值时 将两个社区进行合并操 作 经过反复的实验 可以发现这个阈值设为0 65左右较为 合适 在构造局部社区的同时 冗余社区的检测工作也在同 步进行 在一个社区结构形成之后 立即对其检测 如果该社 区的冗余度小于设定的阈值 便接受这个社区 如果大于设 定的阈值 那么就放弃这个社区 通过反复进行这些操作 可以尽可能避免过度重叠的社区出现 4仿真与性能分析 为了证明本文所提出的EALCN算法的有效性 在如表1 所示的环境下进行试验 表1实验环境 项目 机器 CPU RAM OS 编程语言 辅助程序包 参数 Lenove PC Intel core TM i5 2450M 2 50GHz 4G 4G Windows 7 python Python igraph 图3为原始网络图 图4为使用EALCN算法后得到的优 化处理结果 图3原始网络图 图4使用EALCN算法划分结果 比较图3和图4 使用EALCN算法可以获得多个覆盖全 2015年第7期 学术探讨基金项目 41 网络的局部社区 并且具有算法复杂度小 执行效率高的特 点 5结束语 本文针对目前网络规模不断增大的情况下 难以获得网 络全局信息的现实问题 利用网络中的局部信息来实现对目 标函数的优化 具体而言是通过修改PageRank算法来获取 初始核心节点 然后由初始核心节点开始 通过不断地优化 目标函数来构建局部社区结构 实验证明 本文提出的 EALCN算法能有效地改进网络社区的划分效果 提高社区 划分的准确性 参考文献 1 柴变芳 于剑 贾彩燕 等 一种姓于随机块榄喂的快速广义社区发 现算法 J 软件报 2013 24 11 2699 2709 2 G Palla 1 Derenyi I Farkas T Vicsek Uncovering the overlap ping community structure of complex networks in nature and society Na ture 2005 435 7043 814 818 3 H Shen X Cheng K Cai M B Hu Detect overlapping and hi erarchical community structure in networks Physica A Statistical Mechanics and its Applications 2009 388 8 1706 1712 4 C Lee F Reid A McDaid N Hurley Detecting highly overlapping community structure by greedy clique expansion IA ln Proc SNA KDD Workshop1 1 Washington DC USA IEEE 2010 33 42 5 A Clauset Finding local community structure in networks Physical Review E 2005 72 2 026132 The Research on Network Community Detection Method Based on the Core Node Zhang Yonghua Hunan Industry Polytechnic Changsha 410208 Hunan AbstractAbstract This paper takes advantage of the universal power law distribution of social networks and proposes a leader based lo cal community detection algorithm EALCN It uses local structural information in the network to optimize a local objective func tion A local community can be detected through continuous optimization of the function by expanding from an initial core member computed by a modified PageRank sorting algorithm The advantage of this algorithm is that it only uses some local information of the network to detect communities by utilizing highly important nodes The efficiency is higher than traditional algorithms KeywordsKeywords community detection overlapping community detection local community 上接第38页 Analysis on Channel Capacities of Wireless MIMO Systems Sun Xiuying1 2Xu Pengfei1 1 Huaian College of Information Technology Huaian 223003 Jiangsu 2 Southeast University Nanjing 210096 Jiangsu AbstractAbstract This paper analyzes and simulates some ergodic capacities of several typical systems such as SISO SIMO MISO and MIMO especially