关键词： 复杂网络   社团检测   非负矩阵分解   半监督学习   图正则  

摘要： 社团结构对分析和理解复杂网络的性质和功能具有重要的作用。因此社团检测成为复杂网络分析的一个有效工具,同时也是计算机科学等不同领域广大研究者关注的一个研究热点。然而,由于网络的稀疏性和噪音性,导致网络的社团存在结构模糊、大小不平衡等问题,从而仅依赖于拓扑结构的社团检测不仅不能精确地识别出这样的社团结构,而且不能从语义上理解每个社团的实际意义。针对网络中模糊或不平衡性社团检测问题,本文通过融合少量可用的半监督先验、内容等辅助信息来指导复杂网络的社团检测,研究了一类融合辅助信息的社团检测模型,主要研究内容和创新点可概括为下述三条:1)融合强化网络结构的拓扑相似性信息,本文提出了图正则非负矩阵分解社团检测模型。基于网络的全局和局部拓扑结构,该模型定义了一个新的相似性指标作为辅助信息,并根据图正则的思想将其融入非负矩阵分解模型进行社团检测。生成网络和真实网络上的实验表明,拓扑相似性能强化原始网络中稀疏的拓扑结构,从而有助于提高模糊社团结构(如zout=10的GN网络)的检测精度。2)融合成对约束先验信息并引入节点流行度,本文提出了流行度修正的半监督非负矩阵分解社团检测模型。通过引入流行度来减轻度异质性对一定连接先验信息利用率的影响,本文提出一定连接约束的社团检测模型。进而,考虑到一定不连接先验对社团检测的提升作用,本文通过构建负网络的思想,又提出一定连接和一定不连接同时约束的社团检测模型。这两个模型能够更充分地利用半监督先验信息,尤其对网络中模糊且不平衡的社团,具有更高的检测精度。3)进一步融合节点的内容信息,本文提出了一个融合辅助信息的社团检测及语义信息匹配框架。为了从语义上更好地理解社团的实际意义,针对社团检测和社团语义匹配问题,该框架首先利用半监督先验信息和节点的内容信息分别得到一个精度较高的拓扑驱动的社团结构和一个内容驱动的社团结构,进而引入两者之间的耦合关系矩阵修正社团结构的同时实现社团和内容的准确匹配。本文提出的四个社团检测模型不仅丰富了稀疏网络社团检测的方法体系和研究框架,还为模糊且不平衡等较复杂社团结构的识别提供了理论依据,尤其在恐怖组织、犯罪团伙识别等公共安全领域具有重要的应用价值。

关键词： 复杂网络   社团检测   图数据   并行化  

摘要： 随着计算机与互联网技术的不断发展,网络已成为人们日常生活不可或缺的一部分。人们现实生活中的大部分数据都可用网络或图(Graph)来表示,如通信网络,交通网络、社交网络、生物网络等。社团结构是复杂网络的一个重要结构特征,研究这些社团结构有利于更好地理解复杂网络的功能与特性。此外,复杂网络在社团结构层面通常会显示出一些单个节点或整个网络层面所不具备的特性。为了更深入地研究复杂网络,捕获更多有意义的潜在信息,需要使用社团检测技术。然而随着节点数量不断增加,网络结构不断复杂,传统的社团检测算法已不再适用于大规模复杂网络。而分布式并行处理技术为处理大规模复杂网络提供了有效手段。因此,研究复杂网络的社团检测并行算法对深入理解网络结构与性质具有重大理论意义与实际价值。基于上述原因,本文提出了一种针对大规模复杂网络的并行化社团检测算法——Parallel LPA-Attractor算法(简称PLA)。在设计这种算法的过程中涉及图表示、分割、存储、计算以及结果融合问题,其中最重要的是单个计算单元的社团检测算法。在对现有的社团检测算法进行多方面的权衡比较后,本文采用Attractor算法作为核心计算算法。但该算法会检测出大量单节点社团,本文提出的LPA-Attractor算法(简称LA)利用标签传播算法LPA进行预处理改进这一问题。针对LPA算法只能发现非重叠社团的缺陷,本文提出一种改进型算法Adjustable Multi-Label Propagation Algorithm(简称AMLPA),使节点携带多标签来检测重叠社团。在算法并行化的其他方面,针对已有的图表示方法不再适合于并行及大规模运算的问题,本文提出了耦合表的图表示方式,耦合表可使数据得到更高效的利用,提高计算速度;PLA算法使用METIS图分割算法对输入的图数据进行分割;在数据存储方面,本文提出一种改进的分布式存储方式,利用节点的深层复制解决了现有图数据的分布式存储方法通信开销大的问题;此外对并行处理的结果提出了有效的合并方案。相关实验结果表明,本文所提的并行化社团检测算法有效地减少了计算时间,具有时间复杂度较低,准确率较高等优点。其中核心计算算法LA大幅度地减少了单节点社团的发现数量。因此,PLA算法为解决大规模复杂网络的并行化社团检测问题提供了一种有效的解决方案。

关键词： 社团检测   谱二分法   特征值   特征向量   模块度  

摘要： 针对传统谱二分社团检测算法一般只使用某一特定的特征向量对网络进行划分,并不能保证能够得到最佳的社团结构这一缺陷,提出了一种使用最优特征向量的谱二分社团检测方法。该方法利用网络/子网络转移矩阵的特征向量持续将网络分裂为若干个子网络,分裂过程并不固定使用单一的、特定的特征向量,每次分裂使用的是能使得模块度增量最大的一个特征向量。此外,为了充分利用网络的拓扑信息,还利用网络中每条边所关联的两个顶点拥有的共同邻居的信息,将原始网络转换为带权的网络,并基于此带权网络的转移矩阵,使用最优特征向量持续将其划分为若干个子网络,得到其社团结构。为了验证这两种方法的有效性,在7个实际网络上进行了实验。实验结果证实,该方法能够有效地从网络中提取高质量的社团结构。

关键词： 在线   非负矩阵分解   图流   社团检测  

摘要： 针对现有的在线社团检测方法大多仅从增量相关的节点和边出发,难以有效挖掘社团结构的动态变化特性问题,提出了一种基于图流在线非负矩阵分解的社团检测方法.首先将网络中持续到达的图数据按照流式数据进行存储和预处理,然后借鉴梯度下降思想,采用在线非负矩阵分解架构,根据不同时刻达到的图流序列,实时迭代更新社团归属矩阵,并通过有效的学习率和缓存策略设置,保证了图流处理的收敛性和合理性.实验结果表明,相比于已有在线社团检测方法,该方法具备更高的社团检测精度.

关键词： 复杂网络   社团检测   模块度   谱图方法  

摘要： 社团结构是复杂网络的重要特征之一。谱聚类方法在复杂网络社团检测中具有十分重要的作用。针对谱聚类算法在复杂网络社团检测中只选择部分特征向量聚类的问题,提出了一种改进的谱聚类方法,该方法对网络矩阵的所有特征向量进行加权,并引入尺度参数,采用网络矩阵的所有特征向量进行聚类。实验结果表明,与传统谱聚类算法相比,该方法可以有效地对网络进行划分,并可以反映出网络中社团的多尺度特性。

关键词： 结构洞   社团检测   社会网   社团结构  

摘要： 连接多个不同社团的节点称为结构洞节点,部分已有的结构洞节点检测方法虽然可以检测到关键节点,但存在一些不足:基于局部的测量方法忽略了网络拓扑结构;对于大规模复杂的网络来说,基于全局的测量方法可扩展性差,等等。为了高效准确地检测社会网络中具有影响力的节点,提出了一种新的结构洞度量方法 E-Burt,用来寻找结构洞节点。该方法利用节点与其二步邻居构成的拓扑关系来计算节点的有效规模,用该结果作为结构洞节点重要性的评价指标,计算每个节点的结构洞度量值,并给出了形式化定义。E-B算法基于网络拓扑结构,每次模拟迭代将选中的结构洞节点度量值置为零,下一次迭代只计算该节点二步邻居的有效规模,大大降低了时间复杂度。最后通过实验验证了算法的时间效率,分析了算法的精确度,对算法的正确性进行了证明,并与存在的经典结构洞发现算法进行了对比。

关键词： 高分辨率遥感图像   面向对象   社团检测  

摘要： 随着空间分辨率的不断提高,遥感图像的纹理特征受到越来越多的关注,面向对象的信息提取方法成为近年来学者关注的重点。面向对象技术使对遥感图像的分析从像元层次过渡到对象。分割后的遥感图像形成很多目标对象,而这些地理目标构成了复杂的网络特征,可以通过网络的空间结构和拓扑关系来实现地理目标属性和功能的表述,根据拓扑属性将空间数据库转换为网络。目前,将网络科学的社团检测方法应用到遥感图像目标检测这一领域的工作还没有展开,也没有将之应用到复杂的地理目标分析,以及目标拓扑属性的描述中。本文将对基于社团检测的高分辨率遥感图像分类算法进行梳理和总结,分析本文的研究背景、目的和意义,并对国内外相关算法的研究现状进行介绍,指出社团检测算法在高分辨率遥感图像分类中的指导意义。

关键词： 交互信息   非负矩阵分解   社交网络   社团检测  

摘要： 社交网络的迅猛发展极大地方便了人们的日常生活、工作和学习,但也带来了大量复杂的交互行为和连接模式。如何有效地综合分析网络中的交互信息和网络节点之间存在的连接信息,进而完成高效的社团检测,是在当前网络多维属性的复杂背景下进行网络分析所面临的关键难题。基于此,从有效融合两类不同的异质信息研究出发,提出了一种基于交互行为和连接分析的社交网络社团检测(CDUILS)方法。该方法基于两类信息能够从不同的角度反映网络同一个社团归属的假设,采用联合非负矩阵分解架构,以迭代更新的方式,同时利用两类信息进行社团结果的获取。在真实网络数据集上的实验表明,与已有方法相比,所提方法能够有效融合两类信息进行社团检测,取得了更好的社团划分质量。

关键词： 一带一路   产业支撑网络   服务业   产业地位   社团检测  

摘要： 共建"丝绸之路经济带"和"21世纪海上丝绸之路"重大倡议,得到国际社会的高度关注和积极响应。本文采用2002-2012年"一带一路"国家的投入产出数据构建了服务业支撑网络,探究了网络的整体特征和我国服务业地位,并运用社团检测分析产业支撑情况。

关键词： Corporate tax evasion detection   Data mining   Hybrid intelligent system   Support vector machine   Neural network   Harmony search  

摘要： This paper concentrates on the effectiveness of using a hybrid intelligent system that combines multilayer perceptron (MLP) neural network, support vector machine (SVM), and logistic regression (LR) classification models with harmony search (HS) optimization algorithm to detect corporate tax evasion for the Iranian National Tax Administration (INTA). In this research, the role of optimization algorithm is to search and find the optimal classification model parameters and financial variables combination. Our proposed system finds optimal structure of the classification model based on the characteristics of the imported dataset. This system has been tested on the data from the food and textile sectors using an iterative structure of 10-fold cross-validation involving 2451 and 2053 test set samples from the tax returns of a two-year period and 1118 and 906 samples as out-of-sample using the tax returns of the consequent year. The results from out-of-sample data show that MLP neural network in combination with HS optimization algorithm outperforms other combinations with 90.07% and 82.45% accuracy, 85.48% and 84.85% sensitivity, and 90.34% and 82.26% specificity, respectively in the food and textile sectors. In addition, there is also a difference between the selected models and obtained accuracies based on the test data and out-of-sample data in both sectors and selected financial variables of every sector. (C) 2017 Elsevier Inc. All rights reserved.