文摘
语义网络,社交网络是一种包含巨大的节点和复杂的语义信息,和传统的社区检测算法不能给理想的有说服力的社区。解决语义社交网络检测的问题,提出了一种聚类社区检测算法基于PSO-LDA模型。作为语义模型是LDA模型,我们使用吉布斯抽样方法,可以定量参数从语义信息映射到语义空间。然后,我们提出一个算法策略的语义关系来解决重叠社区发现。最后,我们建立语义模块化(SimQ)评估发现语义社区。PSO-LDA模型的可行性和有效性,实验分析的语义验证模块化。
1。介绍
随着社会的发展和科学技术的提高,语义的社交网络正在迅速发展,许多语义网络,像推特和微博,到目前为止做了一个微不足道的影响在我们的生活中。在这些网络中,不同的人有不同的小社会”世界”被称为社区(1]。因此,研究人员关注社区检测不仅将网络分成多个模块,也使理解深刻了解有趣的属性在语义的社交网络。在实际应用程序中,语义社区有很大的推广智能信息检索,营销管理,个人服务,和其他信息管理领域2]。迄今为止,研究社区检测主要反映在以下三个类别:拓扑社区检测(3),社区检测综合施工(4),和语义社区检测。
拓扑社区检测代表了先锋工作,目标是研究拓扑结构和社交网络划分成几个独立的网络。代表算法包含模块化优化(5],GN [6],FN (7]。然后,研究人员逐渐关注重叠社区比先前的研究网络,可以更真实。因此,CPM (8)提出了检测重叠社区。不久之后,社区检测综合施工收到更多的关注在社会网络和许多代表提出了算法,包括线性调频(9],鹰[10,干椰子肉11,恶魔12),等等。纽曼和实验后13)提出了一个凝结的谱聚类方法与电导和边。在他们的方法中,最相似的节点是基于特征向量空间和边的凝聚。但这种方法只适用于nonsemantic社交网络。大兴趣的语义网络,语义社区检测进入研究人员的眼睛。杨和McAuley [14)提出了CESNA模型开发社区利用边缘结构和节点属性。这种方法会导致更精确的社区检测以及改进的健壮性在网络结构噪声的存在。但是当这个方法应用到语义网络,它执行不稳定。Reihanian和阿里15)提出了一个通用框架的重叠社区发现社交网络与社交网络特别关注评级为依据的。这个框架考虑了信息共享的用户为了找到有意义的社区。语义社区最重要的特点是节点在这些社区不仅有拓扑关系,而且自己的语义上下文。必须考虑语义数据挖掘的文本分析,和许多语义社区检测算法应用潜在狄利克雷分配(LDA) (16)模型为核心的模型。
在过去的几年里,在语义分析社交网络已经成为流行。大多数这些算法利用LDA模型为基本模型。SVM-DTW方法提出Solera、Calderara Cucchiara [17)可以在天使的工作网络。这种方法使结构简单,需要更少的输入参数,但语义上下文并不认为,少发现社会与真正的语义网络。李明和她18不仅]提出了GRTM模型,模拟用户的利益作为潜在变量通过他们的信息,也考虑了用户由于其信息之间的连接。该方法结合上下文分析发现社区的拓扑分析和相似几乎是接近真实的语义的社交网络,但它是缺乏在采样的特点,使一些模糊不相关的社区。肖和刘19)提出了使用prediscretizing GLDA-FP模型可以扩展这个话题可以帮助LDA模型检测的方法自动进化,但计算要求很大。至于LCTA模型提出的阴,曹,顾20.)使不同的主题分布在不同的社区,使模型合理,该方法具有精度高的结果,但是社区的数量需要预设和一些隐藏的参数需要设置与经验。
在本文中,我们提出一个新颖的社区检测算法的目标节点划分成集群。社区检测到该算法的主要特征是同一团体的成员有共同或相似的利益。我们考虑文本的主题和关键字信息从个人的单词通过LDA模型,然后量化语义节点,并将它们映射到语义空间。然后,我们得到理想的虚拟社会在使用粒子群优化算法。最后但并非最不重要,我们构建一个新型模块化模型和使用新功能评估我们的虚拟社会。
与其他模型相比,在语义上的社交网络,如lovain方法模式21和随机块模型22),LDA模型提供了概率统计方法,促进数学的基础。然后考虑抽样后,吉布斯抽样可以给一个精确的和强大的数学证明LDA模型的收敛性和解决方案,这是不可能发生的其他语义模型。结合PSO算法、概率函数编制的LDA模型可以密切结合粒子的惯性权重和收缩因子(23]。在衡量工作表现的方法,我们提出一个新的模块检测评价模型基于语义信息使用余弦函数,这丰富了经典的语义检测评价模型。
剩下的纸是组织如下:部分2介绍了LDA模型在语义网络。部分3显示了吉布斯抽样和该算法。为了验证我们的方法,我们进行了广泛的实验一个真实数据集。绩效评估和实验结果和讨论部分所示4和5。最后,在节6我们做出结论和进一步工作的设想。
2。预赛
2.1。社区检测过程
社区检测问题属于np困难地区(24)开始时需要初始化解决方案和优化解决方案不断的得到最满意的解决方案。语义社区检测的主要目的是形成社区,个人分享共同利益,可能他们有相似的特点25]。所以我们展示一个新奇的想法,关注个人的文本数据。根据社区检测的复杂性,我们利用概率图形model-LDA设计网络。这个模型有一个最明显的层次结构(26,参数空间的规模与培训文档的数量没有关系。
首先,我们从个人的选择主题和词汇语义信息通过LDA模型。然后,我们语义节点映射到语义空间通过吉布斯抽样方法(27]。最后,为了得到更精确的社区,我们使用粒子群优化(PSO)算法,形成语义社区。提出社区检测算法显然是解释以下步骤。
2.1.1。相似的语义信息发现
每个人说不同的单词,每个节点都有自己的社交网络信息内容语义(28]。所以我们上下文语义抽象为主题,然后我们从主题中提取关键字。通过语义信息,我们传达一些分布约束我们的混乱上下文(29日]。这样,在语义划分社区社会网络基于类似文档,主题,从社会语义内容和关键词让社区真正的(30.]。LDA概率模型图所示1。
在本节中,我们研究LDA模型信息的内容。相关的数学符号说明LDA模型给出了表1。LDA模型假定为每个节点生成过程如下:
。的参数 ,属于主题分布,受狄利克雷分布先验参数 。
。的参数 ,这是关键词分布,受狄利克雷分布先验参数 。
。这个话题受多项分布的主题分布概率 。
。关键字受多项分布的关键字分布概率在主题 。
的过程中形成了LDA模型所示算法1。和在这个过程中意味着文档的数量。
|
||||||||||||||||||
3所示。吉布斯采样和PSO的策略
3.1。吉布斯抽样
吉布斯抽样(31日)是一个简单的马尔可夫链蒙特卡罗(密度)32),旨在提取一组近似马尔可夫链样本,目标是使一个合适的概率分布收敛于最优解在高维模型(33LDA等)。根据马尔可夫链的特点,概率分布函数成为吉布斯抽样的关键(34]。至于LDA在这篇文章中,我们只样本主题语义社交网络;也就是说,我们只需要考虑隐藏的品种 。我们表示(主题设置除了 )和(除了组关键词 )画一个后验概率 。至于 ,我们可以找到相应的关键字 。这样的概率可以被描述为在以下方程。 当 和 (的一个关键词吗 ; ,这对应于 ,是其中一个主题 ),的概率 只包括共轭分布 文档和 主题下Dirichlet-multinomial模型。
我们做的数量 主题 文档,可以描述为多项分布 的数量 关键词 主题,命名为 ,多项分布下可以显示如下。 的后验分布和可以得到以下方程。 主题和数量吗关键词的数量。
概率分布 可以计算(6)(11)。 是主题的数量 , 的话题,关键词的数量而吗 ,和关键词的数量。
3.2。PSO类依赖LDA (PSO-LDA)
粒子群优化(PSO)是一种智能优化算法。它第一次被提出的J。肯尼迪和直Eberhart [35]。PSO算法简单的优点,而快速收敛(36速度和更少的控制参数,等等。
与其它优化算法相比,遗传算法(GA)等蚁群优化(ACO)和模拟退火(SA), PSO算法有两个吸引人的特点:首先,PSO优化解决方案首先从局部最优,跑得快,这使得算法更适应网络的发展;其次,粒子在算法中节点可以被映射到语义网络;在算法找到最优解的过程是一致的出生过程语义社区。
算法将一组随机的解决方案在系统启动时间和使用迭代搜索来找出最优解37]。在算法中,每个优化问题的解被称为“粒子”。每个粒子拥有健身本身的价值。所以我们设计一种启发式的方法来检测基于PSO的社区。每个粒子搜索最优解的社会个体之间的信息共享。
在PSO-LDA,一些投入PSO LDA的语义特征。我们使用语义社交网络中节点映射到“粒子”算法和利用每个节点的语义信息向量映射到每个粒子在PSO的速度。至于健身价值,我们使用信息类似的功能。在算法中,我们正常的节点的语义社交网络模拟“鸟群”的行为,社会的共享信息,个人的收益从所有其他节点的发现和以前的经验中寻找食物(38]。因此,每个节点,称为粒子,在语义社交网络被称为群,被认为“飞”在搜索的地方寻找有前途的地区。
首先,我们假设搜索位置 空间;和 粒子群来标示的位置 ,向量 。每个粒子都有两块信息的过程:“最好”的地位与最小值(即。,其个人最佳位置) 全球最好的函数值的粒子群(即。,全球所有粒子的最佳位置) 。在每一次迭代, 粒子群更新它的位置和速度 根据以下方程: 当前迭代, , , 代表人口的规模,是搜索的维数的地方,是惯性权重,和是两个积极的常量。和研究因素,即两个随机数范围提取为每个维度。
在搜索的地方,一旦速度更新, 粒子的位置改变是在以下方程。 收缩因子,管理和调节速度的大小在勘探和开发之间保持平衡和它可以计算如下: , 。收缩因子对该算法的影响;我们在第4部分中讨论这个问题。算法的伪代码描述的算法2(39]。
|
||||||||||||||||||||||||||||||||||||
4所示。性能测量
一般来说,语义社交网络的性能指标主要是基于拓扑结构。和沈等提出的模型。40)广泛用于评估重叠社区,这是描述以下方程: 节点的程度吗和节点的程度吗 , 网络的总程度,是网络的邻接矩阵的元素,是社区的节点的数量吗属于,是社区的节点的数量吗属于,是 社区网络中。我们使用这两种拓扑结构和语义上下文来检测社区,一种新的评价模型命名 ,我们添加信息相似性拓扑评价指标,是由以下方程。 是 节点和是 节点,节点的社区数量吗有关,节点的社区数量吗有关, 网络的总程度,是网络的邻接矩阵的元素,和值的范围是 。至于相似的信息 ,我们给一个正常的社交图 ,在哪里是一组在网络和节点 是 节点;是边链接图节点的集合。实际点的 是衡量结构相关的节点和添加语义相关组件在同一时间。这是更适合语义社区的基本特征。每个节点连接了一个信息向量 ; 两个邻居节点的信息相似吗和这是计算的 社交网络的维数。在我们的方法中,如果两个节点的语义成分接近,这两个节点的投影角度在二维空间相对较小。相反,投影向量是相互矛盾的情况。
5。实验结果
在本部分中,我们将提出并讨论了实验课题数量分析,评价标准,真实的数据集,和不同的社区发现算法,基于三个数据集(美国大学橄榄球网络数据集,克雷布斯polbooks网络数据集,和海豚网络数据集)。
5.1。分析主题数
主题的数量 ,这是PSO-LDA模型中的输入参数之一,会影响社区的紧密度。所以我们选择以下三个数据集验证主题的影响的结果:美国大学橄榄球网络如图2。这个网络,由纽曼,是一个复杂的社会网络对美国大学足球联赛。节点被视为足球队和一个边,两个邻居节点之间,代表两个足球队发挥了比赛。它包含115个节点和616个边缘。克雷布斯polbooks网络建立了V。克雷布斯图所示3。节点代表政治书籍在亚马逊上出售。一般来说,政治倾向的书籍大约分为三个类。所以为了得到主题分布,纽曼收集3步之遥的政治倾向在每个节点。海豚网络收集的纽曼如图4。海豚网络由两个家庭,其中包括62个节点和159边缘。我们模拟每个节点的语义信息来适应狄利克雷分布。
在本节中,我们使用主题数量做实验在三个数据集(足球、polbooks和海豚)。图5显示的比较和三个数据集 。而主题数量在扩大规模、主题分布上升高,发现社区的数量变大上涨。在图5数量变大,当话题在某种程度上,主题分布趋于稳定,导致社区的增量。的比较和 ,这两个测量模型往往会降低性能数量增加,因为话题到达一个最佳点。的最优值6在图5。
为了让社区更直观、形象6显示了社区发现的三个数据集时6、12和18。
(一)
(b)
(c)
5.2。比较在不同的优化算法
在本节中,我们做的比较不同的优化算法有三个以上网络数据集(海豚、polbooks和足球)。我们比较的社区,社区的大小,运行时,浓度和语义与PSO算法,遗传算法(GA),蚁群优化(ACO)和模拟退火(SA)。结果如图7。从图7粒子群优化算法,我们可以看到更多的社区和社区规模较小。PSO算法的运行时,它运行一个小比算法和SA。语义浓度( )(41)是一个函数的测量和测试的凝固程度和在特定的话题所示如下方程: 社区联系的性能指标,而 且仅当和属于同一个社区,有一个之间的联系和 。相比之下,相似度函数 , 使集中在当地环境中稳定的社会群体。但需要注意的是,高并不意味着更高的在社区和更高的并不意味着我们可以得到最好的部门;这是因为社区的重叠部分可以影响语义凝聚力。所以理想的社区建设应该是合适的和 ,这也符合整体优化和局部优化的性能指标。与遗传算法相比,算法和SA在图7的社区发现算法有一个小体积小,更多的社区数字,这是按照主题分布。对于运行时,比ACO算法运行有点慢但比GA和SA。图8显示了四个优化算法运行在海豚网络,像图类似7,算法比其它算法社区检测。
(一)算法
(b)遗传算法
(c)算法
(d) SA
5.3。收缩因子上的比较和
在本节中,我们比较和在三个数据集。跑图,和运行在三个数据集,如图9。从(16),我们把类似的功能的信息 成和 。所以一般的倾向图可以高于 。的最大价值在足球数据集是0.4233 (= 0.52)和是0.4064 (= 0.53);当和存在偏见= 0.53,的价值0.4112(不是最大的一个)。也有偏见polbooks数据集,数据集和海豚和最大的价值是0.4154 (= 0.54)和是0.3982 (= 0.55)在polbooks数据集的最大价值是0.4639 (= 0.60)和是0.4489 (在海豚数据集= 0.62)。
5.4。社区检测算法进行了比较
考虑到语义社区检测的偏见,我们利用古典nonsemantic算法照亮足球数据集的问题,例如。
我们选择GN, FN、线性调频、干椰子肉nonsemantic经典算法、线性调频和干椰子肉重叠社区发现算法。的和都包含在表上方的算法2和社区的检测图所示10与足球数据集。
(一)GN
(b) FN
(c)线性调频
(d)干椰子肉
从结果表2,nonsemantic经典算法的工作高于PSO-LDA(0.5132),但是作品低于PSO-LDA (0.4258)。这表明nonsemantic经典算法做一个更高在拓扑结构检测和较低在语义检测。有一个偏见社区检测nonsemantic经典算法相比,语义算法的理想社区。一方面,我们验证这些算法的性能;另一方面,我们使用这个实验来验证上述关系 , ,和 。至于在表2PSO-LDA性能更好和高 ,和PSO-LDA高于其他算法 。这意味着PSO-LDA表现良好在总体搜索(和 )和工作比别人在本地搜索( )。
5.5。比较真实的数据集
在本节中,我们比较实际不同的数据集,包括量化链接Semantics-Publication (QLSP)数据集(805节点),学术社交网络(ASN)数据集(2500年提取节点)(https://www.aminer.cn/aminernetwork),提取10000个节点和20000个节点从DBLP(2014年12月31日)数据集节点(2839219)(http://dblp.uni-trier.de/db/)DBLP (A)和DBLP (B)和安然(Enron)的电子邮件网络(安然)数据集(25000年提取节点)(http://snap.stanford.edu/data/email-Enron.html)。的 , ,和(检测到社区的数量)的数据集被各种算法在表上方3,随着PSO-LDA 。的柱状图如图11和在图12。从数据11和12,PSO-LDA模型更适合解决语义比古典nonsemantic社区检测算法。
6。结论
在本文中,我们提出了一种新颖的社区检测算法PSO-LDA结合语义信息的拓扑结构。它可以避免社区的数量和大小。吉布斯抽样解决隐藏参数在提出的模型中,抽样结果方法的现实状态。本研究的主要贡献主要关注如何使用不同的相似性度量来衡量基于拓扑结构节点之间的相似性和语义信息。对于未来的工作,我们将应用模型在某些领域隐私保护和蠕虫等容器在语义的社交网络。
数据可用性
使用的数据来支持本研究的发现可以从相应的作者。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作是由中国国家自然科学基金(61402126)、中国黑龙江省自然科学基金(F2016024),黑龙江省博士后科学基金会(LBH-Z15095),大学护理程序为年轻学者与黑龙江省创新型人才(unpysct - 2017094),黑龙江省返回学者基金会(LC2018030)和国家培训项目的创新和创业的大学生(201810214020)。本文还得到中国自然科学基金的支持。