基于相对关系亲密度的局部社团划分算法研究.docx

基于相对关系亲密度的局部社团划分算法研究
摘要：
社团划分是网络社会学领域研究的重要内容，本文介绍基于相对关系亲密度的局部社团划分算法。相对关系亲密度将节点之间的关系进行衡量和排名，并结合节点自身的重要性，来计算局部社团的划分，以实现网络社团的自动发现和社交网络用户的推荐。
关键词：社团划分，相对关系亲密度，局部社团，社交网络，用户推荐
Abstract:
Communitydetectionisanimportantresearchtopicinthefieldofnetworksociology.Thispaperpresentsalocalcommunitydetectionalgorithmbasedonrelativerelationshipintimacy.Relativerelationshipintimacymeasuresandrankstherelationshipbetweennodes,andcombineswiththeimportanceofnodestocalculatethepartitionoflocalcommunities,inordertoachieveautomaticdiscoveryofnetworkcommunitiesandrecommendationofsocialnetworkusers.
Keywords:Communitydetection,relativerelationshipintimacy,localcommunity,socialnetwork,userrecommendation
一、前言
随着社交网络的兴起与普及，人们越来越关注社交网络中的社团划分问题。社团划分是指将社交网络中的节点按照相似性或相互依赖程度分组，形成一些互相联系紧密的社团，并以此来研究社交网络的结构、内部联系与互动情况。社交网络具有复杂性、动态性和大规模性等特点，对社团划分算法的精度、效率和可扩展性提出了更高的要求。
本文提出的基于相对关系亲密度的局部社团划分算法，从社交网络的局部出发，结合网络中节点之间的相对关系亲密度和节点自身重要性，利用贪心算法实现社团划分。相对关系亲密度所指的是相对节点间关系数量而言的关系亲密程度，即两个节点的亲密程度是相对于网络中其他节点而言的。
二、相关研究
社交网络中常用的社团划分算法有Girvan-Newman算法、Louvain算法、SpectralClustering算法等。Girvan-Newman算法是一种自下而上的分层聚类算法，其依据的是网络中边的数量，通过不断地移除边来实现社团划分。Louvain算法则是一种基于模块度的贪心算法，先通过聚集节点和目标社团来决定社团数量，再对节点进行重分配，计算模块度的提升，直到模块度达到最大值。SpectralClustering算法则是利用图的特征向量进行聚类的一种算法，该算法首先将图转化为一个带权矩阵，在进行特征分解后，选择最小的k个特征向量从而进行聚类。
这些算法均具有一定的局限性，如Girvan-Newman算法要求网络中边数量丰富，Louvain算法难以解决局部社团问题，SpectralClustering算法计算复杂度较高等。
基于相对关系亲密度的局部社团划分算法，是一种结合了节点之间相对关系程度和自身重要性的局部社团划分算法。该算法具有精度高、可解释性强、计算复杂度低等特点，可以更好地解决社交网络中的社团划分问题。
三、算法设计
1.算法流程
①：计算相对关系亲密度。统计节点之间的关系数量，计算相对关系亲密度；
②：确定局部社团中心节点。选择相对关系亲密度最高的节点作为中心节点；
③：划分局部社团。在中心节点的邻居节点中选择相对关系亲密度高的节点加入社团，直到满足划分条件为止；
④：扩展局部社团。根据节点自身的重要性和相对关系亲密度，选择适合的节点加入局部社团；
⑤：重复步骤③和步骤④，直到遍历所有节点为止。
2.算法示例
假设有一个由7个节点组成的社交网络，其节点之间的关系如下图所示：
图1.社交网络节点关系图
为了便于描述，我们以节点A为初始的局部社团中心节点。首先计算节点之间的相对关系亲密度，如下表所示：
表1.节点相对关系亲密度
根据表1，我们可以看出节点B、C和E与节点A的关系最为亲密，其中相对关系亲密度最高的是节点C。
因此，我们以节点C作为局部社团中心节点，并在其邻居节点B、E中选择相对关系亲密度高的节点E加入局部社团，得到如下图所示的局部社团：
图2.局部社团示例
随后，根据节点自身的重要性和相对关系亲密度，选择适合加入社团的节点。接下来在此基础上重复步骤③和步骤④，直到遍历所有节点为止。
四、实验结果
基于无尺度网络生成模型、Dolphin社交网络数据集以及Enron邮件通信网络数