社会网络中基于信任链的主题群组发现算法

　　摘要：针对社会网络中用户群组准确发现难题，提出了一种基于信任链的用户主题群组发现方法。该方法包括3个部分：主题空间发现、群组核心用户发现和主题群组发现。首先，给出了社会网络主题群组的相关形式化定义；然后，通过主题相关度计算发现主题空间，并给出主题空间上用户兴趣度计算方法；其次，提出原子、串联和并联信任链计算模型，并给出主题空间上的信任链计算方法；最后，分别给出主题空间发现算法、核心用户发现算法和主题群组发现算法。实验结果表明，提出的用户群组发现算法相比基于兴趣度的群组发现算法和边紧密度群组发现算法，平均准确率提升4.1%和11.3%此处表达不恰当，与两种算法比较，应该有两个值，而不是写一个平均值，请依据图3（c），补充这两个值。，能够有效提升用户群组组织的准确度，在社会网络用户分类识别方面具有较好的应用价值。 

　　关键词：社会网络；主题群组；主题空间；兴趣度；信任链模型 

　　中图分类号： TP391； TP393.08 

　　文献标志码：A 

　　0 引言 

　　近年来，社会网络（Social Network Site， SNS）已经发展成为人们日常交流共享信息的重要平台[1]。SNS中，裂变式信息分享传播模式促使用户更加快速地聚集在共同关心的主题周围，形成全新的社区组织[2]；即用户群组本质上来说，群组模式的出发点是基于某种紧密关系将不同用户组合在一个社区中，用户可以通过群组模式追求个人喜好的话题信息，也可以关注与自己有关的信息或是自己信任的人所发送的信息[3]。目前，许多学者主要通过主题检测技术进行主题聚类，形成信息传播的网络模型[4]。同时，还有诸多针对社会网络社区发现的算法[5]，如基于图论边紧密度、信息论和社区拓扑结构的社区发现算法[2，6-8]等。 

　　然而，SNS信息传播还包含人际关系的作用[9]。众多学者提出了在社会网络中人与人之间关系在信息传播中的关键影响[10]，用户关系是准确组织群组的关键之一。本文认为，主题群组中用户首先对该主题具有相当的兴趣度，同时也凝聚用户之间的信任关系。 

　　近年来，信任被引入并广泛应用于网络相关研究中[11]。本文提出利用信任链为基础进行主题群组发现的方法。目前，针对SNS的信任计算方法主要集中在基于用户过往交互/评论等，以及基于节点交易等信任度计算方法[12-14]。但是这些方法对于社会网络中用户之间的链式信任关系，以及组成链式信任的复杂路径拓扑组成关注较少。 

　　与传统社区发现研究相比，本文提出了一种基于信任链的主题群组发现算法，该方法具有如下特点：1）确定的主题，即准确找到社会网络中用户关心的主题才能围绕其发现群组；2）核心用户，即对该主题具有较高兴趣度，以此作为群组用户发现的起点；3）以核心用户为起点，根据其社会网络关系的紧密度发现在此主题上对核心用户认可、信任或拥护的用户，作为该群组除核心用户之外的扩展用户。 

　　1 社会网络主题群组模型 

　　社会网络主题群组由核心主题、用户集合及用户之间的关系组成。本文对主题群组进行形式化模型的定义如下。 

　　定义1 社会网络图模型。社会网络可表示为SN=〈V，R〉。其中：非空集合V={v1，v2，…}表示用户集合；R={r1，r2，…}表示用户所形成的信任关系。 

　　基于社会网络图模型，可以明确定义其上的信任链模型： 

　　定义2 信任链模型。SNS中的信任链是由社会网络用户之间的信任关系所形成的信任传递链状模型，表示为四元组Ω=（N，F，C，W），其中：NV是用户非空有限集，分为vS表示起始用户，vI表示中间用户，vE表示目标用户；FN×N，是连接节点的原子信任链有限集合；C（F×…×F）∪（F‖…‖F），是由原子信任链组成的组合信任链，符号×表示串联信任链，符号‖表示并联；W：F→[0，1]∪C→[0，1]指信任链在某主题上的信任值。 

　　信任链上的信任值有以下性质。 

　　5.2 用户兴趣度计算有效性验证 

　　本实验首先对兴趣度时间衰减方法有效性进行验证。实验通过随机方法选择100名用户进行兴趣度计算分析。分别对比了不含时间衰减（Non-Time Attenuation， NTA）方法和带时间衰减（Time Attenuation， TA）计算方法是否能够反映用户的兴趣准确率。实验中，最优兴趣准确率通过人工计算设定，衰减系数分别设定为0.6和0.8。图2（a）中可以看到，时间衰减计算方法（TA）效果明显优于未带时间衰减方法。 

　　其次，通过随机方法选择1000名用户进行兴趣度计算分析。实验共设置3组：Group 1采用基于主题浏览时间的兴趣度计算方法，依据用户对主题微博的浏览时间判断其兴趣度；Group 2采用用户实际选择兴趣度计算，即用户可选择范围内其选择概率较高的就是其兴趣所在；Group 3采用本文所给出的兴趣度计算方法。实验中，分别选定50组不同的主题空间进行测试。图2（b）和（c）中分别可以看到在进行1000次计算后，用户在主题空间中各子主题平均兴趣度计算准确率全文中，“准确度”、“准确率”是否应该统一，是否应该为准确率？请结合图形与正文表述再进行明确。和主题空间总体兴趣度准确性。 

　　5.3 主题群组发现有效性验证 

　　首先，对本文所提出的主题群组发现算法（TGD）中的路径深度d和阈值ξ的设定进行分析。实验在数据集的基础上进行用户主题群组发现，对不同的路径深度和阈值进行测试，记录在不同值设定情况下的主题群组准确率，最优群组为预先设定。图3（a）中记录了不同路径深度情况下的准确率（ξ=1.2），当路径深度超过6之后，准确率已达到最高值，信任链上深度超过6的大多数用户均已经被评估或无法达到阈值。图3（b）中，显示了阈值ξ在不同取值情况下的算法准确率（d=6）。从图3（b）中可以看出，当ξ阈值过小时，将会导致与主题无关用户被错误识别为群组用户；而当阈值过大时，用户将会因无法达到阈值而被错误排除出群组中。因此，按照测试的结果，阈值取值为1.2到1.4之间较合适。

　　接着，对主题用户群组发现算法性能进行分析。实验在数据集中进行主题群组的发现，对比记录主题群组发现的准确率。作为对比，设置了3组实验：基于兴趣度发现方法（Interests based user Group Discovering method， IGD）、边紧密度方法（Edge based user Group Discovering method， EGD）和本文方法（TGD）。图3（c）显示了在数据集上不同领域分类下的主题群组发现平均有效性。从图3（c）中可以看出，本文提出的方法在体育、娱乐、财经等大多数领域准确率明显高于其他方法。而在社会主题的分组中，与IGD相似。本文分析，其原因在于本文数据集中社会方面分组时用户的信任链变化较大，在不同主题之间信任情况不同。因此，导致分组时错误率略有上升。