基于行为模式的社会网络论文范文

本站小编为你精心准备了基于行为模式的社会网络论文参考范文，愿这些范文能点燃您思维的火花，激发您的写作灵感。欢迎深入阅读并收藏。

1基本定义和假设

1．1基本定义

本文所研究的用户是针对于社会网络中的用户，用户之间具有一定的交互行为，用户总数表示为U．定义1．用户A与用户B在状态、日志、照片、相册等方面进行了一次交互操作，如用户A对用户B的状态进行一次评论，即视为用户A与用户B发生一次交互，记为(A，B)．定义2．用户与其它用户的交互行为时间流称为该用户的行为模式．

1．2基本假设

直观分析，社会网络中用户间存在一定交互行为，用户交互时主要依赖于当前的交互，对于以前的交互特性并不敏感，也就是用户间的交互行为满足Markov性，所以我们假设用户交互行为是一个Markov过程．由于用户在长期行为中会形成稳定的行为习惯和偏好，所以用户行为具有相对稳定性，经过较长一段时间后，用户的行为模式将趋于稳定状态，也就是用户交互行为的Markov随机过程可以收敛．用户行为Markov模型能够描述用户内在的特性．采用用户行为Markov模型进行聚类基于如下假设:假设:用户行为具有偏好性，不同用户在行为模式上存在一定差异，用户间行为模式并不完全相同，但若干用户间行为模式会存在一定相似性，这些用户相较于其他用户行为模式相似程度较高，存在一定相关性，相反存在若干用户间相似程度较低．

2基于行为模式的社会网络用户谱聚类算法

本文提出一种基于行为模式的社会网络用户谱聚类算法(SpectralClusteringAlgorithmforUserBehaviorPatterns，SCBP)．SCBP算法主要包含2个阶段，第一阶段建立用户行为Markov模型，学习相应参数;第二阶段对用户行为模型进行谱聚类，获得用户划分结果．

2．1社会网络用户行为模型

SCBP方法使用一阶齐次Markov模型对社会网络用户行为进行建模，将Markov模型的状态与用户间的交互行为相对应．在确定Markov模型的状态时，主要有以下3步:1)获取每个用户交互行为数据．设用户ui的交互行为数据为B=(d1，d2，…，db)，它是对用户ui与其它用户的历史交互行为进行预处理后得到交互行为流，其长度为b，其中di表示按时间顺序产生的第i个与用户ui发生交互行为的用户．2)提取交互行为数据流B中互不相同的用户，设B中互不相同的用户有N个(N≤b)，分别记为^d1，^d2，…，^dN，并计算这些用户在B中出现的频率．设第i个用户^d2在B中的出现频率。3)给定频率阈值η，对于^d1，^d2，…，^db中出现频率大于或等于频率阈值η的用户形成Markov模型的状态．设在B中出现频率大于或等于频率阈值η的用户共有S个．

2．1．1学习一步转移矩阵在学习一步转移矩阵时，采用极大似然估计法学习相关参数．首先，依据用户行为Markov模型的状态将交互行为序列中所有的交互行为对应为相应的状态，获得用户的状态序列．其次，依据用户的状态序列学习各个状态间的转移次数及转移概率，从而得到一步转移矩阵．一步转移矩阵的学习算法表1所示．

2．1．2学习收敛后的Markov分布在学习收敛后的Markov分布时，需要获得用户的一步转移矩阵和初始Markov分布．我们采用差值法判断Markov分布是否达到收敛，计算当前Markov分布与之前一次Mark-ov分布的差值，并将所得差值与规定阈值ε进行比较，若所得差值小于或等于规定阈值，说明Markov分布已经达到收敛，此时Markov分布即为收敛后的Markov分布．在初始Markov分布的选择上，可以选择所有状态均为同一概率的初始分布，也可依据已有的先验知识，对不同状态分配不同初始概率，以此作为初始分布．收敛后Markov分布的学习算法如表2所示，通过differentof函数计算当前Markov分布与之前一次Markov分布的差值，并将所得差值与阈值ε比较．

2．1．3学习收敛后的n步转移矩阵在学习收敛后的n步转移矩阵时，需要输入用户的一步转移矩阵和误差阈值ε．为了加快算法执行，采用迭代次数作为算法退出条件．通过不断迭代计算新的n步转移矩阵，直至达到n步转移矩阵稳定或者达到迭代次数，获得收敛后的n步转移矩阵．收敛后n步转移矩阵的学习算法如表3所示，依据一步转移矩阵和当前n步转移矩阵计算新的即下一步n步转移矩阵，然后依据isconvergent函数判断相邻两次n步转移矩阵差值，若所得差值小于阈值ε，则停止迭代．

2．2SCBP聚类算法

通过建立用户行为Markov模型，我们对每个用户的行为模式构建一步转移矩阵、收敛后Markov模型和收敛后n步转移矩阵3种形式化表达，在3种表达基础上，利用谱聚类思想，构建了面向用户行为Markov模型的谱聚类(SCBP)算法．SCBP聚类算法的输入是对象间的相似度矩阵，所以需要定义一步转移矩阵、收敛后Markov分布和收敛后n步转移矩阵对应的相似度矩阵．我们分别采用矩阵L2范数和KL散度定义一步转移矩阵、收敛后n步转移矩阵和收敛后Markov分布基础上的用户行为相似度．根据差值矩阵的L2范数和Markov分布的KL散度，我们定义用户p与用户q的相似度，给定用户p和用户q的一步转移矩阵或者n步转移矩阵，则定义用户p与用户q的转移矩阵相似度为:

3实验与结果分析

3．1实验设计与评价指标

实验数据分别采用人人网(Renren)和Facebook用户的行为数据集，人人网是中国最大、最具影响力的SNS网站．而Facebook为国外知名社交网站，具有庞大的用户数量．人人网数据集包含了435名用户在三年间的活动记录，预处理得到用户间交互行为信息，包含相册交互数据6613条，日志交互数据2921条，照片交互数据130591条，状态交互数据557963条．Facebook数据集为新奥尔良网络数据集1．该数据集包含45813个用户，但其中很多用户的交互行为较少，我们对其中的交互次数大于30的用户进行筛选，选择出2000个用户作为实验数据集．由于SCBP后期采用了KMeans聚类，所以我们采用KNN作为比较方法，KNN是带监督的学习方法，我们从人人网数据中选择行为模式差异较大的50个用户进行标注，分成5类，作为初始学习类别．对于Facebook数据集，则选择行为模式差异较大的50个用户分成5类作为初始分类点．我们设计了2组实验:1)精确聚类结果比较，聚类结果与人工标注结果对比．2)无标注聚类结果比较．将所有用户采用不同聚类方法进行聚类，然后分析各聚类方法结果的合理性．我们采用指标F值和D值对比聚类效果．F值和D值是衡量聚类效果的常见指标．聚类结果评价指标F值和D值的计算方法．1)F-Value(F值)，也称为聚类密集性，F-value的计算方法如下。其中ci是类i的中心，cj是类j的中心，D值代表类与类之间的差异程度，D值越大表示类与类之间的距离值越大，类之间越分离，聚类效果越好．

3．2实验结果与比较

3．2．1精确聚类结果比较本文对50名人人网用户根据行为特征进行人工标注，得到人工聚类结果．然后根据一步转移矩阵(One)、收敛后Markov分布(M)和收敛后n步转移矩阵(n)进行不同度量下聚类，得到SCBP和KNN的聚类结果．通过将各个聚类对象得出的结果与人工标注的分类结果进行对比，计算各个聚类的精度(Precision，P)和召回率(Recall，R)．不同度量、不同方法的精度和召回率如图1所示．从图1上可以看出:1)SCBP聚类的精度和召回率均在0．8以上，相较于KNN，SCBP聚类的精度和召回率明显更高，更加符合依据用户行为划分准则的结果．两种算法在收敛后Markov分布上的差异较大;2)SCBP和KNN使用收敛后的Markov分布聚类的精度和召回率均稍高于使用一步转移矩阵和收敛后n步转移矩阵进行聚类，说明采用收敛后Markov分布进行聚类更有效;3)SCBP聚类算法在三种度量上所得的精度和召回率差异相对较小，且SCBP聚类算法中所得的精度和召回率相比KNN算法中的结果均更高．由此可见SCBP聚类算法能够适应不同的聚类基础，在实际应用中具有较好的适应性．

3．2．2人人网无标注聚类结果比较我们将所有用户采用不同聚类方法进行聚类，聚类结果的D值和F值对比分析结果如下页图2所示．从图上可以看出:1)对比三种聚类度量下的F值和D值可以看出，无论是KNN还是SCBP，使用收敛后Markov分布进行聚类的F值均小于使用一步转移矩阵和收敛后n步转移矩阵聚类的F值，并且使用收敛后Markov分布进行聚类的D值均大于使用一步转移矩阵和收敛后n步转移矩阵聚类的D值．这个结果与50个用户上的聚类结果一致，说明采用收敛后Markov分布进行聚类最合理;2)SCBP聚类中使用收敛后的Markov分布相较于使用一步转移矩阵和收敛后n步转移矩阵聚类的F值下降很大，而D值保持较高值，说明SCBP聚类结果中每个类内部成员更为紧凑，并且类与类之间的差异更大．这个结果与50个用户上的聚类结果也一致，说明SCBP聚类算法能够适应不同的度量;3)对比SCBP聚类和KNN方法的F值和D值，SCBP聚类的F值均小于KNN方法的F值，并且SCBP聚类的D值均大于KNN方法的D值，即SCBP聚类相较于KNN方法，每个类内部成员更为紧凑，并且类与类之间的差异更大．通过对比两种聚类方法的F值和D值，可以明显得出SCBP聚类效果优于KNN方法．

3．2．3Facebook数据集实验结果分析由于Facebook数据集的用户没有个人信息，难以准确判别用户关系，所以没有进行人工分类，直接对其进行聚类．根据人人网数据集上的实验结果，可以知道基于收敛后Markov分布上的聚类结果表现较好，所以我们在收敛后Markov分布上进行SCBP聚类和KNN方法，然后分析结果．SCBP聚类和KNN方法的F值和D值结果如图3所示．从图3可以看出，使用收敛后的Markov分布，SCBP在Facebook数据集上的F值和KNN方法差异较小，SCBP略低于KNN．在表示聚类不同簇间差异性的D值上，SCBP却明显高于KNN．实验结果说明SCBP聚类结果中每个类内部成员紧凑，并且类与类之间的差异程度很高，类之间的区分度大．由于Facebook数据集内的用户间交互存在一定的偶然性，一个聚类簇内的用户在行为上具有一致性，不同簇间的差异性越高，说明能够区分不同行为特征的用户群．相较于KNN方法，SCBP聚类方法不同簇中的用户在行为模式上差别较大，使不同类别的用户得到了较好、较为准确的划分，在一定程度上减少了误分类的情况，提高了用户划分准确度．同时，也说明SCBP方法能够满足社会网络上具有一定噪声和随机性的用户聚类，这对于发现用户兴趣、用户推荐、社区挖掘等具有重要的价值．

4结论与总结

本文提出了基于行为模式的社会网络用户谱聚类方法．本文聚类方法的效果优于传统聚类方法，而收敛后Markov分布的聚类效果优于一步转移矩阵的聚类效果．基于行为的用户聚类可应用于个性化推荐等领域，从而为用户提供更优质的社交服务．在未来工作中，考虑将不同聚类方法和聚类对象整合，进行提升处理．同时，在对用户进行聚类时，尝试融入用户的基本属性信息，以补充用户行为信息中缺失的因素，以保证聚类结果更加准确．

作者：韩忠明张晨李斌莫倩单位：北京工商大学计算机与信息工程学院