社区划分
网络社区划分算法
网络社区划分算法 目录 ? 1 简介 ? 2 构建一个点击流网络 ? 3 网络社区划分的两种主要思路：拓扑分析和流分析 ? 4 拓扑分析 o 4.1 计算网络的模块化程度Q-Modularity o 4.2 计算网络的连边紧密度Edge betweenness o 4.3 计算网络拉普拉斯矩阵的特征向量Leading eigenvector o 4.4 通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值 o 4.5 通过multi level方法搜索网络模块化程度Q-Modularity的最大值 ? 5 流分析 o 5.1 随机游走算法Walk Trap o 5.2 标签扩散算法label propagation o 5.3 流编码算法 the Map Equation o 5.4 流层级算法 Role-based Similarity ? 6 总结 使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。 假设我们手头有一批用户在一段期间访问某类资源的数据。为了减少数据数理规模，我们一般只考虑最经常被访问的一批资源。因此在数据处理中，我们考虑UV（user visit）排名前V的资源，得到节点集合|V|，然后对于一个用户i在一段时间（例如一天）访问的资源，选择属于|V|的子集vi。如果我们有用户访问资源的时间，就可以按照时间上的先后顺序，从vi中产生vi-1条有向边。如果我们没有时间的数据，可以vi两两间建立联系，形成vi(vi-1)/2条无向边。因为后者对数据的要求比较低，下文中，暂时先考虑后者的情况。对于一天的n个用户做这个操作，最后将得到的总数为的连边里相同的边合并，得到|M|个不同的边，每条边上都带有权重信息。这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。
大型复杂网络中的社区结构发现算法
—92— 大型复杂网络中的社区结构发现算法 胡 健1，董跃华1，杨炳儒2 (1. 江西理工大学信息工程学院，赣州 341000；2. 北京科技大学信息工程学院，北京 100083) 摘 要：在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值。该文把超图模型以及基于此的聚类算法应用到社区结构发现的领域。对于简单图的社区结构发现，引入边聚集系数的概念，提出基于边聚集系数的社区发现算法。将安然邮件数据集作为测试数据集，通过算法对比分析，证明该算法在时间复杂度上可以提高一个数量级。 关键词：边聚集系数；社区结构；社区发现 Community Structure Discovery Algorithm in Large and Complex Network HU Jian 1, DONG Yue-hua 1, YANG Bing-ru 2 (1. Faculty of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000; 2. School of Information Engineering, University of Science and Technology Beijing, Beijing 100083) 【Abstract 】The automatic search and community discovery in large and complex network has important practical applications. This paper applies the hypergraph based model and cluster algorithm in community structure discovery, introduces the concept of Edge Clustering Coefficient(ECC) to community structure discovery of simple graph and proposes an algorithm of community discovery based on ECC. Enron e-mail data sets are test data sets, through comparative analysis of algorithm, to prove that this algorithm can significantly improve the time complexity. 【Key words 】Edge Clustering Coefficient(EBB); community structure; community discovery 计 算 机 工 程Computer Engineering 第34卷 第19期 Vol.34 No.19 2008年10月 October 2008 ·网络与通信· 文章编号：1000—3428(2008)19—0092—02 文献标识码：A 中图分类号：TP301.6 1 概述 复杂网络中社区发现(community finding)的研究起源于 社会学的研究工作。能够在大型复杂网络中自动搜寻或发现“社区”具有重要的实际应用价值[1]，如社会网络中的社区可能代表的是根据兴趣或背景而形成的真实的社会团体，引文网络中的社区或许代表的是针对同一主题的相关论文，万维网中的社区或许就是讨论相关主题的若干网站，而生物化学网络或者电子电路网络中的社区可能就是某一类功能单元。发现这些网络中的社区有助于更有效地理解和开发这些网络。与社区发现相关的成熟理论包括图论以及模式识别。Wu 和Huberman 的研究成果[2]以及Newman 和Girvan 的研究成果[3]使得复杂网络中的社区发现成为近几年复杂网络领域的一个研究热点并形成了复杂网络中的一个重要研究方向。Newman 和Girvan 把社区发现问题定义为将网络节点划分成若干组，使得组内的节点之间连接比较稠密而不同组节点之间的连接则比较稀少。Newman 和Girvan 在其研究中提出了基于边介数(edge betweenness)概念的分割方法，尽管该方法计算量很大，但由于其性能优越而成为社区发现研究的重要参考模型。 对于一般简单图的社区发现，也可以称之为基于图的聚类，把具有相同或者相似属性的有共性的节点聚合到一起，形成一个个的聚类[2]。这方面的方法有很多，最常用的有G-N 算法、谱二分法和层次聚类法。 尽管人们对复杂网络的社区发现问题已进行了大量的研究，但是仍然存在一些目前无法解决的基本问题[4]，如社区的概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需要的计算量却很大；更为 关键的是，很多算法不是针对异构数据集。这说明复杂网络中社区发现的研究还远没有成为体系，还有很多工作待完善。 2 边的聚集系数定义 为了刻画描述一个网络，通常有这样几个角度，一个是这个网络中点与点之间的距离以及整个网络的平均距离；另一个是每个节点的度以及整个网络的平均的度；还一个就是节点之间聚集的情况，点的聚集系数这个概念是用来体现对于某个节点A 来讲，如果B 和C 都是A 的邻接点(朋友关系)，那么B 和C 两者之间也有邻接(朋友)的可能性。 定义1 某节点n 的聚集系数(node clustering coefficient) ()C n 如下定义： (1)假设某节点n 的度是k ，则该节点的这些邻居之间可能形成边的最大数是： ()(1)/2T n k k =? (2)()E n 表示图中这些邻居之间实际的边的个数，则 ()()/()C n E n T n = 定义2 一个网络的聚集系数为这个网络中节点的聚集系数的平均值。 如图1所示，节点1的度为5，所以与它相连接的5个顶点之间最多存在54/210×=条边；而实际上另外5个顶点相互之间存在6条边，所以节点1的聚集系数是6/100.6=。 基金项目：国家自然科学基金资助项目(60675030) 作者简介：胡 健(1967－)，男，副教授、博士，主研方向：数据挖掘，智能信息检索；董跃华，副教授；杨炳儒，教授、博士生导师 收稿日期：2008-08-01 E-mail ：euguenehu@https://www.docsj.com/doc/c04196952.html,
网络社区划分算法
网络社区划分算法 目录 ?1简介 ?2构建一个点击流网络 ?3网络社区划分的两种主要思路：拓扑分析和流分析 ?4拓扑分析 o 4.1计算网络的模块化程度Q-Modularity o 4.2计算网络的连边紧密度Edge betweenness o 4.3计算网络拉普拉斯矩阵的特征向量Leading eigenvector o 4.4通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值 o 4.5通过multi level方法搜索网络模块化程度Q-Modularity的最大值 ?5流分析 o 5.1随机游走算法Walk Trap o 5.2标签扩散算法label propagation o 5.3流编码算法 the Map Equation o 5.4流层级算法 Role-based Similarity ?6总结 []简介 使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。 假设我们手头有一批用户在一段期间内访问某类资源的数据。为了减少数据数理规模，我们一般只考虑最经常被访问的一批资源。因此在数据处理中，我们考虑UV（user visit）排名前V的资源，得到节点集合|V|，然后对于一个用户i在一段时间内（例如一天）内访问的资源，选择属于|V|的子集vi。如果我们有用户访问资源的时间，就可以按照时间上的先后顺序，从vi中产生vi-1条有向边。如果我们没有时间的数据，可以vi两两间建立联系，形成vi(vi-1)/2条无向边。因为后者对数据的要求比较低，下文中，暂时先考虑后者的情况。对于一天内的n个用户做这个操作，最后将得到的总数为的连边里相同的边合并，得到|M|个不同的边，每条边上都带有权重信息。 这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。
局部最优社区挖掘算法(社区紧密度,关键词查找)
收稿日期:2008-11-07;修回日期:2009-01-15 基金项目:国家“863”重点基金资助项目(2006AA010106);国家“973”基金资助项目(2007C B311007) 作者简介:吴龙庭(1982-),男,湖北荆州人,博士研究生,主要研究方向为信息检索、决策科学(aaron792@https://www.docsj.com/doc/c04196952.html,);戴汝为(1932-),男,院士,主要研究方向为人工智能、模式识别;崔霞(1975-),女,副研究员,博士,主要研究方向为信息检索、人工智能. 一种局部最优社区挖掘方法 * 吴龙庭,戴汝为,崔 霞 (中国科学院自动化研究所复杂系统与智能科学重点实验室,北京100190) 摘 要:研究互联网论坛中划分用户社区问题。首先通过分析用户在论坛上的发言层次结构与内容建立用户之间的回复关系图,然后提出一种基于局部最优的图聚类方法LOGCA 对大容量的论坛网络图进行分类。实验得到互联网论坛上几个有意义的用户社区,并且确定了社区成员的共同兴趣。实验结果表明新方法简单有效,能够从大规模网络中发掘出有意义的用户社区。关键词:社会网络;知识发现;数据挖掘;中文论坛 中图分类号:TP 391 文献标志码: A 文章编号:1001-3695(2009)08-2855-03doi:10.3969/j.issn.1001-3695.2009.08.014 Com m unity m ining approach ba sed on local opt im izat ion WU Long-t ing,DAI Ru-wei,C UI Xia (K ey Laboratory of Complex Sys tem &Intelligence S cience,Institute of Automation,Chinese Academy of Sciences,B eijing 100190,China) Abst ract :This pa per st udied how to m ine m eaning ful Web com m unities from forum .Cons truct ed user int era ct ion g raph ac-cording t o the hiera rchical st ructure a nd content of forumpost s.P roposed a nov el g raph clus tering a lg orit hm LOGC A t o exploit m eaning ful com m unities from la rge-scale net works.The experim enta l result s show t hat t his a pproach is effect iv e in dis cov ering Web com m unit ies from Internet forum . Key words:social net works;knowledge discovery ;dat a m ining ;Chinese forum 0 引言 近些年随着互联网的快速发展,论坛、博客等虚拟网络空间越来越受到网民们的欢迎。围绕这些虚拟网络空间,网络社区应运而生。网络社区是指由网民在电子网络空间进行频繁的社会互动形成的具有文化认同的共同体及其活动场所,也具有实在社区的基本要素:活动因素、人群(网民)、频繁的互动、共同的社会心理基础等。在网络社区中,网民迅速地交流沟通各种信息资讯,网络社区已经在人们的生活工作中发挥着越来越重要的作用。 研究虚拟网络社区的结构对于互联网研究中的一系列课题如确定社会热点、提供个性化服务具有重要意义。大量研究[1～3]表明,虚拟网络社区具有与现实社会网络类似的性质,如指数分布特性及尺度无关性等。通常虚拟网络社区可以用图的形式表示,其中网络中的节点表示个人,连线则表示人与人之间的某种联系。因此从虚拟网络中挖掘虚拟社区转换为从一个复杂图寻找聚类子图的问题。传统的图聚类方法是阶梯聚类,即首先给定一组节点集合及它们之间的相似度矩阵,将每个节点设为一个单独的类;然后将点间距离最近的点合并为一类,将它们与其他节点的距离加权平均后作为新类与其他节点的相似距离;最后继续重复类合并过程,直到所有的类都合并成为一类。但这种方法不能直接应用于网络社区挖掘问题,主要是因为在网络社区中有时难以定义用户之间的相似距离。 1 相关研究 图聚类问题在物理学、生物学、生态学和计算机科学中都有广泛的研究。较早提出的解决这一问题的方法是Ker-nigha n-Lin(K-L)算法[4]。该算法使用二分规则不断地将图进行二分,从而得到图聚类结果。对一般的图聚类结果,该方法的聚类结果较好,同时运行速度也较快;但该方法的缺点是需要预先确定所需分类类数,如果类数指定错误,则分类结果也可能出错。由于实际图聚类问题中往往无法预先指定所需分类数,该方法的实际应用有限。另外一种应用较广的图聚类方法是最大流最小分割(m a x flow-m in cut)法。F ord 等人[5]证明了对图进行最小分割的问题等同于求取图的最大流问题。在实际应用中,也存在大量算法性能优越的最大流最小分割算法,但该算法的主要缺点是不能对所分类的容量大小进行限制。Girva n 等人 [6] 近年提出了一种基于邻近度(betw eenness) 概念的图分类算法,该算法假定任一条边的邻近度为图中所有点间最短路径经过该边的次数,因为连接两个属于不同类节点的连线的邻近度显然大于连接两个属于同一类节点的邻近度,所以去掉这些邻近度较大的连线,就自然地得到了图聚类结果。该算法的思想非常直观,但缺点是计算图中所有点间的最短路径的计算量非常大,而且每去掉一条连线,就要重新计算一次,这使得该方法的计算非常复杂,不利于用于大型的图聚类问题。在互联网中寻找有效的用户社区的方法首先出现在Kleinberg 的HITS 算法中 [7] 。该算法使用限定特征值的方法 第26卷第8期2009年8月 计算机应用研究 Applicat ion Research of Com puters Vol.26No.8Aug.2009
二部图社区划分算法的实现与验证
二部图社区划分算法的实现与验证 2015年6月
摘要 二分网络是复杂网络的网络表现形式之一，二部图是描述二分网络的工具。对于二分网络的社区划分研究通常用以下方法：一种方法是把二分网络以无权投影或加权投影的方式投影到单分网络中进行社区划分。但是这种方法有个缺点：它会把原始二分网络上的一部分信息丢失，导致实验结果不准。另一种方法是直接在二分网络上进行网络社区划分，这种方法很好的避免了上一种方法中投影造成的实验误差。 PageRank算法是Google的网页排序算法，是Google用来衡量网页的重要性的算法，该算法根据人们对这个网页的点击率来衡量网页的受欢迎程度从而得出该网页的排序，该算法是随机游走理论的一个典型应用模型。 对二分网络单侧节点进行社区划分的研究是具有重要的实际意义的。基于能量在网络中的转移概率和模块度思想，本文将PageRank算法用于二分社交网络的社区发现中，具体内容是利用二分社交网络节点间的连接关系，构造PageRank算法适用的概率转移矩阵，并利用不同维度的两个PageRank矩阵的联合运算，实现对二部图中单侧节点的社区划分，并计算出Q值。该算法通过模拟能量在网络中转移的过程，利用各个节点的能量在网络中转移后收到的其他节点的能量作为社区之间合并的依据，并用模块度作为判断社区划分好坏程度的标准。最后将PR算法用于典型网络（南非妇女网络）上测试。 关键词：二分网络；PR算法；模块度；随机游走理论；社区划分
Abstract Bipartite network is one form of the network performance in complex networ- ks,bipartite figure is a tool of describing bipartite network.For the research of bipartite net- work community division,there are usually two ways.One way is to divide the bipartite network into the one-mode network in the form of a unweighted projection or weighted projection for community division.However,this method come with a disadvantage:it will lose some information of the orginal bipartite network,which leads to the experimental results inaccurate.Another way is to divide the network community directly on the bipartite net- work.This method can avoid the error caused by the first method. PageRank algorithm is a page ranking algorithm which Google used to measure the importance of web page algorithm.It can measure webpage popularity according to the web hits and get the page ranking.This algorithm is a typical application model of random walk theory. The research on the community division of the unilateral nodes in bipartite network has very important practical significance.Based on energy transfer probability in the network and modularity thought,this article use PageRank algorithm for bipartite social network community discovery,specific content is using the bipartite social connection relationship between network nodes to construct the probability transfer matrix for PageRank algorithm.By using different dimensions of two PageRank matrix for compu- tation to realize the unilateral nodes in the bipartite figure community division and cal- culate Q value.This algorithm simulate the energy transfer process in the network,take the energy of each node in the network transfer energy received after other nodes as the basis of merger,use modularity as the judgement of community division.At last,the PageRank algorithm is used for testing in the typical network(south Africa women’s network). Keywords: bipartite network; PR algorithm; modularity; random walk theory; community division
复杂网络社区结构划分方法
复杂网络社区结构划分方法 已有 3661 次阅读2009-4-30 08:38|个人分类:科研笔记|系统分类:科研笔记|关键词:网络，系统，复杂网络，社区结构，聚类，划分方法 随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质，即社区结构。也就是说，整个网络是由若干个“社区”或“组”构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏[1][2]。揭示网络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站[3]；而生物化学网络或者电子电路中的网络社区可以是某一类功能单元[4][5]。发现这些网络中的社区有助于我们更加有效的理解和开发这些网络。 在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法，比如K-L算法[6]、谱平分法[7][8]、随机游走算法[9]和派系过滤算法[10][11]等；第二类是层次聚类算法，比如基于相似度度量
的凝聚算法[2]和基于边介数度量的分裂算法[1][12][13]等。最近几年从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致可划分如下：基于电阻网络性质的算法[14]、基于信息论的算法[15]、基于PCA的算法[16]和最大化模块度[17]的算法[18-23]等。对于符号网络，Doreian和Mrvar提出了一种利用局部搜索划分符号网络社区结构的算法[24]，且Bo Yang等提出一种基于代理的启发式划分符号网络社区结构的算法(FEC)[25]。 尽管复杂网络的社区发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社区概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社区发现的研究还需要付出大量的努力。 关于复杂网络社区发现问题更加系统深入的最新进展情况请看2009长篇综述文章Community Detection in graphs by Santo Fortunato (arXiv:0906.0612) 参考文献 [1] Girvan M, Newman M E J. Community structure in social and biological networks[J]. PNAS, 2001, 99(12): 7821-7826. [2] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.