符号社会网络社团结构发现及符号预测研究

论文摘要

社会网络中,成员之间不仅具有合作、朋友、支持、喜欢等积极的社会关系,还存在竞争、敌人、反对、讨厌等消极的社会关系。这种同时具有正反两种社会关系的网络称之为符号网络。符号网络因其包含更全面的社会关系,已成为国内外学者研究的热点之一。社团结构及符号生成机制作为符号网络分析的基础,对理解社会系统的组织构成、提高社会化服务水平具有理论及现实意义。本文分别从社团发现及符号预测两部分内容展开对符号社会网络的结构分析。在符号网络社团发现的研究中,基于网络进化的社团发现算法在运行效率上具有其他算法无法比拟的优势。网络进化时往往只考虑一种交互作用模式,避免了大量的复杂计算,这使得网络的进化过程仅仅是一种时间上的节点状态更新过程。在进化过程中,属于同一社团的节点由于联系的紧密或相互的吸引,会出现一致的收敛状态;而属于不同社团的节点由于联系的疏松或相互的排斥,会形成不同的收敛状态。针对已有算法的缺陷,提出了一种新的进化机制,节点状态值的变化是所有邻居对其影响权重的总和。为排除初始化对网络进化的影响,令网络初态为单位矩阵,即初始时刻每个节点属于一个唯一的社团。为提高社团的凝聚力,节点在进行社团选择时总是选择对其最优的社团,即使其平衡程度最高的社团。由于节点进化与划分目标一致,任一点的进化,总存在目标函数值的增加,因此网络最终会进入收敛状态。而且,在网络进化过程中,某一节点进化后,其邻居的进化会直接受到该节点进化结果的影响,所以节点进化具有累加效果,而且网络越密集收敛速度越快。在进化过程中,为排除节点随机进化的影响,同时满足平衡程度最大化,对交叉社团设置了合并条件。节点在进化时不需要针对不同网络调节参数,普适性高。从实验结果来看,新的进化算法在平衡度、符号模块度及标准互信息等评价指标上都优于已有的算法。对发现的社团结构,本文做了以下几点分析:（1）对社团结构的嵌入性作了分析,通过定义节点在社团内的正负适应度概念,发现节点可根据在社团内的嵌入程度的高低分为两类,一类节点在社团内嵌入程度较高,其在社团内存在具有较高的正适应度,这类节点往往巧妙的镶嵌在社团内部;另一类节点在社团内的嵌入程度较低,其在社团内具有较低的正适应度,甚至在其他社团内仍然存在正适应度,这类节点往往位于社团与社团的交界处,充当中介人身份。通过定义社团间密度的概念,发现网络中社团与社团的关系并不对等。存在某些社团之间的对抗或相异关系明显弱于其他社团之间的对抗或相异关系。（2）从平衡性与模块性、度量尺度与方式两方面对比了社团结构评价指标——平衡度及符号模块度,发现符号模块度指标倾向于将网络划分成规模较小的社团,而平衡度指标则不然,其对社团规模并无明显约束。就划分目标而言,基于平衡度划分社团时,整体目标与单个节点的目标具有一致性;而基于符号模块度划分社团时,追求的是网络模块性,单个节点并无模块性可言。（3）基于结构平衡角度对重叠社区进行了探索分析。通过对社团结构的平衡性分析,发现重叠节点是破坏网络平衡的关键节点。提出了衡量节点平衡性的引理,即节点所在的“仅包含一条负边的简单圈数”越多,节点越不平衡越可能为重叠节点。通过分析不平衡圈的构成形式,提出了冲突边挖掘算法,进而实现了重叠节点的挖掘。将该算法应用到国际军事联盟及对抗关系网络,从社团结构、结构平衡、符号预测及节点排序等方面分析了重叠节点的性质及应用。本文从符号网络邻接权矩阵的谱特征出发,分析了邻接权矩阵的特征向量与网络平衡性的关系,指出网络中边的平衡性可以通过其对应的特征向量元素来衡量。从而提出了基于主特征向量的分层划分谱算法以及基于前k个特征向量的逐级划分谱算法:（1）在4.2节分析了当网络划分为两个社团时,其邻接权矩阵的主特征向量可以作为社团结构的指示器,特征向量中正元素所对应的节点为一个社团,负元素所对应的节点为另一社团。而对于每个社团,可以通过计算其对应的子网络的邻接权矩阵的主特征向量,再次将其划分为两个子团。这样通过分层划分的思想实现对符号网络社团结构的发现。（2）由分析可知,邻接权矩阵的每个特征向量均可以将网络划分为两个社团,而不同特征向量对应的划分结构的平衡性与其特征值大小相对应,即特征值越大其对应的特征向量平衡性越高。因此,可以通过逐渐增加特征向量来发现平衡性最高的社团结构。在4.3节中,通过生成不同的人工符号网络,验证了基于特征向量进行划分的合理性。（3）由于标准化条件下特征向量元素值的连续性（元素值大于-1小于1）,当元素值近似为0时会不可避免的造成划分的误差。本文根据目标函数设计了优化阶段。在优化阶段,每个节点在其所属社团内的适应度被计算,如果节点在其他社团内的适应度大于其在所属社团内的适应度,则调整其到适应度最大的社团内。节点在调整其所属社团时只进行局部（节点周围邻居）计算,使得优化阶段效率非常高,这点在4.3节实验中得到了证明。本文通过对边符号生成机制的针对性分析,提出了一种高度对称的四边形结构,该结构同时符合社会平衡理论及社会地位理论,因此可以有效过滤由于网络连接的复杂性带来的干扰因素,并从中提取了能有效反映边符号生成机制的节点对之间的相似-相异性。此外,通过对真实大规模符号网络中节点的正负度分析,提出了可以有效反映节点对在生成边时的态度倾向性——偏好性及声誉值。构造了基于以上四种影响因素的边符号预测模型。通过在三种真实大规模符号社会网络上的模拟实验及与已有预测方法的结果对比,证明了预测模型的科学性与合理性。分析了预测算法的复杂度,由于构成预测模型的影响因素反映了目标边的局部结构特点,使得预测算法的复杂度非常低,适应于大规模符号网络。

论文目录

摘要

Abstract

第一章绪论

1.1 选题理由及意义

1.2 国内外研究背景

1.2.1 社团发现

1.2.2 符号预测

1.2.3 其他相关研究

1.3 本文组织结构

1.4 本文创新点

第二章社团结构发现与符号预测理论基础

2.1 引言

2.2 符号网络基本概念及理论

2.2.1 符号网络定义及表示方法

2.2.2 结构平衡理论

2.2.3 社会地位理论

2.2.4 相似性度量方法

2.2.5 节点重要性度量

2.3 社团发现

2.3.1 社团结构概念

2.3.2 社团结构度量

2.4 符号预测

2.4.1 符号预测概念

2.4.2 符号预测度量指标

2.5 本章小结

第三章基于节点进化的社团结构发现及分析

3.1 引言

3.2 DBAS及DEC算法

3.2.1 算法描述

3.2.2 算法分析

3.3 基于节点进化的社团发现算法

3.3.1 算法思想及描述

3.3.2 算法流程

3.3.3 实验及结果分析

3.4 社团结构嵌入性分析

3.4.1 社团结构分析

3.4.2 节点分析

3.5 社团结构评价指标分析

3.5.1 平衡度与符号模块度

3.5.2 度量尺度与方式

3.6 重叠社区

3.6.1 结构平衡角度下重叠结构挖掘

3.6.2 重叠结构性质及应用

3.7 本章小结

第四章基于邻接矩阵特征向量的社团发现算法

4.1 引言

4.2 基于主特征向量的分层社团发现算法

4.2.1 算法思想及描述

4.2.2 算法流程

4.2.3 实验与分析

4.3 基于top-k特征向量的社团发现算法

4.3.1 算法描述及思想

4.3.2 算法流程

4.3.3 实验与分析

4.4 结论与讨论

第五章基于网络局部结构特点的符号预测

5.1 引言

5.2 方法与模型

5.2.1 相似性与相异性

5.2.2 偏好性与声誉

5.2.3 预测模型

5.2.4 算法及分析

5.3 实验结果及分析

5.3.1 评价指标

5.3.2 不同数据集上的结果对比

5.3.3 与已有预测算法的结果对比

5.3.4 参数分析

5.4 讨论与结论

第六章总结与展望

6.1 工作总结

6.2 研究展望

参考文献

读博期间完成的论文

致谢

文章来源

类型: 博士论文

作者: 朱晓宇

导师: 马英红

关键词: 社会网络,符号网络,社团结构,符号预测

来源: 山东师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 山东师范大学

分类号: O157.5

DOI: 10.27280/d.cnki.gsdsu.2019.000100

总页数: 110

文件大小: 9400K

下载量: 221

符号社会网络社团结构发现及符号预测研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢