基于随机块模型的社区隐藏统一框架

社区检测是复杂网络分析的重要工具之一,可帮助深入了解网络的社区结构和节点间潜在的关系,但同时也带来了隐私泄露问题.社区隐藏作为社区检测的伴生问题,旨在以最小的边扰动代价破坏网络的社区结构,近年来受到越来越多学者的关注.但现有的社区隐藏方法忽略了网络的生成机制且缺少针对不同尺度隐藏的统一框架,因此提出了一种基于随机块模型的社区隐藏(community hiding-stochastic block model,HC-SBM)算法,该算法从网络生成机制角度构建了社区隐藏的统一框架,即实现微观(个体)、介观(社区)、宏观(网络)3个尺度上的社区检测算法攻击.其基本思想是基于随机块模型刻画网络的生成机制,特别是网络社区形成和分裂的规律和模式,挖掘生成过程中的关键性链接以及链接集合,最终通过最小代价扰动策略破坏网络社区结构.通过在真实网络上的大量实验,并与4种先进的基准算法进行比较,表明了提出的HC-SBM算法在社区隐藏效果更优.

网络嵌入随机块模型的社区发现和链路预测

社区发现与链路预测任务是网络数据研究中的热点问题,兼顾网络传递性与区块结构有助于捕捉个体之间的有效关联、探测数据中蕴含的内在规律,帮助研究者挖掘更多数据价值进而做出决策.当前的算法与模型多侧重于网络传递性或区块结构单一层面的分析,且依赖一定的假设条件.本文提出网络嵌入随机块模型(NE-SBM)用于社区发现与链路预测.搭建贝叶斯框架完成模型参数的正则化,利用Metropolis Hasting-Gibbs算法获得节点嵌入表示的隐位置与社区隶属关系,基于多维尺度变换算法解决隐位置可识别性问题.本方法可解决传统启发式算法中过分依赖判断准则或评价函数的问题,对各类型的数据都具有更好的适应性.人工数据及真实数据的实验结果进一步验证了该方法在社区发现与链路预测中有更优的表现.

一种基于随机块模型的快速广义社区发现算法

随机块模型可以生成各种不同结构(称作广义社区,包括传统社区、二分结构、层次结构等)的网络,也可以根据概率对等原则发现网络中的广义社区.但简单的随机块模型在网络生成过程建模和模型学习方面存在许多问题,导致不能很好地发现实际网络的结构,其扩展模型GSB(general stochastic block)基于链接社区思想发现广义社区,但时间复杂度限制其在中大型规模网络中的应用.为了在无任何先验的情形下探索不同规模网络的潜在结构,基于GSB模型设计一种快速算法FGSB,更快地发现网络的广义社区.FGSB在迭代过程中动态学习网络结构参数,将GSB模型的参数重新组织,减少不必要的参数,降低算法的存储空间;对收敛节点和边的参数进行裁剪,减少每次迭代的相关计算,节省算法的运行时间.FGSB与GSB模型求解算法有相同的结构发现能力,但FGSB耗费的存储空间和运行时间比GSB模型求解算法要低.在不同规模的人工网络和实际网络上验证得出:在近似相同的准确率下,FGSB比GSB模型求解算法快,且可发现大型网络的广义社区.

一种高效的随机块模型学习算法

由于随机块模型能够有效处理不具有先验知识的网络,对其研究成为了机器学习、网络数据挖掘和社会网络分析等领域的研究热点.如何设计出具有模型选择能力的快速随机块模型学习算法,是目前随机块模型研究面临的一个主要挑战.提出一种精细随机块模型及其快速学习算法.该学习方法基于提出的模型与最小消息长度推导出一个新成本函数,利用期望最大化参数估计方法,实现了边评价模型边估计参数的并行学习策略,以此方式显著降低随机块模型学习的时间复杂性.分别采用人工网络与真实网络,从学习时间和学习精度两方面对提出的学习算法进行了验证,并与现有的代表性随机块模型学习方法进行了对比.实验结果表明:提出的算法能够在保持学习精度的情况下显著降低时间复杂性,在学习精度和时间之间取得很好的折衷;在无任何先验知识的情况下,可处理的网络规模从几百节点提高至几万节点.另外,通过网络链接预测的实验,其结果也表明了提出的模型及学习算法相比现有随机块模型和学习方法具有更好的泛化能力.

基于混合隶属度随机块模型社会网络结构分析

由于大规模社会网络中存在着多种结构,且这些结构对于大规模社会网络的研究至关重要,但现有的结构发现方法大多只能够发现单一的结构或事先确定的结构,不能较为全面的反应大规模社会网络的特征。为解决上述社会网络中多结构发现的问题,引入了混合隶属度随机块模型MMSBM(Mixed Membership Stochastic Block Model)。它不仅能够生成不同结构的网络,同时还可以根据随机等价原则发现网络中的其他结构。通过在两个不同规模的微博数据集上进行结构发现实验,结果表明MMSBM能够同时发现社会网络中的多种结构,与实际观测结构基本吻合,但其计算复杂度较高,在实际应用中仍难以推广。

正则化度修正随机块模型的演化网络社团发现

目前大多数用于社团发现问题的模型只适用于静态网络而忽视了时序信息,因此,无法较好地建模真实世界数据。针对该问题,提出一种基于度修正随机块模型的演化社团发现模型。根据演化聚类框架的原理,基于社团隶属矩阵将一个正则项引入到度修正随机块模型的目标函数中。利用网络交叉验证方法进行模型选择,处理社团个数随时间变化的演化网络,从而克服由于假定社团个数为常量而导致的与真实世界数据不相符合的问题。实验结果表明,与经典的动态随机块模型和Facet Net相比,该模型具有较高的准确性和较低的误差率。

基于随机块模型的多层次服务生态系统演化分析

随着云计算、边缘计算和移动计算等新技术的快速发展,可用服务的数量和多样性呈现出爆炸式增长.服务之间快速增长的合作、竞争关系催生了“服务生态系统”这一新现象.复杂多变的市场环境使得服务的变化频率越来越高,因此服务生态系统的演化研究是当前一个重要的研究问题,发现其演化过程中蕴含的潜在演化模式以帮助服务提供者和市场监管者做出决策.为此,服务生态系统演化分析成为了软件服务工程领域的研究热点之一,许多的研究工作依托当前流行的开源服务生态系统ProgrammableWeb展开.然而,现有服务生态系统演化分析视角比较单一,分析内容局限于服务生态系统宏观的网络拓扑性质,这种分析方式极大的限制了服务生态系统演化分析的应用场景.本文首先利用带权重的度修正随机块模型对服务生态系统进行建模,基于随机块模型中的参数变化,从服务生态整体、服务社区和服务个体三个层次对服务生态系统的演化进行了全面的分析,提出了面向服务生态整体层面的演化点发现算法、面向服务社区层面的社区演化事件检测算法、面向服务个体的个体发展阶段划分算法.基于一个典型的Web服务生态系统ProgrammableWeb的真实数据集进行了实验,实验结果验证了本文方法的有效性.

一种度修正的属性网络随机块模型

社区检测是复杂网络分析中的重要任务,现有的社区检测方法多侧重于利用单纯的网络结构,而融合节点属性的方法也主要针对传统的社区结构,不能检测网络中的二部图结构、混合结构等情况.此外,网络中每个节点的度会影响网络中链接的构成,同样会影响社区结构的分布.因此,提出一种基于随机块模型的属性网络社区检测方法DPSB_PG.不同于其他属性网络中的生成式模型,该方法中节点链接和节点属性的产生均服从泊松分布,并基于随机块模型考虑社区间相连接的概率,重点在节点链接的生成过程中融合度修正的思想,最后利用期望最大化EM算法推断模型中的参数,得到网络中节点的社区隶属度.真实网络上的实验结果显示:模型继承了随机块模型的优点,能够检测网络中的广义社区结构,且由于度修正的引入,具有很好的数据拟合能力,因此在属性网络与非属性网络社区检测性能上优于其他现有相关算法.

基于平均场近似的BP算法求解随机块模型

置信传播(BP)算法作为推断概率图模型的主流算法是求解随机块模型中联合概率分布的重要方法之一.但现有的方法要么在处理核边结构问题上存在精度不足问题,要么在理论的推导上存在近似太多,导致求解过程复杂且难以理解问题,或两个问题均存在.当然,精度不足也是由近似多造成的.导致理论近似多且推导复杂的主要原因,是随机块模型推断过程中求解联合概率分布并不是直接套用BP算法,即处理的图(网络)与概率图模型的图不统一.因此,本文利用平均场近似修正联合概率分布,使其完全匹配BP算法的迭代公式,这样使得在理论推导上简单易懂.最后通过实验验证,该方法是有效的.

基于随机块模型的中外统计学研究趋势分析

研究趋势的自动识别可以节省科研人员的时间,帮助他们把握本学科的研究动态.根据最小描述长度原则选择了最优的度修正随机块模型,分析了2001年至2015年中外统计学期刊的关键词网络,梳理了十五年来中外统计学研究的发展趋势·结果发现,国外统计学研究以统计理论为主,近几年以高维数据为代表的大数据相关主题持续火热;我国统计学研究主要与经济相关,近些年数据科学相关主题才有所发展.

基于统计推理的社区发现模型综述

社区有助于揭示复杂网络结构和个体间的关系。研究人员从不同视角提出很多社区发现方法,用来识别团内紧密、团间稀疏的网络结构。自2006年以来,提出了一些基于统计推理的社区发现方法,它们可识别实际网络中更多的潜在结构,并以其可靠的理论基础和优越的结构识别能力成为当前的主流。该类方法的主要目标是建立符合实际网络的生成模型以拟合观测网络,将社区发现问题转化为贝叶斯推理问题。首先给出社区发现中生成模型的相关定义;其次按照模型中社区组成元素将已有统计推理模型分为节点社区推理模型和链接社区推理模型,并深入探讨各种模型的设计思想及实现算法;再次,总结各模型适用的网络类型及规模、发现的社区结构、算法复杂度等,给出一种选择已有基于统计推理的社区发现模型的方法,并利用基准数据集对已有典型统计推理模型进行验证及分析;最后探讨了基于统计推理模型的社区发现存在的主要问题和未来发展的方向。

基于WB-MMSB模型的微博网络社区发现

提出了一个用于微博网络社区发现的模型WB-MMSB,该模型考虑了微博网络中节点存在的单向关系,节点的社区隶属度从链入主题隶属度和链出主题隶属度两个方面表示。用指数族分布和平均场变分推理方法推导了模型中各变量的表示,并用SVI算法计算模型涉及的参数。实验在新浪微博数据集上进行,采用归一化互信息和困惑度进行评估,结果表明,WB-MMSB模型的社区发现能力优于aMMSB模型,并且其收敛速度快于aMMSB模型。

基于拓扑信息和特征属性的社区发现算法

文章提出一种新颖的加权算法,旨在提高社区检测算法准确性。该算法结合网络拓扑信息和节点属性信息,采用光谱聚类技术来揭示潜在的社区结构。它能够自适应地学习不同属性对检测任务的贡献度并相应地分配权重,同时采用软阈值算子和L1正则化项来降低“噪声”属性对检测精度的不利影响。通过对数值模拟和真实世界数据集的测试验证该算法在社区检测应用中的有效性。

基于复发瞬间链接间隔的动态网络社区发现

纵向网络数据是较为常见的复杂网络数据,也是目前网络数据分析的热点之一。随机块模型是网络社区发现的经典模型,但是该模型无法直接用于模拟纵向网络数据。基于随机块模型,引入半参数比例风险模型去分析纵向网络数据,并利用随机块模型来描述复发瞬间链接间隔。结合变分EM算法,采用两步估计来分别估计模型参数和非参数部分,通过不同场景下的模拟试验来验证所提议模型的优良性,最后利用法国小学生的社交网络数据进行了实证分析。模拟和实证结果表明,在统计计算的时效和参数或非参数估计的精度上,本文所提出的网络数据模型和统计分析方法比现存文献的模型和方法具有较好的优势。

基于正则无回路矩阵的网络社团数目估计

针对社团检测中社团数目未知的问题,提出一种基于正则无回路矩阵的社团数目估计方法。该方法通过定义一种正则无回路矩阵并利用其谱特性对网络中社团数目进行估计。该方法计算高效,并且能够适用于随机块模型和度纠正随机块模型。利用两种人工网络进行验证,实验结果表明,相比基于无回路矩阵的估计方法,该方法重点消除了度异质分布对社团数目估计的影响,从而提高了估计结果的准确率。

内容网络广义社区发现有效算法

在对网络无任何先验知识情形下,PPSB-DC模型(popularity and productivity stochastic block model and discriminative content model)利用网络的内容和链接对网络生成过程进行建模,可有效地发现广义社区及社区间的链接模式。但该概率模型的参数估计算法耗时,初始链接模式参数设置敏感,限制了该模型的应用。对参数求解算法进行了改进,设计了一个有效的内容网络广义社区发现算法EPPSBDC(efficient PPSB-DC)。该算法通过采取抽样和并行技术,提高了算法运行速度,通过引入链接概率先验,消除了算法对初始参数的敏感性。在内容网络上与同类算法进行了比较,验证了EPPSBDC算法的有效性。

复杂网络中社团个数的估计

以随机块模型为基础,并假设社团之间顶点连边的概率符合伯努利分布,通过积分的方法构造出社团个数的似然函数。根据复杂网络的一个观测值求出这个似然函数的最大值,从而得到社团个数的估计。并用人工随机网络和真实的网络进行了验证。

基于网络拓扑与节点元数据的社团检测算法

传统社团检测算法利用网络拓扑挖掘社团结构,忽略了真实复杂网络中节点自身属性等信息在社团归属方面的重要作用。为此,提出基于网络拓扑与节点元数据的复杂网络社团检测算法。将高维的节点元数据建模为混合高斯模型,结合随机块模型建立似然概率模型,通过求解模型最优解得到网络的最优划分结果。在基准网络与Facebook网络上的实验结果表明,该算法不仅能准确挖掘网络中的社团结构,而且可结合真实社团情况给出合理解释。

基于种子节点扩展的社区发现方法

现实生活中的许多复杂互联的系统可以被抽象为网络结构,通过这种抽象可以更好地研究和分析这些系统。社区可检测性研究的是"社区能否检测"的问题。社区可检测性研究是社区发现算法的一个前提工作,现有的社区可检测性方法一般是在均匀社区的前提下工作的。针对非均匀条件下的社区可检测性的问题,提出了一种基于SBM的社区可检测性方法,并进一步的验证表明,提出的社区可检测性方法在非均匀社区的条件下可以完成社区可检测性的工作。

加权网络结构分析

网络研究已经成为机器学习领域中的热点问题之一,近年来发展起来的随机块模型是通过建模生成网络的一种方法.本文对随机块模型加以推广,建立加权的随机块模型,在求解过程中,采用一种可以广泛的用于求解混合模型的变分EM算法.最后通过数据模拟,证明了此方法的可行性.