关键词： 中心性   LPA算法   复杂网络   社团结构   社团检测  

摘要： 随着复杂网络不断涌现及其实际应用领域不断拓宽,复杂网络的理论研究受到广泛关注。社团结构和中心性特性是复杂网络中典型的结构特征,其中社团结构是指网络中的顶点可自然地形成不同的组,每个组即为一个社团。社团表现出高密度聚拢状态,即社团内部的节点之间联系较为紧密,位于不同社团的节点之间联系则相对稀疏得多。社团结构作为复杂网络的重要结构特征,包含的社团往往对应于网络的功能模块。通过检测网络的社团结构,可以发现网络的功能单元,研究结构与功能的对应关系,通过结构预测网络的功能。此外,已有研究表明,从社团层面往往可以发现单个顶点或整个网络层面未曾表现出来的一些特性。因此,社团检测方法的研究不论是在理论方面还是在实际应用方面都具有重要意义。研究人员已经提出了大量的社团检测算法,但很多算法的时间复杂度较高,无法有效地应用于规模较大的网络。针对这一问题,本文首先将频繁项集挖掘技术与LPA算法相结合,提出了改进算法LPAFI;其次基于局部中心性,提出了CG和CD两个社团检测算法。(1)LPAFI:该算法是基于LPA和频繁项集提出的确定性的社团检测算法。LPAFI算法首先通过多次运行LPA算法,将每次运行检测到的社团结构作为一条事务,从而构造出事务数据库,然后通过挖掘频繁项集的方法挖掘出满足条件的频繁项集,其次合并频繁项集,得到社团的大致结构,即“核心社团”。最后将不在核心社团的顶点作为“单点社团”,与核心社团进行社团合并,得到最终的社团结构。(2)基于中心性特性的社团检测算法:该算法根据社团结构的定义提出了新的局部中心性,即顶点与其邻居构成的社团,其内部边的数目占该社团总边数的比。局部中心性有一个重要的性质:中心性值较小的顶点往往处于社团的“边缘”。中心性增益算法又简称为CG算法,该算法首先通过重复的移除连接到顶点的边使得每个顶点的中心性值达到最大,从而将网络划分成小的社团,然后从得到的小社团中找出不稳定的小社团,将其划分成更小的社团,最后将得到的小社团进行合并,得到最终的社团结构;中心性扰动算法又简称为CD算法,该算法首先通过重复的移除对当前顶点中心性“贡献”较小的顶点之间的边,从而将网络划分成小的社团,然后从得到的小社团中找出不稳定的小社团,将其划分成更小的社团,最后将得到的小社团进行合并,得到最终的社团结构。为了验证本文提出的社团检测方法的性能,本文在7个网络数据集上进行了实验。实验结果表明,本文提出的方法能够快速地从网络中检测出高质量的社团结构。

关键词： 推特   社团检测   事件检测   情感分析   大选预测  

摘要： 随着互联网的发展,社交媒体在人们生活中的应用越来越多样化。而推特(Twitter)作为社交媒体中的佼佼者,已经成为近年来最流行的社交媒体应用之一。而社交媒体在政治事件中的影响也在与日俱增。2012美国总统奥巴马连任、英国脱欧公投等一系列政治事件的背景中都出现了推特的身影。推特在事件传播、反映民众的政治倾向上有逐步取代传统民意调查的趋势。目前在社交媒体上的政治倾向研究主要针对文本中的特定信息来进行分析,例如推文中的标签(hashtag)、提到(@)等。由于社交媒体数据不具有正式性,所以政治倾向分析的结果不够精确。同时对于社交媒体中的大选选情预测并没有特别完善的流程和方案。所以,本文通过图挖掘的方法,对社交媒体中的政治类事件进行分析研究。针对2016美国总统大选选情预测的问题,提出并设计了大选选情预测模型。本文的主要工作和创新点概括如下:(1)在推特数据上进行政治倾向情感分析和大选相关事件检测。在情感分析上,针对推特信息简短、非正式、缺乏补充信息的特点,本文采用了基于字典的情感分析方法,对推文的政治倾向性进行判断。同时对于情感分析中的反语鉴别难点,通过推文的表情符以及用户的历史推文来提升情感分析的结果。在事件检测中,针对美国总统大选的背景,本文采用了多次聚类、同义词拓展,关键词权重提升等方法,来对碎片事件进行整合。该方法提升了大选相关事件检测的性能。(2)利用图挖掘的方法来对推特数据进行研究分析。由于推特数据源上有多种多样的信息,例如用户,推文,图片,视频等等。而用户的点赞,转发和评论行为,往往也会表露出用户的政治倾向。所以,本文采用复杂网络分析方法,将不同类型的社交媒体数据投影到复杂网络中,再根据实际需求,对社交媒体复杂网络进行分析。在大选预测结果中发现支持总统候选人的用户社团。这种分析方法不仅仅适用于大选选情预测,还可以应用于社交媒体的舆论导向分析、用户影响力等方面。本文使用了真实社交媒体数据,分别对情感分析方法,事件检测模型和大选预测模型进行实验。实验结果显示,本文提出的大选预测模型可以对大选选情进行正确预测。

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

摘要： 互联网技术的发展推动了各种社交网络(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个概念,利用演化聚类框架进行重叠社团演化分析。实验结果表明,该方法不仅能有效地发现动态网络中重叠社团结构,而且还可以分析出社团随时间的演化模式。

关键词： 水体检测   化学社团   综合实践   创新意识   思维能力  

摘要： 以社团活动为载体,开展“1+1”河涌水质实践模式,发挥化学学科的优势,结合实际生活,通过实验了解身边河涌的水质状况,激发学生的学习兴趣,提升思维能力。让学生关注身边的事物,促进学生多样化发展,提高综合素质和能力。