关键词： 聚类分析   量子聚类   核熵主成分分析   结构相似度   社团检测  

摘要： 数据挖掘技术是近年来在人工智能、信息决策及数据库领域研究的热点之一。在众多数据挖掘分析工具中，聚类分析是一种最常用、最有力的工具。聚类分析的目的是将抽象出来的对象或样本集合根据相似度划分成若干具有特殊意义的团或者类，从而更好地理解和分析数据，发现样本的潜在分布结构。迄今为止，人们提出了大量聚类算法。但随着数据规模（包括样本个数及数据维度）越来越大，而先验知识相对匮乏，传统的聚类算法效果并不尽如人意。受量子力学启发，量子聚类（Quantum Clustering, QC）将聚类问题作为一个物理系统，在波函数已知的情况下，通过求解薛定谔方程式（Schr dinger equation）导出势能函数，从势能能量点的角度来确定聚类中心。作为一种基于划分的无监督聚类算法，量子聚类能够克服传统方法的一些缺陷，如对初始值和噪声敏感，聚类类别数需要事先给定等。为了进一步提高数据的聚类精度和运算效率，本文在传统量子聚类基础上做了相关的改进工作。由于复杂网络的社团检测与数据的聚类分析具有一定的相似性，量子聚类同样可以应用于社团检测问题研究。本文所做的主要工作如下： （1）通过研究了量子聚类的基本理论及特点，提出了一种利用核熵主成分分析的量子聚类算法。为了获取数据的潜在结构，采用核方法将原始数据映射至高维特征空间，并用熵值为评价标准筛选特征向量，以获得核熵主成分。为了增强算法的局部特性，同时提高算法的运行效率，在量子聚类算法中引入K近邻策略，并通过梯度迭代获得最终的聚类结果。通过实验分析，不论是聚类效果还是鲁棒性，该算法远优于其他对比算法，尤其是对线性不可分数据集。 （2）在对已有的复杂网络社团检测算法进行深入研究的基础上，将量子聚类应用于复杂网络的社团检测问题研究中。首先为把网络转化为适合聚类分析的数据结构，构建了结构相似度矩阵，度量网络中节点之间连接关系的强弱。同时，在量子聚类过程中，引入节点的邻接信息，在提高算法局部分析能力的同时，降低算法的时间复杂度。 （3）针对大规模复杂网络的社团检测问题，借鉴小规模社团检测解决方式，综合考虑检测精度和运算效率两方面的因素，提出了两点改进策略以增强量子聚类算法对大规模网络社团检测的处理能力。该算法采用网络层次划分方法，将原始大规模网络划分成若干个较小的子网络，并在子网络中构建相似度矩阵。此外，采用Nystr m方法逼近结构相似度矩阵的特征向量，进一步提高算法的运行效率。仿真结果表明，该算法能够取得较好的检测效果，且运算时间较之于原来的算法大大降低。

关键词： 社团检测   社会网络   邻居相似性   半监督   数据挖掘  

摘要： 社团检测分析作为社会网络领域中一个重要的研究领域,在国内外都受到学者们的广泛关注。随着数据挖掘技术的普及和互联网的发展,社团检测的地位也越来突出。其中标签传播算法(LPA:Label Propagation Algorithm)因其具有线性的时间复杂度受到学者们大力推崇,基于层次凝聚和层次分裂的社团检测算法(代表算法如FastQ和GN算法)为社团检测领域也做出了巨大贡献。然而,标签传播算法具有不稳定性,对标签更新顺序比较敏感,而基于层次凝聚和层次分裂的社团检测算法由于时间性能过低,在一定程度上限制了它们应用的广泛性。 本文设计了两个社团检测算法： (1).基于邻居相似性的社团检测算法(NSA:Neighbor Similarity Based Algorithm):NSA算法分为两大步,第一步是根据相似性阈值对网络图进行初步的划分,得到社团结构的轮廓；第二步是对第一步得到的社团结构进行优化,得到更加清晰的社团结构。NSA算法在社团检测过程中只考虑每个节点和它的邻居节点之间的相似性关系,而不考虑和其它节点之间的相似性关系,这点和LPA算法有一定的相似性,只不过LPA算法考虑的是每个节点和其邻居节点的标签关系。所以NSA算法的时间性能和LPA算法相比不会相差甚远,NSA算法也具有接近线性的时间复杂度。同时NSA算法在多个数据集上的实验证明,用NSA算法可以得到高质量的社团划分结构。 (2).基于选点的半监督社团检测算法(SSCDAWSP:Semi-Supervised Community Detection Algorithm With Selected-Point):SSCDAWSP算法在研究社团检测特点和半监督学习理论过程中,发现了社团检测和半监督的结合点,将半监督思想应用到社团检测中。在SSCDAWSP算法设计过程中设计了节点的边界值和核心度定义,以此为选点提供规则基础,另外设计了节点之间的归属度定义,以此来判断相邻节点之间的社团划分关系。SSCDAWSP算法在选点过程中需要用到节点边界值信息和核心度信息,因此计算节点的边界值和核心度会消耗一定的时间性能。但相比其他大多数社团检测算法,SSCDAWSP算法的时间性能还是有一定优势,同时通过多个数据集上的实验证明,SSCDAWSP算法的社团划分精度可达到非常理想的期望。

关键词： 动态网络   社团检测   局部模块度   重叠性   层次性  

摘要： 随时间缓慢变化的复杂系统可以建模为抽象的动态网络。由于动态网络在社会学、生物信息学、物理、计算机等研究领域有广泛应用,越来越受到科研工作者的重视。近几年动态网络成为科研热门领域,具有实际意义的动态社团结构是动态网络中普遍而又重要的特征。当前动态社团检测算法仍主要基于静态检测方法的相关理论基础。基于极大化Q函数的动态社团检测算法存在分辨率问题,即为了获得更优的模块度值小社团常被合并为大社团。另一方面,很多动态社团检测算法需要设置多个参数或阈值,这就要求对网络有一定的先验知识或需要借助Q函数对结果进行判定。而且,已有的动态社团检测算法不能识别出如社团间的重叠结构等重要拓扑特征。为解决上述问题,本文提出了一种基于进化聚类和局部模块度的重叠结构动态社团检测算法。基于局部模块度的社团检测方法,将整个网络的社团检测问题转化为自底向上的凝聚问题,能适应网络中规模不等、密度不均的社团结构。通过统计节点随机游走行为特征,增强无权网络的分辨率,并使用进化聚类框架下的时序开销嵌入技术来平衡当前社团的拓扑特征与历史信息,从而检测出社团演化的动态规律。该算法仅在进化聚类过程中对平衡因子进行设置,无需领域先验知识。本文使用真实网络数据对该动态网络社团检测算法进行评估,包括Drosophila melanogaster数据集和科学家合作网络(DBLP)数据集。实验结果表明,基于进化聚类框架和局部模块度的动态社团检测算法与基于进化和局部优先的算法相比,扩展模块性指标提高了15%,显著提高了Drosophila melanogaster社团检测结果质量。并且,该算法能有效刻画出DBLP中科研团队的动态演化过程。综上,该算法可适用于无社团结构先验知识的网络,有效检测出具有特定意义的小规模社团及其重叠结构。

关键词： 复杂网络   社团结构   邻居   依赖度  

摘要： 社团结构是复杂网络的一个重要属性,在生物学、社会学等众多学科领域有着广泛的应用,越来越受到人们的关注。近年来有很多的社团结构探测算法被提出来,但是这些算法在计算复杂度和准确度上仍然存在着一些不足。本文从节点间的邻居关系出发,提出了两种检测社团结构的算法,主要工作如下： (1)给出了某种社团结构划分下单个节点划分效果的评价：强社团结构节点、弱社团结构节点、二义性社团结构节点和非社团结构节点。这种评价方法的理论基础是强社团结构和弱社团结构的定义,对于分析和判断一种社团结构的划分效果具有一定借鉴意义。 (2)提出了一种改进的派系查找算法,从当前网络中度最小的节点开始,每找到一个派系就删除只存在于这个派系中的边；从大到小选取派系来组成社团或者将派系中的节点吸收进社团。在几个实际网络上对算法进行了测试,并对结果进行分析,结果显示该算法在派系查找上相对现存的其它算法有更高的时间效率和更低的空间资源需求,并且对网络的社团结构划分效果较好。 (3)提出了基于节点间依赖度的社团结构检测算法,这种算法只需考虑一个节点的邻居节点,即可将该节点划分到社团。给出节点对节点、节点对社团的依赖度以及节点对社团的条件依赖度,详细介绍了算法的实现过程,在几个实际网络上对算法进行了测试,并对结果进行分析,该算法有较低的计算时间复杂度,对社团结构的划分结果也比较理想。 本文得到国家自然科学基金(61370145,61173183,60973152),高等学校博士点专项科研基金(20070141014),辽宁省高等学校优秀人才支持计划资助(LR2012003),辽宁省自然科学基金(20082165),中央高校基本科研基金(DUT12JB06)的联合资助。

关键词： 社团检测   复杂网络   自然最近邻居   结构相似度  

摘要： 很多自然和社会中的复杂系统，都可以按一定的方式描述成图或者网络。这些网络具有复杂的内部结构，因此称为复杂网络。近些年来，随着复杂网络在众多领域中的广泛应用，复杂网络中的社团检测与分析也越发受到人们的注意。社团结构的特点在于社团中的节点处于一种高密度的集聚状态而社团之间的节点则处于一种低密度的连接状态，而社团检测最基本的作用是将个体进行社团分类，将个体分配到若干社团中。该问题的深入研究有助于以一种分而治之的方式研究整个网络的模块、功能及其演化，更准确地理解复杂系统的组织原则、拓扑结构与动力学特性。 到目前为止，人们提出了许多算法来检测复杂网络中的社团结构。典型的社团检测算法大致可以分为传统的分级聚类和图形分割算法，比如Kemighan-Lin算法和谱平分算法，以及GN算法和Newman快速算法。这些算法都有各自的优势和不足，都有其特定的适用范围，还需要进一步改进。如有的算法在计算效率方面，有的算法在算法思想方面仍值得改进。但是，这些算法绝大多数都是将网络检测成为若干个相互分离的社团，准确度在一定程度上取决于初始条件的选择，并且不能识别网络中的一些重要节点。2011年Xu Xiaowei提出了一种基于结构相似的社团结构检测算法SCAN。该算法的优点是不仅可以对网络进行社团结构的检测，并且可以找出网络中的特殊节点。但该算法的不足在于对参数的选择非常敏感，难以保证检测出的社团的质量。 本文在SCAN算法的启发下，借用结构相似度的思想，利用自然最近邻居算法无需参数的优势，提出了一种新的社团检测算法——基于自然最近邻居的社团检测算法CD3N。同时，邻居本身就包含一种社团的概念，这使得自然最近邻居算法可以很好的理清复杂网络中的节点关系。本文对原有的自然最近邻居概念进行了改进，使用结构相似度代替距离作为邻居的判定依据，详细分析了各种自然最近邻域图的优缺点并提出了一种适用于社团检测的自然最近邻域图的构造方法。最后使用真实数据集进行实验，与源数据划分结果和SCAN算法结果进行对比分析，证明了算法的可行性和有效性。

关键词： 社会网络   社团检测   层次凝聚   主动学习   半监督  

摘要： 近年来,复杂网络研究作为一个新兴的研究方向,已经成为了计算机科学、统计物理学、社会学、生物信息学等领域的一个热点问题。复杂网络具有小世界性、无尺度性、模块性等特性。通常,一个复杂网络包含有若干个社团,同一个社团内的节点联系紧密,不同社团间的节点联系疏松。发现复杂网络的社团结构是理解和分析复杂网络的一种重要工具和手段。有效的社团检测算法,可以划分出清晰的社团结构,降低复杂网络的研究难度。发现复杂网络的社团结构是复杂网络研究中的一个重要课题,具有重要的应用价值。 本文通过对现有社团检测方法的研究分析,提出了两个新的社团检测算法CDACSM和ASCD。CDACSM算法是基于相似度度量的层次凝聚社团检测算法,该算法主要解决层次凝聚社团检测算法存在的两个问题：1)容易产生极小和极大社团；2)一旦节点的标签被划分错误,直到社团检测结束都是错误状态,无法更正。CDACSM算法通过定义单点社团间的相似度、社团间的相似度等度量标准和单点社团和社团间的合并规则等,在一定程度上有效地避免了以上两个问题。ASCD算法是基于主动学习的半监督社团检测算法,该算法的设计主要针对以下三种社团划分结果不清晰的情况：1)半监督学习的标签数据质量不理想时；2)网络结构比较复杂和模糊时；3)社团规模大小相当时。ASCD算法定义了相关度、最相关节点、凝聚力等度量标准,提出了标签数据的主动选取方法和利用这些标签数据进行半监督学习的策略,在以上三种情况下获得了较好的社团检测效果。 本文利用多个真实的复杂网络数据集和评判基准图数据集对CDACSM算法和ASCD算法进行了实验验证。通过模块度、准确率、运行时间效率等多项指标对CDACSM算法和ASCD算法进行评价,实验结果表明本文提出的两种社团检测算法具有较好的社团检测效果且运行效率较高。

关键词： 复杂网络   社团检测   重叠社团   局部优先   标记传播  

摘要： 信息技术的迅猛发展，特别是互联网的发展，使人们已迈入了“网络时代”。复杂网络的研究已成为当前炙手可热的研究领域之一。作为复杂网络研究的重要课题之一，社团检测得到的极大的研究与发展。传统的社团检测方法大多集中在检测非重叠社团上，然而真实网络的一个重要的特性是网络中存在大量的重叠节点。因此，高效准确地检测出复杂网络中的重叠社团结构能够更准确真实地揭示复杂网络的拓扑结构。 针对复杂网络中普遍存在重叠节点这一特性，本文提出了两种社团检测算法：局部优先的重叠社团检测算法和增强的多标记传播社团检测算法。局部优先的重叠社团检测算法针对每个节点生成其邻居网络，通过构造节点邻居网络的一棵最大生成树，从中提取该节点的所有局部圈子，以局部圈子为最小单元，通过定义局部融合策略，实现全局重叠社团检测；增强的多标记传播算法是一种基于标记传播的社团检测算法，但是该算法能同时检测出复杂网络中的重叠社团结构和非重叠社团结构。算法首先扩展了传统标记传播算法节点只能存储单一标记的能力，通过设置从属因子使节点能够同时保存多个标记。同时，通过模拟一种特殊的投票过程设计了新的标记更新策略——增强的标记更新策略。 通过对比分析大量真实网络和生成网络上的实验表明：本文提出的两种社团检测算法能够高效、准确地检测出复杂网络中潜在的社团结构。

关键词： 复杂网络   社团结构   边模式   网络检测  

摘要： 为了检测网络的社团结构,提出基于统计推理的边模式社团检测方法,在计算机生成的网络中和实际网络检测了算法的可行性和准确性,并与现有的两种基于边模式的社团检测方法做了比较。实验表明,所提出的方法可以快速有效地检测出重叠社团,在性能上优于后两种方法。

关键词： 用户社团   社团变化   异常检测   复杂网络  

摘要： 为准确刻画Internet上的用户群体行为,发现网络中潜在的协同攻击。首先从采集的流中提取用户的社会行为特征,构建用户交互网络(HIN)。然后,基于HIN的用户社会行为的相似性,定义用户社团,并定义5个指标对用户社团的变化进行定量描述,采用基线法设置每个指标的检测区间。期间,为了适应网络环境的动态性,引入了固定时间宽度的滑动窗口机制实现自适应网络异常群体行为检测。提出了一种通过对用户社团变化的监测实现网络异常群体行为检测的方法。通过在两个实际网络流数据集上进行试验验证了基于用户社团变化的方法可以检测大型网络的异常群体行为。

关键词： Whistle-blowing   Fraud   Internal reporting   Whistle-blowing policies   Hotlines  

摘要： In order to provide an effective whistle-blowing system, it is expected that companies would provide employees with a high level of disclosure regarding the whistle-blowing process. This study investigates variation in the extent of whistle-blowing disclosures. As a measure of whistle-blowing implementation, this study further examines the provision of a hotline channel. The results suggest that the extent of whistle-blowing disclosures is positively associated with the permissibility of anonymous reporting and organisational support for whistle-blowing, the number of external directors on the audit committee, and the existence of concentrated shareholdings. The mere existence of whistle-blowing disclosures could simply be symbolic. The findings also indicate a greater likelihood of the provision of hotlines when companies are larger in size, have a higher level of current inventory, are cross-listed in the US, and permit anonymous reporting.