关键词： 进化计算   标签传播   密母算法   强化学习   网络嵌入   图自编码器  

摘要： 现实世界的许多事物,如电力系统、社交网络、交通网络等,都可以抽象成由节点和其联结关系构成的复杂网络。社团检测和网络嵌入是复杂网络中两个重要的研究方向。一方面,社团是复杂网络在结构特性上的一个重要体现,不仅可以反映社交网络中的兴趣团体,还可以反映蛋白质相互作用网络中的调控模块,因此社团检测对于理解网络中信息传播,发现网络中功能模块都起到关键作用。另一方面,网络嵌入通过将高维稀疏连接关系映射至低维向量空间,克服了处理高维非线性数据的困难,为后续在分类、识别和预测等任务上使用机器学习算法创造了有利条件。然而这两个研究方向面临着诸多困难:在社团检测问题中,多样化的现实情境和图结构的非线性性质对如何定义合适的社团目标函数提出了挑战,同时大规模的节点数量亦要求社团检测算法具有高效的搜索方式;在网络嵌入问题中,如何突破传统的一阶二阶相似度定义引入社团结构相似度,并在网络嵌入学习算法的可导目标函数中加入社团结构信息是一个挑战。基于以上挑战,本文一方面研究并设计了基于进化计算的社团检测算法中的三个关键算子:初始化算子、交叉算子和局部搜索算子;另一方面,针对如何在网络映射中保留社团结构信息,提出了一种使用图自编码器和进化计算交替优化网络嵌入的方法,主要研究工作如下:(1)基于启发式采样和等价映射的社团检测进化算法大多数基于进化计算的社团检测算法没有处理个体交叉时社团编码存在一部分差异的问题,而且在生成初始解时缺乏对物理假设的考虑。针对上述问题,本文提出了采样算子和学习算子。前者借鉴标签传播算法的思路从发展的角度看待社团的变动,认为社团划分采样于由图矩阵支配的信息传播过程;后者在海明距离的意义下,构建了寻找两个个体之间等价映射的贪心算法,来消解一部分编码差异的问题。进而本文提出综合两者的基于启发式采样和等价映射的进化算法用于处理社团检测问题。通过多种现实网络的独立对比实验,分别证明了学习算子和采样算子的有效性,以及整体算法相对以往基于进化计算的社团检测算法的优势。(2)基于置信度上限和大规模邻域搜索的社团检测密母算法大部分的基于进化计算的社团检测算法中,局部搜索算子往往采用的是传统的爬山法和模拟退火等缺乏针对性的搜索方法。本文引入了强化学习和大规模邻域搜索的框架,并针对社团检测问题建立了社团评分函数、移动收益函数的概念来使用基于强化学习范式的控制策略,建立了破坏算子和修复算子的概念来使用大规模邻域搜索的框架。两者在密母算法的框架下结合起来以利用不同社团评分函数的优势。实验表明,我们提出的局部搜索方法相对传统的启发式局部搜索算子收敛速度快,收敛上限高,同时基于不同社团评分函数的局部搜索算子在密母算法中的重组算子影响下组合具有更大的优势。(3)基于进化计算与图自编码器的网络嵌入学习算法将高阶结构信息以及社团所暗含的信息融入到网络嵌入的学习之中一直是人们所期望的事情,然而无论是传统的矩阵分解方法还是现在流行的深度学习方法都是从重建损失函数的角度优化嵌入问题,从而难以引入不可导的离散形式的社团结构函数。本文一方面建立了表示重叠社团的向量和社团相似度矩阵,在图自编码器的目标函数中加了社团结构项;另一方面,利用第一个工作中提出的采样算子从自编码器输出的网络嵌入表示中提取社团表示,构成了进化优化的初始种群。上述两者结合实现了交替优化的网络嵌入学习算法。实验结果表明,我们提出的方法与经典的网络嵌入方法相比在基于网络嵌入的节点分类任务上表现良好。

关键词： 复杂网络   二分网络   映射模型   社团检测  

摘要： 复杂网络是由大量的个体以及个体之间紧密联系、相互作用的一类网络。近年来,复杂网络理论的发展速度惊人,吸引了众多研究者的关注。研究者们将其应用在日常生活中常见的社会网络、生物网络和交通运输网络等领域。为了更好地了解生活中实际的网络(系统),我们有必要加强对复杂网络理论及其应用的研究。这将对于我们更深入的认识生活中的实际网络是非常有帮助的。当对各领域的真实系统进行网络分析时,网络模型的建立能让我们的工作变得更加高效。生活中很多实际系统都可以用二分网络来表征,比如:男女性别网络、运动员参赛网络以及大学生选课网络等。本文基于前人所做的工作,对原有的二分网络映射模型进行优化。在二分网络=((3,(4,)中,该模型可以获得集合(4的节点在集合(3视角下的重要程度。具体的说,当集合(4的节点具有相同的初始资源时,基于节点自身的连边数以及连边权重,初始资源从集合(4的节点映射到相应的集合(3的节点,在下一时刻,资源又从集合(3的节点映射回集合(4的节点。经过多次映射过程后,集合(4的节点的最终资源收敛于一个常数值。该模型的结果取决于网络的拓扑结构、连边权重以及集合(4的节点的初始资源值,即,连接集合(4的某一节点的连边数越多,并且其关联边的权重越大,则该节点的最终资源就越高,则该节点在集合(3的视角下就越重要,本文将该值称为该节点的重要度。由于金融领域作为近些年来复杂网络研究的热点领域,所以本文选择将该模型应用于实际的金融系统。具体的说,本文提出了一个基金-股票网络映射模型来研究基金的投资规律。该模型能够计算每只股票的重要度,可以有效量化基金对股票的相对投资力度。从股票的重要度出发,研究了基金的投资水平、投资分布和投资倾向;本文根据股票的重要度提出了一个投资策略,为个体散户投资者提供了一定的参考。然后,为了研究基金的抱团持股行为,在基金-股票网络映射模型的基础上,本文提出了一种基于股票节点之间相似度的加权投影方法,建立了一个加权股票网络。本文对该网络进行社团检测,并给出了其社团分布图,寻找出该网络中的关键社团,进一步分析了关键社团的重要度演化以及关键社团中行业的重要度占比演化。

关键词： 复杂疾病   多组学数据   遗传网络   模式挖掘   社团检测  

摘要： 复杂疾病往往是由遗传、环境等多种因素共同作用导致的。挖掘复杂疾病的潜在遗传模式是揭示复杂疾病遗传机理的重要方法,其中基于多组学数据的复杂疾病网络模式挖掘方法为识别复杂疾病的遗传因子提供了新思路。本文以仿真数据和真实的复杂疾病多组学数据(基因表达数据、甲基化数据、拷贝数变异数据、单核苷酸多态性数据等)为基础,以遗传交互网络的构建与网络模式挖掘方法为手段,致力于发现复杂疾病的潜在遗传模式。具体研究内容如下:(1)针对复杂疾病多组学数据的网络构建问题,提出交互部分互信息测度,有效量化基因之间的依赖关系,从而构建基因之间的交互作用网络。将该方法应用到复杂疾病的基因表达数据上,进而从该基因网络中提取了与复杂疾病相关的特征基因以及重要通路。(2)针对复杂疾病遗传因子间的高阶交互作用检测问题,引入了两种节点用于构建高阶网络:真实节点表示遗传因子,虚拟节点表示遗传因子之间的交互作用。对构建的高阶交互网络进一步挖掘得到高密度子图,并对其进行了相关生物意义的验证。(3)针对复杂疾病遗传网络的节点检测问题,提出了基于归一化中心性测度的网络节点挖掘与分析方法。首先,识别复杂疾病的差异表达基因,并构建差异表达基因之间的遗传交互网络。然后,提出归一化中心性测度,全面分析该遗传网络中基因的局部特征和全局特征,从而充分挖掘网络中蕴含的特征基因以及重要生物通路。(4)针对复杂疾病多组学整合数据的社团挖掘问题,提出基于鲁棒主成分分析方法的社团挖掘与分析方法。首先,对多个复杂疾病的基因表达数据进行整合,引入鲁棒主成分分析方法从整合数据中筛选差异表达基因,并构建差异表达基因之间的交互作用网络,进而从网络中提取重要的社团。(5)针对复杂疾病多组学数据的网络构建以及网络整合问题,提出基于非负矩阵分解的网络整合与分析方法。首先,基于皮尔森相关系数构建复杂疾病多组学数据的异质性网络。然后,利用该整合方法对多个异质性网络进行整合,充分考虑不同的遗传因子之间的交互作用机制。最后,从网络中挖掘到与疾病相关的核心社团,并进一步检测出重要的生物通路。各项实验表明,本文提出的方法比同类方法在网络模式挖掘中更具优势,且可以检测到更多与复杂疾病相关的潜在遗传模式。

关键词： 加密货币交易网络   节点删除   有向二分图   一模投影   社团检测  

摘要： 随着加密货币影响力和市场价值的不断提高,不同领域的研究者对加密货币交易网络的关注也在不断增加。而当前,加密货币交易网络的建模方式仍存在较大的优化空间,比如现有各模型之间的关系仍有待探索、各模型间的特点尚待区分。特别的,在应对加密货币交易数据规模不断迅速增大的挑战时,构造合理的动态模型以实现对演化过程的细致分析,进而把握加密货币发展规律极为重要。为应对上述问题,本文主要从以下三个方面开展了探索工作。其一,针对现有静态模型构建过程繁琐重复的特点,本文探索了三种常见交易网络静态模型间的联系,并证明了三者间的定量转换关系,简化了静态模型构建的流程。针对加权有向二分图,提出了一种有效的一模化方法,并通过真实的比特币交易网络对该方法进行了验证。最后,对比了三种模型的特点,推荐使用“地址-交易”模型作为静态分析模型。其二,针对现有模型难以应对海量交易数据、开展动态演化行为分析的痛点,本文提出了一种可变权有向二分网络模型,可通过时变权值、节点影响力等指标动态展现网络演进状态。接着首次在比特币交易网络中引入了节点删除机制,改变了传统分析方式中网络节点只增不减的状况,有效降低了网络分析的复杂度;定义了网络信息熵指标,并据此提出关键演化时期筛选机制,便于快速开展演化过程分析。另外,利用该模型对真实比特币交易网络进行了研究,从六个方面分析了网络的动静态特征,发现了节点影响力和转账金额均近似服从幂律分布。其三,针对全局模型不能反映交易网络局部特性的短板,本文进一步提出了基于Louvain算法的动静态模型下交易网络的社团检测方法。首先,我们对经典的Louvain算法进行了预处理,引入了预设参数r以提高社团检测的灵活性。接着,我们对加权有向二分图模型下的“全局网络”和VW-DBG模型下的“有效网络”进行了社团检测,总结了三种典型的社团模式,并证实了早期比特币交易网络中存在“核心社团”;最后,我们对演化中的“有效网络”最大组元进行了社团检测,研究了最大组元的演化细节,并分析了演化过程中“长链型”社团占比情况。

关键词： 社交网络   社团检测   社团安全   社团隐藏   链路扰动  

摘要： 现实生活中频繁的信息交互依赖于社交系统的快速发展,这些复杂的社交系统在科学界被抽象化表示为具有特殊含义的社交网络;同时,这些社交网络又为网络科学的兴起和发展提供了原生动力。社团是社交网络的一个重要的结构属性,对网络中的社团结构的挖掘有助于科学家更好的理解社交系统的组成原理和功能,有利于挖掘网络中蕴藏的潜在信息,以及有助于对整个社交系统的发展趋势进行合理的预测。然而,人们频繁地参与社交活动必然会导致泛社交化现象,并且参与社交活动的用户总是在有意识或者无意识的情况下被现代复杂的社交系统所绑架。通常情况下,用户以个人隐私信息作为前提条件来获得参与社交活动的权利,这会给网络用户或与用户有关联的其他人带来隐私泄露的风险。例如,攻击者通过对用户所参与活动的社团进行深度挖掘能够掌握某些用户的生活习惯、家庭背景等隐私信息。基于上述问题,本文首先研究了社交网络中的社团检测问题,并提出一种基于种子用户的局部的自底向上的社团检测方法。其次,本文对社团检测的相关理论进行逆向研究,提出了基于链路扰动的目标社团隐藏算法。本文的主要研究如下:1.提出了一种基于种子用户的局部的自底向上的社团检测方案LBPCD。LBPCD主要研究基于物体的轨迹数据的社团检测方法的相关问题。具体地,本文首先通过研究2018年国际足联世界杯的足球比赛发现在球类比赛中都具有相同的特性,即比赛都是由相互独立的两支队伍对某个目标物体(例如足球、篮球等)进行传递完成的,而这种物体的传递可能发生在同一个队伍之内,也可能发生在不同的队伍之间。因此,每场比赛都会产生许多复杂的目标物体的轨迹数据集,通过对轨迹数据进行预处理,本文构建了目标物体的加权传输社交网络,网络中的链路权重表示目标物体从一个节点到另一个节点的转移传递次数。然后,本文引入了加权社交网络中的网络模块度的概念,在网络模块度的指导下,通过对种子用户进行迭代扩展,从而找出轨迹网络中的社团结构。最后,本文在人工收集的20场足球比赛的轨迹数据中进行了社团检测实验。实验结果表明LBPCD检测算法对于解决类似特定轨迹数据的社团划分问题具有较高的应用价值。2.提出了一种基于链路扰动的目标社团隐藏算法H。为了保护网络中的目标社团免受社区检测算法的攻击,本文提出一种通过对社交网络的链路进行扰动的方法来实现隐藏目标社团的目的。首先,本文对目标社团隐藏问题进行了形式化的描述,并设计了一个评估社团安全性变化的增益函数。基于该增益函数,本文分别证明了在网络中删除旧的链路和增加新的链路对目标社团隐藏所产生的不同影响。然后,在增益函数的指导下,算法H对网络进行有限次数的链路扰动操作,得到一个目标社团被隐藏后的社交网络。最后,本文在不同规模的社交网络中进行了大量的实验,并与其它社团隐藏算法进行比较。实验结果表明,本文所提出的目标社团隐藏算法H相比较于其它的社团欺骗方法而言能够获得更好的隐藏效果。

关键词： 电商用户   字符串相似度   复杂网络   社团检测   个性化推荐  

摘要： 互联网经过不断地发展,现已进入繁荣时期,来到了大数据时代,大量的信息随之而来。随着电子商务应用的不断发展,如何在用户情境日趋复杂的情况下精准识别出电商用户的不同类型,以满足用户的个性化需求己成为个性化推荐领域新的研究趋势。为了帮助电子商务平台解决电子商务用户的类型划分问题,在阅读了大量电阻距离以及复杂网络的相关文献后,本文提出了一种基于电阻距离的复杂网络社团检测算法（RD算法）,并基于社团结构划分质量评估指标模块度值和标准化互信息NMI,分别在四个真实世界网络（空手道俱乐部网络、海豚网络、美国足球队网络、爵士音乐家网络）和计算机生成网络（GN网络）上对本文提出的算法进行了评估。通过与其他五种社团检测算法进行对比,发现本文提出的RD算法在精度上有更好的表现。其次,本文在阿里云天池数据集获取的淘宝用户数据的基础上,以收集的用户访问记录数据作为研究对象,根据收集到的用户访问记录数据计算出用户序列节点间的距离,再通过已有的字符串相似度算法,选取合适的阈值,得到用户访问序列相似度以及距离。基于上述的用户距离矩阵,构建出电商用户行为网络,再从节点的度、平均路径长度、聚类系数、节点中心性等方面分析了该网络的统计特征,并判断了用户行为网络的无标度性和小世界特性。最后,利用复杂网络社团检测技术对构造出的电商用户行为网络进行社团结构划分,由于本文构造出的电商用户行为网络属于未知真实社团结构的网络,所以本文选择通过比较模块度值的大小来对本文提出的算法进行质量评估,通过与其他五种社团检测算法进行对比,发现本文提出的基于电阻距离的社团检测算法对电商用户行为网络的划分结果所得的模块度值最大。因此,本文提出的RD算法应用于真实网络的社团划分也有较好的表现,可以较好的解决电商用户的类型识别问题。根据本文对电商用户行为网络的社团结构所得的类型识别结果,将有助于帮助现有平台精准营销,为个性化推荐提供量化依据。

关键词： 复杂网络   社团检测   重要性矩阵   LPA算法   公共安全数据分析  

摘要： 复杂网络是对现实世界中各种复杂系统的抽象,包括社交网络、通信网络、交通网络和金融网络等。社团结构是复杂网络重要的结构特性之一,社团内部的节点联系紧密,不同社团间的节点联系稀疏。通过社团检测算法可以揭示网络的拓扑结构和功能组织之间的潜在关系。因此,复杂网络中的社团检测课题具有非常重要的研究意义和应用价值。本文通过对现有的社团检测算法进行研究后,提出两种基于标签传播的改进算法。本文主要的研究内容和成果如下: (1)针对标签传播算法LPA存在的问题,本文提出基于重要性矩阵的标签传播算法LPAIM。首先,利用MCL算法构建概率分布矩阵,并结合概率权重矩阵计算节点重要性。其次,在标签初始化阶段提出节点扩散的初始化策略,形成初始小社团。接着,在标签传播阶段结合标签相似性和节点重要性提出标签影响力指标,指导更新冲突时选择标签。最后,输出标签传播过程中最佳模块度对应的社团结构。本文在人工网络和真实网络上进行对比实验,实验结果表明LPAIM算法拥有较高的稳定性和准确性,能够从网络中检测出高质量的社团结构。 (2)为了完善LPAIM算法存在的不足,并且进一步提高算法的准确性,本文提出基于一阶h指数矩阵的标签传播算法LPAH。LPAH算法主要做了三点改进:首先,为了全面考虑节点重要性,引入局部重要性指标h指数,并结合重要性矩阵构建一阶h指数矩阵。其次,改进标签初始化过程,将节点扩散的策略优化成吸收邻居节点标签的策略。最后,提出一种社团后处理算法合并小社团,加强社团结构。通过对人工网络和真实网络上的实验结果进行比对分析,验证了LPAH算法的准确性,能稳定且有效地从模糊网络中提取出合理的社团结构。 (3)为了检验本文提出的社团检测算法的有效性和可行性,将两种算法应用于公共安全领域。利用社团检测技术对有组织犯罪进行辅助分析,挖掘未知的关联人员,刻画犯罪团伙的组织结构。

关键词： 复杂网络   社团检测   分块矩阵   投资组合  

摘要： 复杂网络理论应用于股票市场的已有文献大多研究股票网络拓扑结构,较少与投资组合理论结合.从复杂网络理论视角,利用两种网络社团检测算法将股票网络进行社团划分,用分块矩阵刻画网络社团结构,据此构建新的投资组合模型.基于上证180指数成分股的实证研究发现,在给定的期望收益下,新投资组合风险比皮尔逊相关投资组合低,且有效前沿位于皮尔逊相关投资组合有效前沿的左侧.实证结果验证了新投资组合模型的有效性.

关键词： 动态网络   社团检测   时序平滑  

摘要： 针对动态网络相邻网络快照社团检测结果差异较大、准确性不足的问题,文章在基于角色的标签扩散算法(role-based label propagation algorithm,RLPA)基础上,结合前一时刻社团结构信息以提高时序平滑性,根据时序结构差异性调整前序信息对当前社团结构的贡献权重,提出了一种基于角色的演化标签扩散算法(role-based evolutionary label propagation algorithm,RELPA)。在两类真实数据集上进行了对比实验,结果表明,该文算法能够准确有效地检测出动态网络中的社团结构。

关键词： 矿石   矿物成分   关联规则   社团检测   大数据   数据挖掘  

摘要： 近年来,借助于大数据技术的发展,地质学迎来了新的发展机遇,但目前利用大数据技术来分析矿物之间关系的研究还比较少。矿物是岩石、矿石的基本组成要素,通常都是以共存集合体的形式产出。矿物的产出不是随机的,而是按照一定的规律共生、伴生在一起。通过大数据技术挖掘出这种矿物的共伴生规律,能够更好地认识矿物之间的关系,对于指导找矿实践有积极作用。本文利用频繁模式挖掘、关联规则、网络分析以及社团检测这些常用的大数据挖掘方法进行了矿石主要组成矿物的大数据分析。所使用的矿石矿物组成数据来自于美国地质调查局的全球矿产资源数据系统(MRDS),该数据集收集了来自于全球的大量矿床中矿石的矿物组成数据。研究结果显示,通过关联规则可以挖掘出隐藏在矿石矿物成分大数据集中的频繁矿物组合,对于找矿勘查和认识矿物之间的关系有积极作用;关联规则挖掘出的规则是一种量化的推理规则,通过兴趣度度量指标能够定量地表征规则的强弱,这种规则相比于经验总结的规律更加定量化和精细化;通过网络分析能够对矿石中主要矿物之间的关系和共伴生规律进行动态、多维、定量的可视化;再结合社团检测可以从矿石矿物数据集中发现隐藏在其中的矿物之间的关系。