Identify Implicit Communities by Graph Clustering

0 IntroductionWeb communities are very i mportant signature of Weborganization. Community is a set of pages denselyconnected, which reflect that many pages have created bysome persons or groups with common interest . Communitiesare helpful for Web information retrival , social attribute ofWeb,customs analysis and site portal management . For in-stance,the Web directories in Yahoo!and Infoseek are com-munities . There two different communities . Oneis manifestlydefined communities such as n…     

Extracting the Cores of Implicit Communities

In this paper, we improve the trawling and point out some communities missed by trawling. We use the DBG （Dense Bipartite Graph） to identify a structure of a potential community instead of CBG （Complete Bipartite Graph）. Based on DBG, we proposed a new method based on edge removal to extract cores from a web graph. Moreover, we improve the crawler to save only potential pages as fans of a core and save a lot of disk storage space. To evaluate the set of cores whether or not belong to a community, the statistics of term frequency is used. In the paper, the dataset of experiment were crawled under domain ＂.cn＂. The result show that the our algorithm works properly and some new cores can be found by our method.     

谱聚类在社团发现中的应用

在分析谱聚类原理的基础上,研究了其在社团发现中的应用,提出了快速估计社团数量的新方法.该方法通过计算和分析Laplacian矩阵特征值的分布来估计社团的数量,利用K-means算法对Laplacian矩阵特征向量构造的向量空间进行聚类,实现社团的发现.该算法在真实社会网络和合成网络上做了测试,验证了在社团发现中的准确性和有效性.      

基于社区节点重要性的社会网络压缩方法

针对目前图压缩方法中存在的时间复杂度较高、依赖先验知识设定参数、需要调节的参数过多、压缩有损、忽视网络社区结构等问题, 提出基于社区节点重要性的社会网络压缩方法。该方法由基于贪婪策略的社区发现算法(GS)和社会网络压缩算法(SNC)两部分组成。GS算法采用拓扑势理论, 不但可以实现社区发现, 而且可挖掘出社区中的重要节点。SNC算法以网络社区为压缩对象, 在保持社区间的关联关系的前提下实现了无损压缩, 并可在必要时保留社区中的重要节点或基本结构。通过实验, 对方法的可行性和有效性进行了验证。     

一种新的基于社区结构的影响最大化方法

基于传播网络的结构性,提出一种新的基于社区结构的影响最大化方法AMICS.该方法先利用已有社区挖掘算法识别出隐藏在网络中的社区结构,然后迭代选择跨越社区数最多的k个节点作为影响的初始传播者最大化影响的社区覆盖.在小型网络和中等规模网络数据集上的实验表明,该算法比传统的影响最大化方法更具优势.     

基于路标的机器人自定位方法

介绍了一种基于路标的移动机器人自定位方法。为了解决仅仅利用视觉系统得到的路标信息使用蒙特卡洛自定位(MCL)算法进行机器人自定位时存在较大误差的问题,提出了一种将MCL算法与unscented卡尔曼滤波器相结合进行自定位的方法,将从机器人视觉系统获取的路标信息,从驱动轮码盘获取的位置信息,以及从电子罗盘获取的机器人方位信息进行有效融合,从而提高了机器人的自定位精度。实验结果表明,该方法不但可以提高机器人的自定位精度,而且具有较好的鲁棒性。     

基于网页内容相似度和链接关系的社区发现及动态添加

给出了一种基于网页内容相似度和网页之间链接关系的社区发现方法.该方法不仅考虑了网页之间的超链接关系,而且着重考虑了网页在内容上的相似度并克服了传统社区发现算法忽略网页内容的局限性,使发现的社区在内容上更相关.在原始社区的基础上对其进行动态添加,将网络中新出现的与原始社区中的网页存在链接关系同时与主题相关的网页加入到原始社区.实验表明,此方法可以有效地应用于网络的社区发现,使发现的社区在内容上更相关.     

基于多准则的多层模糊神经网络学习算法

模糊算子函数丢失信息量过大,并且在某些点不存在导数,由此导致在采用传统的误差平方和准则优化网络参数时,有些参数无法得到调整,而且网络容易陷入局部极小,甚至发散.本文提出了一种基于模糊熵准则和误差平方和准则的多准则多层模糊神经网络学习算法,在一定程度上克服了单准则学习算法的局限性.     

基于社团密合度的复杂网络社团发现算法

传统的社团发现算法大多存在划分效果和复杂度相矛盾的问题,为了解决该问题,提出一种新的单社团结构评价标准——社团密合度(group density).在此基础上,设计了一种基于凝聚思想的社团发现算法,该算法通过不断融合小社团,使网络的社团结构向平均社团密合度最大的方向发展,并使用模块度检测算法的划分结果.通过与经典的GN,Fast Newman,LPA等算法对多个数据集进行实验对比,验证了本文算法在获得较好的划分效果的同时具有较低的时间复杂度.     

基于重要结点的社区发现算法

复杂网络中内部的社区结构是复杂网络结构特征和属性特征的具体体现。首先依据模块度最大化理论计算网络的模块度矩阵的最大k特征向量矩阵;然后提出聚类中心方法,并用于求出k个社团的重要结点作为k聚类中心,利用欧几里得距离计算每一个结点到k个聚类中心的距离,将结点分配到距离聚类中心最近的社区中;最后对网络应用k-means方法进行迭代计算,得到k个社区的划分。分别在Karate Club Network和American College Football数据集上对算法进行了实验验证,实验结果表明该算法可以有效发现潜在社区,其纯度与模块度比已有的社区发现算法都有一定的提高,并且迭代次数较少,效率较高。     

一种基于EVS相似度的邮件社区聚类方法

聚类方法的核心是如何度量事物间的邻近性。介绍了邮件特征的向量表示形式、构建了邮件特征矩阵,并使用变形后的极值分布函数模型拟合了邮件间通信特征信息;在此基础上提出了一个新的邻近性度量方法(ex-treme value distribution similarity,EVS),用以指导邮件社区划分;使用微聚类-宏聚类邮件社区划分算法验证了该方法的有效性。实验表明,在测试数据集上,相比余弦、PCC等经典的邻近性度量方法,以EVS作为划分依据的邮件社区划分算法能够更加有效地发现高质量的邮件社区。     

基于子团规模的社团划分算法与地理位置

针对以往社团划分算法中存在的子团规模过大的问题,在CNM算法的基础上重新定义子团规模,提出了CLCNM社团划分算法.社团划分结果表明,改进后的算法在子团数量和模块度方面要优于CNM算法.在此基础上,研究社团划分与地理位置间的关系,提出地址前缀相似度的概念,子团地址前缀相似度越大,说明社团划分后的地理效应越明显.CLCNM社团划分结果表明:IPv6网络子团具有明显的地理效应,即子团中节点分布在相邻的地理位置.这一结论可对网络拓扑的再部署提供借鉴性意见.     

基于共邻节点相似度的加权网络社区发现方法

为实现加权网络的准确划分,发现真实的社区结构,提出一种基于模块度和共邻节点相似性的层次聚类社区划分方法IEM.首先,定义两节点间基于共邻节点的相似度.之后,基于该度量快速聚合当前节点和与其关联紧密度最强的邻居节点以形成初始社区,并进行社区扩展.最后,以最大化网络模块度为目标进行社区合并以优化划分结果.算法通过形成初始社区、扩展社区、合并社区三步,实现了加权网络合理有效的社区划分.以加权模块度作为社区划分质量的评价标准,在多个数据集上的实验结果表明,IEM算法优于加权CN、加权AA、加权RA.同时,与CRMA算法相比,IEM算法对加权网络社区划分的有效性和正确性更高.     

基于社区森林模型的分布式重叠社区发现算法

重叠社区发现是复杂网络挖掘中的重要基础工作,可以应用于社交网络、通讯网络、蛋白质相互作用网络、代谢路径网络、交通网络等多种网络的数据分析,从而服务智慧交通、传染病防治、舆情分析、新药研制和人力资源管理等领域.传统的单机运算架构已经难以满足各类大规模复杂网络的分析和计算要求.人工智能领域的研究人员提出将社区发现应用到网络...     

基于吸收度的三支决策社团划分算法

该文针对社团划分存在的重叠区域问题引入三支决策思想,提出了一种基于吸收度的社团划分算法(3WD-PPOC).3WD-PPOC首先根据网络结构的重要度矩阵进行社团的初始划分,再利用F吸收度来构建社团间的重叠区,即社团边界域,并得到各社团的正域,最后通过P吸收度来完成对在社团边界域中节点的再次划分和社团正域的更新.对比同类算法,3WD-PPOC具有较低的时间复杂度.实验结果进一步表明:3WD-PPOC能够有效地进行社团划分,相比其他社团划分算法,3WD-PPOC表现出更好的社团划分质量,划分后的各社团结构更紧密.该算法对社团重叠节点的划分具有较好的稳定性.     

基于相似度投票的社区划分改进算法

为快速、 准确地对日益复杂的大规模社会网络进行社区划分, 提出一种基于相似度投票的改进算法替代Louvain算法的底层划分, 解决了Louvain算法在底层划分收敛速度较慢, 并出现大量重复计算的缺点, 使社区划分更迅速. 由真实社会网络数据实验结果可见, 与Louvain算法相比, 改进算法在保持模块度基本不变的情况下, 效率显著提高, 划分的社区数更少、 社区结构更紧凑.     

基于大规模复杂网络社区发现的科研合著网络分析

针对基于极大团的社区发现算法,设计了适应大规模数据的MapReduce并行计算框架,提出了基于大规模复杂网络社区发现的科研合著网络分析算法,并用于对我国管理科学与工程领域2012年科研合著网络进行社区结构划分。实验结果表明,基于MapReduce的并行社区发现算法可在保证正确性的同时有效提高计算效率,适用于大规模复杂网络的社区发现。针对我国管理科学与工程领域2012年科研合著网络的社区划分结果展现了我国管理科学与工程领域科研合作的特点和问题。     

动态传感器网络中距离相关的蒙特卡洛定位算法

动态无线传感器网络的许多应用中定位技术具有至关重要的作用,在这种网络中部署区域内的全部节点不断运动.针对动态传感器网络中的定位问题,在蒙特卡洛方法的基础上提出了一种新的定位算法-距离相关蒙特卡洛(DRMCL).该算法通过利用节点的RSSI测距性能减小预测时未知节点可能存在的交叠区域,提高定位精度.仿真结果表明,对比蒙特卡洛和凸规划等现有的移动传感器网络定位算法,提出的DRMCL可以明显提高定位精度,在运动的过程中,定位精度能够达到20%以下.     

基于动量粒子群优化的社会网络分析

针对社会网络分析中的社区发现问题,在原有的粒子群优化算法的基础上,提出了一种基于动量粒子群优化算法,并且将此算法应用于社会网络分析中的社区发现研究中,提出了一种自适应社区发现方法.利用Newman提出的模块度作为适应度函数,在优化过程中自动获取社区数目,在Karate网络上的实验结果表明,所提出的算法能够有效地进行社区...     

基于节点通信监听机制的高效感知消息传输机会网络路由研究

针对采用社区划分策略的机会网络路由算法在消息传输过程中存在冗余转发的问题,设计节点通信监听机制,构建了新的消息传输策略,以高效感知邻居节点社区属性信息;并充分考虑携带移动设备的人的移动轨迹特点,设计了社区移动模型;嵌入时间片轮回机制,对网络节点进行动态划分社区;最终提出了基于节点通信监听机制的高效感知消息分发机会网络路由算法。在社区内转发消息时,选取与目的节点通信范围重叠区域内的邻居节点作为下一跳,若不存在这样的节点则将消息转发给与目的节点相遇概率较大的邻居节点或目的节点;在社区间转发消息时,算法选取与目的社区通信概率较大的中继社区节点转发消息,通过充分利用通信重叠区域内的节点转发消息,优化转发节点判定机制,重设消息传输条件,降低消息转发次数,从而提高消息传输成功率,降低传输时延。理论分析和仿真结果显示:与当前机会路由算法相比,新算法的传输成功率以及转发效率更高、平均端到端时延与平均存储时间更低。