关键词： 社会网络   影响最大化   结构洞   贪心算法   社团检测  

摘要： 互联网技术的发展推动了各种社交网络(Facebook,Twitter,新浪微博等)的蓬勃发展,社会网络中丰富的信息数据的挖掘以及通过社会网络进行的营销活动都给社会网络的研究带来了前所未有的挑战和机遇。网络营销是基于个人通过社会关系对周围朋友,家人或者同事进行影响力扩散而产生的“口碑”营销模式,在影响力扩散过程中,挖掘社会网络中最有影响力的用户变得十分关键。在这个背景下,影响最大化问题的研究变得炙手可热。影响最大化问题就是从社会网络中选出少量节点作为种子节点,从种子节点开始传播,在社会网络中获得最大的影响收益。目前已经提出很多社交网络中的影响最大化算法,例如各种贪心算法,启发式算法等,目的都是降低影响最大化算法的时间开销,提高算法的结果精度。然而,现有算法中鲜有考虑社会网络中节点的结构特征,例如结构洞节点具有鲜明的结构特征,与普通节点相比传播能力更强。忽略节点的结构特征的影响最大化算法的结果精度不够理想,而且利用结构特征可以有效的降低算法的时间开销。针对上述影响最大化研究中的挑战和问题,本文从以下两个方面进行研究:(1)研究基于结构洞理论的影响最大化算法。提出SG(Structure-based Greedy)算法降低影响最大化算法的时间开销,改善影响传播范围。SG算法的基本思想是为原始社会网络建立拉普拉斯矩阵,通过求解费德勒向量确定结构洞节点。本文综合考虑节点的结构特征和影响力,采用过滤的方式筛除非结构洞节点和影响力特别小的节点,缩小种子选取的候选集空间。在缩小的候选集中贪心的选取能够获得最大传播范围的种子节点。本文通过实验验证,本文提出的基于结构洞理论的影响最大化算法和现有算法相比,在算法时间开销和算法结果质量方面都具有明显的优势。(2)研究高效的结构洞发现算法和社团划分的关系。已有的结构洞发现算法主要开销在于计算节点的结构洞值,在大规模社交网络中,结构洞值的计算开销相当可观。本文提出借助社团划分的思想降低结构洞值的计算开销。首先将原始社会网根据节点的相似度进行粗糙划分得到简单社团结构,然后根据社团结构确定结构洞节点,最后计算结构洞节点与已有社团的相似度值作为节点的结构洞值。此外,在已知社会网结构洞节点的前提下,本文提出基于“二步”信息流理论的新的社团划分方法 SCD(Structure-based Community Detection)。SCD 算法的基本思想是首先将原始的社会网根据节点相似度获得粗糙社团结构,然后在粗糙社团中确定网络中的结构洞节点,最后从结构洞节点出发,根据“二步”信息流理论检测潜在社团,根据潜在社团与粗糙社团的相似度对比发现新社团。本文通过真实实验验证了提出的基于结构洞的社团检测算法的正确性和精确性都有很大的改进。

关键词： 复杂网络   社团检测   结构特征   聚类  

摘要： 随着信息技术的飞速发展,互联网已经逐渐融入人们的日常生活当中。在此背景下,出现了大量的复杂网络。社团结构是复杂网络的重要特征,研究复杂网络的社团结构能够帮助研究者更好地理解复杂网络的特征和功能。论文详细介绍了复杂网络的基本概念、网络模型以及社团检测的几类常用算法。在此基础之上,作者对不同类型的复杂网络的拓扑结构进行深入研究之后,挖掘其隐含的信息,并提出了两个改进的社团检测算法。(1)提出一个基于节点相似度的社团检测算法—AR-Cluster算法,用于检测节点具有属性特征的复杂网络社团结构。通过对IGC-CSM算法进行分析和研究之后,我们发现IGC-CSM算法在计算节点的结构相似度时,只考虑拓扑结构中节点的三种连接关系,却未深入分析网络拓扑中,这些节点内部的密切关系。为了能够检测结构紧密且属性特征相似的社团,AR-Cluster算法提出吸引度和推荐度两个概念,重新定义节点的结构相似度,然后采用结构相似度和属性相似度的协同策略,定义节点之间的相似度;最后使用K-Medoids算法进行聚类。实验结果表明,AR-Cluster算法对于节点具有属性特征的复杂网络,能够有效检测社团结构。(2)提出一个基于节点重要度的社团检测算法—NI-DF算法,用于检测一般复杂网络中的社团结构和重叠点。算法分为两个阶段:网络硬划分和重叠点检测。第一阶段,NI过程,首先基于网络结构特征提出节点重要度的计算方法,然后选择重要度最大的节点作为簇的中心节点,通过TROC算法的中心节点扩展方法,最终得到网络的硬划分。第二阶段,DF过程,在第一阶段得到的划分结果之上,提出区别函数用于检测重叠点。实验结果表明,NI-DF算法能够较好地检测社团和重叠点。AR-Cluster算法目前只研究节点属性数目相同的社团检测问题,未考虑属性不对称的情况。NI-DF算法检测重叠点过于粗糙,需要细化。

关键词： 科技社团   科技创新   形成性评价  

摘要： 目的:进一步探索大学生创新社团实践能力培养与形成性效能评价改革.方法:通过问卷调查形式采集大学生参与创新项目、论文发表与分享奖励等情景过程中产生的正能量信息,包括态度、自信与成就感;采集大学生创新实践活动对专业学习促进作用等形成性效能评价的信息;运用创新社团与非社团成员A、B组"两两"法进行效能检验,对比两组创新实践能力培养效果的差异.结果:通过对科技创新实践兴趣感、促进专业学习自信感和获得社会认可度的成就感问卷分析得知,A组学生优良率为100%,而B组学生优为0,良率为76.91%.检测A组学生的形成性效能评价明显优于B组.结论:A、B组"两两"效能检验有显著性差异.

关键词： 复杂网络   社团检测   AP聚类   并行化  

摘要： 复杂网络作为生活中电力系统、通信网络和万维网等复杂系统的高度抽象,复杂网络社团结构表示着网络中的节点聚合的趋势,是复杂网络的一个重要的拓扑属性。社团检测可以有效认识复杂网络的结构和功能,进而对网络中的行为模式进行预测和分析,对复杂系统的研究与应用具有重要的意义。现有的大多数复杂网络社团检测算法都在追求算法的准确度,而忽略了时间复杂度高的问题。本文针对目前社团检测算法在处理大规模数据时在速率上不足的问题,设计了一种在Hadoop平台下进行的社团检测的并行化方法。本文主要工作如下:1.本文对复杂网络的基础知识和现有社团检测算法进行了研究。简述了复杂网络基本理论,介绍了社团检测算法的研究现状,重点介绍了几种流行的社团检测算法的基本思想和计算过程。2.由于可以通过相似度将复杂网络的社团检测问题转化为相似节点的聚类问题,本文对AP聚类(Affinity Propagation Clustering)进行了深入的研究,针对传统AP聚类在计算相似度时用欧氏距离而没有考虑到复杂网络的集聚特性的问题,本文采用一种改进的Jaccard系数来计算复杂网络节点之间的相似度。3.针对社团检测AP聚类在处理大规模数据速度慢的问题,结合大数据分析工具Hadoop,设计一种分步并行化的AP聚类社团检测方法,将AP算法整个过程分步进行并行化来实现社团检测的AP聚类算法的并行化。在PC机上搭建Hadoop集群,在不同规模的数据集上对本文设计的计算方法进行测试。实验中分别对本文设计的方法在算法准确度和方法性能上进行的测试,结果表明,本文方法在进行社团检测时具有良好的准确度和计算性能,尤其是在大规模数据集中,本文方法能够取得较好的加速比。

关键词： 社团检测   有向网络   相似度   CNM算法   MapReduce  

摘要： 社团结构是复杂网络研究的热点,近些年来提出了许多社团检测算法,但目前提出的大多数算法主要适用于无向网络的社团结构挖掘,对于有向网络这些算法往往难以取得较好的社团检测效果。另外,大规模数据量的产生使得传统的社团检测算法不能满足计算效率以及数据存储等方面的需求。因此,寻找大规模有向网络的社团检测算法对于社团的研究具有重要的意义。本文主要工作如下:(1)对复杂网络的理论基础、社团的概念以及Hadoop技术进行了详细的介绍,分析了一些具有代表性的社团检测算法并指出其各自的优缺点;深入研究了社团检测的研究现状和所面临的问题。(2)研究基于相似度的有向网络社团检测算法,该算法利用网络的方向信息指导节点相似度的计算,从而把有向网络的拓扑结构信息转化为代数值,然后利用相似度改进CNM算法,结合CNM算法本身的优点提高了算法的准确性和适用性。(3)针对传统社团检测算法在单机环境下不能有效处理大规模网络的局限性,使用MapReduce分布式编程模型对本文的算法进行并行化,使得大规模网络数据的社团检测得以实现。基于相似度的有向网络社团检测算法利用相似度改进CNM算法,使得算法与网络的拓扑结构相关,并且利用方向信息指导相似度的计算,使得有向网络社团检测得以实现。在单机和分布式环境下分别进行实验,结果表明本文的算法具有较高的准确性,对大规模网络数据的处理具有高效性。

关键词： 复杂网络   重叠社团发现   话题检测   青少年  

摘要： 社交媒体话题检测一直是个热点问题,由于社交数据杂乱异构,且具有时效性,语义模糊性等特点,话题检测也是个难点问题.研究利用复杂网络对社交文本数据进行建模,并结合一种基于极大团凝聚层次聚类的重叠社团发现方法实现了社交话题的检测.文本数据建模中,通过自定义突发系数量化话题词,即把话题词看作具有时域分布偏好的关键词,并通过自定义相关系数连接话题词,构建话题网络.为使自定义系数更适用于动态数据环境,实验结合真实数据进行了适应性测试优化系数.文章把采用EAGLE重叠社团发现方法在公开数据集上评测,根据Q函数值显示结果明显优于当前一些重叠社团发现策略,研究对采样的60万条青少年社交数据进行了话题分析并可视化了分析结果.

关键词： 动态网络   重叠社团   局部优先   演变模式   时序平滑框架   Ego社团  

摘要： 社团检测简化是重要的图挖掘问题,动态网络上的重叠社团检测及其社团演变模式是近年来的研究热点,但将静态网络的局部优先的社团检测算法应用到动态网络的重叠社团及其演变模式检测上的研究较少。为此,提出一种局部优先的动态网络重叠社团演化分析方法。该方法在每个网络快照上利用标签传播算法检测局部Ego社团,通过不断合并局部Ego社团得到全局社团结构。在此过程中引入社团相似度与关联度2个概念,利用演化聚类框架进行重叠社团演化分析。实验结果表明,该方法不仅能有效地发现动态网络中重叠社团结构,而且还可以分析出社团随时间的演化模式。

关键词： 复杂网络   社团检测   重叠社团   局部扩充  

摘要： 基于局部扩充的重叠社团检测算法由单个节点或团出发,不断添加新的节点而获得最终的社团划分,但现有算法均为每次添加一个节点,没有充分考虑所添加节点的局部信息,从而影响了社团检测结果的准确性.为此,文中提出了一种基于单步添加团的重叠社团检测算法,该算法从一个团开始,通过不断添加此团邻居内适应度增值最大的团,使算法在局部扩充时不仅考虑了所添加节点与已有社团的连接紧密性,而且考虑了所添加节点内部的连接情况.在真实网络和计算机生成网络上的实验结果表明,与现有基于局部扩充的重叠社团检测算法相比,文中算法可以更准确地检测出复杂网络中的重叠社团.

关键词： 社团检测   复杂网络   频繁项集   社团结构   标签传递算法  

摘要： 首先充分利用LPA的不确定性来构造事务数据,然后通过挖掘频繁项集的方法发现核心社团结构,对单个顶点构成的社团和核心社团进行合并,得到最终的社团结构.最后通过在5个实际网络上进行实验,实验结果表明,该方法在保持LPA算法高效率的情况下,能得到更好的、确定性的社团结构.

关键词： 共词分析   复杂网络   连边社团检测算法   科学计量学  

摘要： [目的/意义]传统共词分析的聚类算法存在以下不足:1关键词只能被划归一个聚类;2聚类过程对分类数目的确定缺乏严格判断标准。针对以上问题,采用复杂网络理论进行改进研究。[方法/过程]采用连边社团检测算法对关键词进行聚类,以科学计量学为例进行实证研究。[结果/结论]分析结果表明:算法对关键词的聚类结果有较好的改进效果,能够把核心度高的关键词同时划分到不同的研究主题之中,克服传统聚类算法的不足,而且划分密度可为聚类数目的确定提供客观判断依据。