社区发现

摘要： 随着互联网的不断普及与网络通信技术的不断进步,网络已经逐渐进入到人们生活的每一个层面,越来越多的网络应用应运而生.但是另一方面,随着当前网络结构的日益复杂,会引起各种各样的网络安全问题,对社会构成了巨大的威胁和挑战.因此,网络安全问题至关重要.其中网络异常检测得到了研究人员的普遍关注.多年来,虽然已有许多异常检测的工作可以一定程度上发现和抵御网络攻击,但是有些方法难以适用于无标签的数据集,有些方法则训练成本过高,无法应用于实时场景.此外,对于细微异常的检测也是现有方法面临的一大问题.考虑到模型可解释性对于很多场景的必要性,本文以可视分析作为基础,提出了基于社区发现的网络异常检测方法,通过一个较为合适的粒度来提高系统对于细微异常的检测能力.该方法首先使用多层常量玻茨模型(CPM)算法对移动时间窗内的网络数据检测社区,并以社区为单位提取特征向量,然后用社区匹配方法将相邻时间步的社区关联起来,通过监控各社区特征的变化情况来检测异常.这种方法既考虑了网络数据作为动态图的特性,又能从一个比较合适的粒度提取特征.此外,系统提供可视化界面来帮助用户确认异常点前后的网络情况、关联异常事件.通过在Vast Challenge 2013挑战三的NetFlow数据集上的实验证明了该方法能够有效地检测更加细微的网络异常,验证了所提方法的有效性.

摘要： 社区发现能够揭示真实社会网络的拓扑结构和重要节点。由于具有线性时间复杂度,无需定义目标函数及目标参数,标签传播算法(LPA)作为经典社区发现算法被广泛应用在学术和实践领域。针对LPA算法更新顺序的无序性和标签选择的随机性,提出基于节点影响力的理性节点标签传播算法(RLPBNI)。将节点影响力排序作为更新顺序,引入理性节点概念进行标签选择,并定义重叠度进行社区再降维。实验结果表明,与其他对比算法相比,RLPBNI算法不但可有效提高社区划分精度,且更容易发现混合程度较高的网络中隐藏的社区。

摘要： 社区发现是一个基础性的且被广泛研究的问题。现有的社区发现方法大多聚焦于网络拓扑结构,然而随着真实网络中实体可用属性的激增,捕获图中结构和属性的丰富交互关系来进行社区发现变得尤为必要。据此面向属性图提出了一种基于染色随机游走的可重叠社区发现算法OCDC,该算法解决了传统的基于随机游走的社区发现算法利用结构转移矩阵造成社区发现效果不佳的问题。具体地,首先利用经典的初始种子策略选出网络中差异度较大的节点,在此基础上设计种子替换策略,挖掘网络中质量更佳的种子替换路径集合对初始种子集合进行替换;其次构建结构-属性交互节点转移矩阵并执行染色随机游走过程得到高质量种子节点的染色分布向量;最后基于融合结构和属性的并行电导值对社区进行扩展。在人工网络和现实网络上的实验表明,本文提出的算法能够准确地识别属性社区并显著优于基准算法。

摘要： 社区结构作为复杂网络的一个重要属性,对于了解复杂网络的组织架构和功能具有深远意义。为了解决复杂网络的社区发现问题,提出了一种融合动态距离和随机竞争学习的社区发现算法(Dynamic Distance Stochastic Competitive Learning,DDSCL)。该算法首先结合节点度值和节点间的欧氏距离来确定随机竞争学习中粒子的初始位置,使得不同粒子在游走初期不会在同一社区内进行竞争,加快了粒子的收敛速度;然后结合动态距离算法,将节点间的动态距离融入粒子优先游走过程中,使得粒子的优先游走过程更具方向性,减小了随机性,并且粒子游走的过程也会优化动态距离的变化;当粒子达到收敛状态时,节点将被对其具有最大控制力的粒子占据。最后网络中每一个粒子对应一个社区,根据各粒子占据的节点来揭示网络的社区结构。在8个真实的网络数据集上,以NMI和模块度Q值为评价指标,将DDSCL算法与现有的代表性算法进行实验比较,发现DDSCL算法整体上优于其他算法,其不仅降低了随机竞争学习中粒子优先游走的随机性,而且解决了动态距离算法中出现的碎片化社区问题,提高了社区发现结果的准确性。实验结果表明,所提算法具有有效性和可行性。

摘要： 非负矩阵分解(nonnegative matrix factorization,NMF)因其有效性和易解释性强被广泛应用于社区发现领域。然而,现有大多数基于NMF的社区发现方法都是线性的,无法有效处理复杂网络的非线性特征,从而导致社区发现性能还有待进一步提高。针对该问题,提出了一种图卷积网络(graph convolutional network,GCN)增强的非线性NMF社区发现方法NMFGCN。NMFGCN包含两个主要模块:GCN和NMF,其中GCN用于学习网络节点表示,NMF将节点表示作为输入获得网络的社区表示。此外,提出一个联合优化方法以训练NMFGCN,不仅使得NMFGCN具有非线性特征表示能力,而且可以使得GCN和NMF相互促进并获得更好的社区划分结果。在人工合成网络和真实网络上进行大量实验,结果表明NMFGCN优于目前基于NMF的社区发现方法,从而证明NMFGCN确实可以提高NMF社区发现方法的性能。此外,NMFGCN还优于DeepWalk和LINE常用图表示学习方法。

摘要： 基于模型的协同过滤算法通过矩阵分解来将用户偏好以及物品属性用隐变量来表示,但现有的矩阵分解算法很难应对个性化推荐系统中严重的数据稀疏性以及数据变化性所带来的问题。针对上述问题,提出了基于双边块对角矩阵的矩阵分解算法。首先通过基于社区发现的点割集图分割算法将原始的稀疏矩阵转换成双边块对角矩阵,将具有相同偏好的用户以及相似特征的物品归并到同一个对角块中,然后将结构中的对角块和双边拼接成数个密度较高的子矩阵。实验结果表明,对这几个密度有提高的子矩阵进行并行分解,基于其分解结果进行原始矩阵的预测,能够有效缓解矩阵分解中数据稀疏性所带来的问题,既能提升预测的精度,又能提高推荐结果的可解释性。同时,每个子对角块都能并行独立分解,能达到提高算法效率的目的。

摘要： 标签传播算法是一种重要的社区发现算法,具有不需要先验知识、时间复杂度低的优点.针对传统标签传播算法随机性强导致社区发现结果稳定性差的问题,提出基于共同邻居相似度的改进标签传播算法LPACN,在选择邻居节点中出现次数最多的标签时,将邻居节点与该节点的相似度一并考虑,降低了标签选择的随机性,提高了算法的稳定性.在4个基准网络数据集上进行了对比实验,实验结果表明基于共同邻居相似度的改进标签传播算法能够得到更好的社区划分.

摘要： 针对基于网络嵌入的社区检测算法中节点嵌入和聚类过程独立进行时容易陷入局部极值的问题,文中提出基于双监督网络嵌入的社区发现算法.首先利用图自编码器,得到可保持网络的一阶相似性的节点嵌入.优化模块度,发现拓扑连接紧密的社区.采用自监督聚类优化,发现嵌入空间上相似的社区.引入互监督机制,使发现的社区在模块度优化和自监督聚类这两个角度上具有一致性,同时避免算法陷入局部极值.4个真实网络上的对比实验表明,DSNE性能较优.

摘要： 针对相似度预测算法无法同时嵌入局部和全局信息并提高运行速度等问题,融合社区发现和影响节点识别技术提出一个通用可扩展的链接预测模型。对网络进行社区划分,分别计算局部共邻节点的社区参与度和全局影响力得分,集成到统一的相似度框架中。为验证算法的有效性和可扩展性,给出在加权和无权下多个局部密集结构和影响节点识别指标的定义。在真实数据集上的实验结果表明,提出方法可快速实现通用可扩展性的预测任务,结果也普遍优于基准算法。

摘要： 发现由相似功能的个体所形成的社区结构是复杂网络分析的重要任务之一.提出一种基于非对称三角形割的重叠社区发现算法,首先根据社区内三角形连接情况对社区质量进行评价,并根据节点与社区的三角形连接定义了节点对社区的归属度和连接强度.考虑到网络不同部分连接密度的差异,在将节点从社区中移除或加入社区的过程中,为每个节点分别设置了不同的移除阈值和扩展阈值,以提高社区发现质量.将每个节点与其邻居节点组成初始社区,将归属度低于移除阈值的边缘节点从社区中移除,将连接强度高于扩展阈值的外围节点加入社区,社区节点移除和扩展阶段迭代进行直至社区结构趋于稳定,最后去掉重叠率过高的社区得到最终结果.在7个带社区标签的网络上将所提算法与其他7个经典重叠社区检测算法进行比较,通过重叠标准互信息和F;指标进行评价,结果表明所提算法可以较好地发现不同规模网络中的社区结构.

摘要： 同质网络的单一性已经不能有效地处理当前纷繁复杂的网络信息,异质网络包含多种类型的实体和链接关系,能够更加精确地对复杂系统进行建模和分析.基于异质网络的社区发现通过对异质网络中的多维结构、语义文本和多模信息进行信息表示和提取分析,对网络信息的获取与挖掘、信息推荐以及网络演化预测具有重要研究价值.首先简单分析了社区发现领域当前研究的不足之处,紧接着引出了异质网络的定义;随后针对异质网络社区发现领域,介绍了包括基于主题模型、基于排序和聚类相结合、基于数据重构和基于降维的方法等现有技术研究方法;最后讨论了该领域在网络结构复杂性、信息多样性、数据规模等方面面临的挑战,并指出基于并行化、可扩展、动态增量的研究是未来的研究热点和难点.

摘要： 近年来,互联网上社交应用越来越多,人们之间形成的社会化网络结构呈现出复杂网络的特征.社区发现是研究复杂网络中节点关系的重要方法,现今对重叠社区结构的研究更是此领域的重点与难点.通过研究发现,节点处在的位置不同、邻居节点数目不同等信息都会对它在网络图中的重要性造成影响,节点的重要性对社区的构造也具有很大影响.为此,本文结合这一特性对标签传播算法进行深入研究和改进,以提高方法准确性及效率.针对国内外社区发现算法、节点重要性排序进行研究,在重叠社区发现算法COPRA(Community Overlap PRopagation Algorithm)的基础上,提出基于节点重要性的标签传播算法NI-COPRA(Node Importance-Community Overlap PRopagation Algorithm),通过节点重要性排序、构建初始团的方式来进行改进提高.算法验证实验表明改进算法NI-COPRA在效率和准确性上都有所提升,并且减小了随机性.

摘要： Fast Unfolding算法是一种基于模块度优化的层次聚合社区发现算法,其优点是运行速度非常快,不足之处是准确度有待提升,这是因为该算法采用传统模块度作为合并社区的衡量标准,而传统模块度函数在计算时只考虑节点间的链接信息,忽略周围邻居节点的影响,导致会出现两个节点共同邻居较多但由于节点间链接信息较弱不能被合并的情况,从而影响最终结果的准确度.针对该不足之处,通过引入优化后的相似度来改进Fast Unfolding算法的模块度函数,提出一种基于相似性模块度的层次聚合社区发现算法,并采用归一化互信息量即NMI作为评价算法准确性的指标,在真实网络和LFR人工合成网络上进行实验,结果表明改进算法检测社区结构的准确度有明显改善.

摘要： 传统社会网络建立在社交关系图谱的基础上,而以兴趣或主题分享等为目的的兴趣型社交网络则引领着社交网络改革的浪潮.融合社交关系和兴趣爱好关系构建一个新型社交网络模型——主题关注模型.在此模型基础上,首先,采用集对联系度刻画顶点间相似性度量指标,该度量方法可以更好地刻画网络结构特征,提高传统局部相似性度量指标对某些顶点间相似性值的计算精度,降低全局相似性度量指标的计算复杂度.其次,综合考虑主题影响和社交关系,将集对联系度与凝聚型聚类算法相结合,提出一种新的主题社区发现方法.最后,在Karate网络和豆瓣数据集上进行主题社区发现,实验结果表明,考虑主题影响的划分具有更好的社区结构。

摘要： 社区发现旨在挖掘复杂网络的社区结构,现有的社区发现方法普遍存在着划分速度和精度不均衡的问题.商空间理论是一种粒度计算理论,通过粒度变换来降低问题求解复杂度,同时保持问题求解精度.提出一种基于商空间的多层粒化社区发现方法(multilayer granulation community detection method based on quotient space,MGQS).该方法首先通过快速粒化操作对复杂网络进行多层次粒化,形成逐层粒化、逐层抽象的多粒度商空间,再依据所求问题选择最佳粒层作为最终划分结果.在公用数据集上的系列实验结果表明,相比于其他算法,该方法既能快速划分不同类型和规模的网络,也能获取多粒度的社区结构并根据所求问题选择最佳粒层,取得较高的模块度值和NMI值.

摘要： 在社交媒体中自动发现高质量的社区是当前社会网络分析研究中的热点之一.传统的社区发现方法或基于兴趣内容或基于链接关系,这都存在一定的局限,为此本文提出一个结合兴趣内容和链接关系的社区发现方法.该方法首先分别基于用户兴趣内容和链接关系得到内容主题向量和链接社区向量;然后使用经过标准化处理的内容主题向量和链接社区向量计算用户之间总的距离;最后用二分K均值算法划分社区.通过在真实社会网络数据集上的测试表明,本文提出的方法比单纯基于兴趣向量聚类与单纯基于链接关系聚类方法要好,研究结果为社会化媒体上的社区发现研究提供参考.

摘要： 随着电子商务的发展,网上购物逐渐成为人们生活的一部分.在网上购物的时候,越来越多的顾客将在线产品评论作为挑选产品的重要标准.受利益驱使,水军会编写虚假评论来提高或贬低目标产品的声誉.一些水军甚至会结成水军群组,协同作案,危害更大.为了检测水军群组,之前的工作通常是提取曾经共评论过相同产品的评论者作为候选群组,然后判断其是否为水军群组.他们通常只专注于检测水军群组,却没有对水军群组的特征和差异进行分析.在本文中也使用了共评论性质.但本文是利用共评论性质构建带权评论者网络图,然后聚类出水军群组.首先,本文构建了一个带权评论者网络图模型,权重由本文提出的几个特征来计算.然后,本文利用权重筛选出由可疑评论者组成的子图.最后,本文用Louvain算法,一种社区发现算法,来聚类出水军群组.基于一个Yelp的打标签的大型数据集,本文测试了提出了模型,并分析了水军群组的特征及差异.

摘要： 随着大连接时代的到来,家庭客户市场成为各个通信运营商抢夺的重点.为充分挖掘潜在家庭客户,不断提高家庭市场占有率,本文利用主被叫次数、上下行短信条数、驻留位置、驻留时长等用户通信行为综合信息来构建邻接矩阵,对社区内不同家庭群之间的差异性进行分析,然后基于谱聚类算法设计模型,形成一种快速迭代的谱聚类社区发现方法,从而实现家庭客户分群.类似思路可扩展应用于大连接背景下的各类连接场景中.

摘要： 随着许多像Twitter一样具有全球影响力的社交网站的出现,舆论的影响力也开始跨越不同国家之间的界限,网络监察部门开始需要关注与评估国外舆论对国内的影响,而Twitter必然成为一个关注的焦点.文章基于社交媒体数据挖掘的关键技术和网络分析的相关理论,运用Python、graph-tool和NLTK等相关工具包,设计并实现了一个对Twitter进行数据搜集存储、数据分析和分析结果交互展示的综合分析系统.该系统能实时地搜集并展示某一地区的热门话题及相关推特文章,可以对推文进行情感分析展示;能够获取指定用户指定大小的个人关系网络,利用接近中心性、介数中心性以及Pagerank算法对该网络进行个体影响力分析,使用随机块模型对该网络进行社区发现.系统测试符合预期,为公安网络舆情监察工作提供了一定的参考与帮助.

摘要： 社会是一个由多种多样的关系构成的巨大网络.对社会网络进行研究,可以揭示关系的结构,解释一定的社会现象.为此首先引入关系以及关系描述词的定义,利用关系抽取技术,扩展传统的二元关系,提出了一种基于同义词词林的提取关系描述词的方法,并收集特定领域内的人物关系信息构建成人际网络.接着对人际关系网络的拓扑结构,社区发现以及网络社区核心人物进行了研究,同时对分析结果实现了可视化.结果表明,社会网络分析可以揭示真实社会中的许多现象,有助于人们理解和开发这些网络.

摘要： 本发明涉及一种考虑社区结构稳定度和增量相关节点进行社区发现的方法，包括以下步骤：1、生成初始社区集，设置社区的初始权重，并初始化迭代时刻；2、计算增量相关节点集合IVt；3、遍历每个社区，解散社区集NSt中社区权重和社区规模小于阈值的社区；4、对集合IVt中的节点进行社区划分，生成新社区；5、遍历每个新社区，解散社区规模小于阈值的新社区；6、遍历剩余相关节点集合IVt‑rm中各节点，计算节点与相邻社区的相似度，将其加入相似度最高的社区，生成社区集NSt；7、更新每个社区的稳定度和权重；8、计算NSt的社区结构稳定度；9、判断是否满足迭代停止条件，以结束计算。该方法可以高效、准确地进行社区发现。

摘要： 本发明公开了一种基于社区结构的内外比度量方法及社区发现方法，首先定义了内外比度量标准，用来判断子网络结构是否社区，以及该结构的社区紧密程度。然后提出比邻双向迭代算法，使用优化后的一组初始子网络结构，通过增加邻节点或减少内点两个方向，基于内外比度量标准，来迭代发现社区。本发明用于快速发现网络中紧密程度高的社区结构，能够更快、更全面地发现更好的社区，在最早发现最好社区的时间比上平均提高39.64％，在搜索覆盖面上平均提高12.67％，并具有计算数据依赖程度低的特点，适合分布式并行计算。

摘要： 本发明提供了一种非负矩阵社区发现方法及电影社区发现方法，包括如下步骤S11数据收集与计算，形成相似度矩阵X和L；S12将X进行非负矩阵分解，X≈UV；S13构造含有L的目标函数O；以及S14基于目标函数，得到非负矩阵分解的迭代公式，进行迭代，完成社区划分。本发明的一种非负矩阵社区发现方法及电影社区发现方法，将双属性的非负矩阵分解应用于社区发现，提高了社区分解模块的精确性。

摘要： 本发明公开了一种基于重叠社区发现算法的银行交易群体发现方法和系统，其中银行交易群体发现方法包括：1、读入银行交易流水数据，构建有向交易网络；2、对有向交易网络进行初始化，每一个节点初始化为一个社区；3、对每个节点，根据模块度增益决定该节点是否加入相邻节点所属的社区以及加入哪个相邻节点所属的社区，然后重构交易网络；将重构后的交易网络中的每一个社区合并为一个节点，跳转至步骤3应用模块度增益理论重构交易网络，直至所有节点所属社区不再变化，或整个网络的重叠模块度不再增加或者增加幅度低于某一指定阈值为止，最终获得划分好的社区，即得到银行交易群体。该方法能够快速划分出交易网络中的重叠社区，发现银行交易群体。

摘要： 基于复杂网络社区发现的层次重叠核心药群发现方法，包括如下步骤：1)TCMF网络的构建：a)对给定数量的方剂计算每味药物的出现贡献度并删掉出现贡献度小于一定阈值的药物；b)计算二元组药物的AC值做删减，再计算三元组药物的AC值做删减；c)剩余三元组构建TCMF网络；d)结束；2)TCMF网络层次及重叠核心药群发现：a)预处理步骤1得到的TCMF网络；b)对预处理后的TCMF网络执行MAIGA算法进行药群发现；c)返回药群划分结果；d)结束；本发明从复杂网络的观点出发来探索中药方剂配伍规律，为中药方剂挖掘的研究提供了新的模型，解决了传统聚类单分配问题。

摘要： 一种基于图剪枝和局部社区扩展的边社区发现算法是一种重叠社区发现算法。首先，计算图中的边吸引力，将图中边吸引力低于阈值的边删除，得到剪枝后的图。之后，将剪枝图转化为线图，使用PageRank算法，计算线图上的节点的得分矩阵，选取一个种子节点，扩展社区，重复该过程，直至网络中无候选种子节点为止。合并重复线图上的节点社区，并将其转换回原图上节点的重叠社区结构。本发明为重叠社区发现提供了一种基于图剪枝和局部社区扩展的边社区发现算法，与现有方法比较，本发明具有如下主要优点：（1）提出边吸引力概念，利用边吸引力进行图剪枝，降低线图节点的规模。（2）使用局部社区发现算法对线图上节点进行社区发现，能达到更优的评估度量值。

摘要： 本发明提供一种基于社区熵的多目标优化动态网络社区发现方法，包括将社交关系动态网络G初始化为方案集；通过解码方案集得到在时间步t时的社交关系动态网络G中不同社区的划分方案集合；计算每个划分方案的多目标最大化值得到目标函数结果集合，进而得出帕累托最优解集合；预先设定迭代次数，进行迭代操作，迭代过程中，生成规模为N的新方案集合，遍历新方案集合里的每一个方案，从帕累托最优解集中随机选择一个作为初始最佳值复制给新方案；进行局部优化；将原方案集和新方案集合并，得到新的帕累托最优解和相应的帕累托前沿；新的帕累托最优解作为下一次迭代的初始最佳值的候选解。

摘要： 本发明涉及一种考虑社区结构稳定度和增量相关节点进行社区发现的方法，包括以下步骤：1、生成初始社区集，设置社区的初始权重，并初始化迭代时刻；2、计算增量相关节点集合IVt；3、遍历每个社区，解散社区集NSt中社区权重和社区规模小于阈值的社区；4、对集合IVt中的节点进行社区划分，生成新社区；5、遍历每个新社区，解散社区规模小于阈值的新社区；6、遍历剩余相关节点集合IVt‑rm中各节点，计算节点与相邻社区的相似度，将其加入相似度最高的社区，生成社区集NSt；7、更新每个社区的稳定度和权重；8、计算NSt的社区结构稳定度；9、判断是否满足迭代停止条件，以结束计算。该方法可以高效、准确地进行社区发现。

摘要： 本发明涉及一种自动确定社区数目的快速符号社区发现系统，包括网络N的邻接矩阵A和网络模型(NModel)；所述的网络模型(NModel)＝(n,K,Z,π,θ,ω)，其中，n对应于网络的节点数；K是模型块数，对应于网络中的社区数；Z为n×K维矩阵，其元素Z

摘要： 本发明属于社交网络分析技术领域，公开了一种基于种子节点扩展重叠社区的发现方法、网络社区系统，对节点进行过滤，去除边缘须图结构，运用种子选区算法选取传导性良好的种子集；种子扩展使用PPR向量扩展，形成核心重叠社区结构；使用传播算法剔除边缘须图结构重新加入核心重叠社区。本发明可用于大型社交网络的朋友推荐，商品推荐和广告投放；针对大型社交网络的特点，结合边缘须图过滤，种子集选取，种子扩展以及最后的传播算法实现了大型社交网络重叠社区发现的良好效果。