微博社交网络中用户群体关系挖掘与群体行为分析

黄涵霞+胡燕萍+孙知信

Community Relationship Mining and Behavior Analysis for a Microblog

中图分类号：TP391 文献标志码：A 文章编号：1009-6868 （2014） 01-0011-003

摘要：提出了一种基于权重属性的图聚类方式。该图聚类方式在图聚类的基础上，考虑了每个节点的不同属性，并根据影响度给属性分配权重，从而在依据亲密度构建的网络拓扑图上进行图聚类的修正。实验证明，该方法更符合实际的群体聚合方式。

关键词： 社群挖掘；图聚类；相似度计算

Abstract： This paper proposes a graph-clustering algorithm based on attribute information. The attributes （and their weights） of each node are considered in this model when modifying the network topology based on intimacy. Experiments show that the modified algorithm is closer to the actual group polymerization.

Key words： community detection； graph clustering； similarity calculation

社交网络发展势头强劲，微博更是一个强大的社交平台。名人们纷纷开启了认证微博，相互关注顿时拉近了陌生人在网络空间中的距离。随着智能终端性能的突破性革新，社交平台向着移动互联网络进军。中国互联网络信息中心（CNNIC）发布的第32次《中国互联网络发展状况统计报告》中显示2013年具有微博的网民数已达33 077万人，社交网站的网民数已达28 880万人。对比使用率与增长率，微博的发展势头超过了传统的社交网站。与往年数据对比发现，传统社交网站的用户大批量转战到微博，这主要是因为微博用户只需要即时即地的输入简短的文字信息或者上传图片就可以公开发布状态，支持原创，更快速更便捷地反映微博用户的情感等各方面资讯，关注、@等功能增强了微博用户之间的互动。

从网络营销角度看，微博不仅成为用户社交生活的网络工具，也成为传统网络与移动互联网的营销基地，在普通微博用户的博文被感知程度低的情况下，以营销为目的的博文却在潜移默化地培养着客户群，然而这样的客户群是可以依靠群体挖掘技术实现的。因此，需要自适应隐式或显示的在海量微博用户中组件群组。基于微博的信息挖掘是实现微博资源多重利用的技术手段，本文主要依据六度空间理论，研究传统社交网络中群组机制在微博社交网络中的移植性，研究群体关系的挖掘方案与行为，在依靠用户兴趣模聚类获取到的网络拓扑结构后依靠节点的属性矩阵进行初始拓扑结构的重分割。

1 微博社交网络相关工作

社交网络不同于普通的静态网络，社交网络中的网络结构随着时间变化而不断发生变化，一定程度上反映真实世界的状况。微博社交的即时即地性能够更好地反映网络与现实世界的关联。社会性网络中普遍存在群体现象，可以把网络结构中连接紧密的节点集命名为群体，类似于“好友圈”的显示群体，群体与群体之间通过关键节点互联被称为稀疏网络，社交性网络中的群体挖掘主要有相似度计算和图聚类两方面的研究热点。

（1）基于相似度的社会群体挖掘

网络在时间维度上的动态性，文献[1]提出的网络相似性度量方法，在基于图形结构的基础上计算用户的概要信息与语义信息，用户的概要信息主要以标签记录为主，通常在用户申请账号时生成静态的文本，这样计算出的相似度与网络拓扑结构缺乏动态性。相似度计算就是计算用户之间的相似情况，依靠计算每两个用户之间的相似度来构建网络拓扑结构，将大型网络社区分割成一个个具有关联性的小型的群体。在文献[2]中提出了一种新的协同过滤的用户相似度计算算法，但没有将其扩展到社交网络。文献[3]用监督式学习方法构建了一个关系相似度模型，利用关系特性与非关系特性以及两个核心用户与其所在的社区信息，实现高度准确的好友推荐。

（2）社交网络的图聚类技术

图挖掘方法是社会性复杂网络分析的重要方法，主要是将网络中的个体分别用节点表示，形成复杂的网络图。节点之间采用直线连接的通常表示节点之间的某种关系，节点之间的距离计算公式直接影响到聚类的结果。欧几里德距离与曼哈坦距离不能直接用在节点距离的计算中，坐标的缺少使得节点间的距离不能直接采用欧几里得距离和曼哈坦距离。实验证明采用k-medoids算法时，相比随即漫步距离算法与最短路径算法，在数据库系统和逻辑编程（DBLP）数据集形成的网络图的子图中最短距离算法的聚类结果更为合理[4]。Kohout与Nerda认为可以通过一个有向图模型将社交网络中的用户分到集群中去，他们分析了几个不同的遗传算子，并提出了一种遗传算法用于直接加权图的聚类[5]。基于熵的聚类方法是获取局部最优簇的随机种子成长的方式，最大限度地减少图熵。基于熵的方法比竞争方法在计算精度和效率上有更好的性能[6]。文献[7]研究了集群图中社群交互的关键作用节点的发现。一个广义马尔可夫图模型被提出并用在在社交网络的分类上。该模型揭示了度分布、聚类系数分布。该拥挤系数分布给出了社会网络特征。

2 微博社交网络中的用户

群体关系挖掘

大多数文献都采用图聚类算法来挖掘紧密联系的群体。文献[8]介绍了一种群体挖掘方法，在图聚类算法的基础上，加入了节点属性的因素，使得群体分类更加精确。但是该文献采用了二进制的方式对节点属性进行描述。所有的属性都采用0和1的方式进行表示。这种方式过于简化了属性的取值范围，并且不具有代表性。endprint

本文在此基础上，提出了基于亲密度的网络拓扑结构图，并对节点属性的取值进行了改进。采用对微博的博文分词的方式，提取其中的关键字，并对关键字进行归类，关键字分属于不同的属性。对同一种属性的关键字出现的次数进行统计，看该属性占总值的比例，来作为节点属性的具体数值。同时，考虑到群体聚类的不同目的，本文还对属性的权值进行了设置，根据群体划分目的的不同，来分配属性权重的大小，从而达到更好划分群体的目的。

2.1 问题描述

微博社交网络中用户采用相互关注、评论博文、转发与@好友等形式形成节点之间的关联，本文主要在由亲密度构建的网络拓扑图上进行图聚类的修正。

在群体挖掘中，挖掘目的直接影响着网络群体的组合，亲密度的计算可以将具有现实关系的博友聚集起来，形成拓扑结构。用有向带权图G（V，E，X）来表示微博网络中用户关系。V表示微博网络中的节点集合；E表示用户节点的有向边，即用户之间的亲密行为；X为有向边的权值，值小就代表不怎么亲密，很少有亲密举动。考虑到亲密需要双方互动，故采用节点间双向的权值的较小值E（X，Y）=min（W（X，Y），W（Y，X））表示亲密度。依据亲密程度可以构建起类似于图1的网络拓扑结构。

由上述方案获得的网络拓扑结构还不具有较强的群体特性，需要进一步计算才能获得社交网络中的群体结构图。根据网络拓扑图，修改拓扑图的表示方法，将节点属性值作为参数重新描述拓扑图：G（V，E，X），其中V={V1，V2，V3…Vn}是节点集合，n=|V|代表图中的节点数量。E?V×V是边的集合。E={（Vi，Vj）}：Vi，Vj∈V}，并且X∈R|V|×d是一个顶点属性矩阵。图1显示了的是一个基于亲密度组成的社会性网络，每个节点代表一个用户，用户存在若干属性，假设存在n个属性值（T1，T2…Tn），下文将建立属性矩阵，利用相似度函数计算出节点的相似矩阵，进而对图1进行修正。

2.2 节点集的属性矩阵

本文以一个12个顶点的简单拓扑网络为例，研究基于属性举证重构的拓扑网络，为其寻找新的边界。图2中的拓扑结构中有3个小型群体，可以看出这3个小群体存在一个闭环关系。

由于每个属性的重要程度不同，为属性集（T1，T2…Tn）分别分配权值P1，P2…Pn，Pi的取值采用机器学习的方式，根据不同的聚类和挖掘目的，根据属性的重要程度动态地为属性分配权值，P1，P2…Pn需满足条件P1+P2…Pn=1。

对微博的博文采用分词的方法，提取其中的关键字，对关键字进行归类，分属于不同的属性，对同一种属性的关键字出现的次数进行统计，设为k，所有关键字出现的总次数设为P，那么每个节点该属性的属性值a_ij=k/P。节点集属性矩阵如图3所示。矩阵给出了拓扑结构中每个节点的属性。

上述矩阵给出了节点的属性值，y1表示单纯的属性矩阵，y2依据属性在割边中的关键程度加入了权值计算，期中假设属性权重向量为[T→]（1/2，1/4，1/4），接下来就可以依据加权的属性矩阵求节点的相似度。

2.3 基于相似度的拓扑图修正

根据属性矩阵y2采用类余弦相似性计算公式：

可以计算得到每两个节点的相似性值，从而得到节点集的相似度矩阵，如图4所示。

根据矩阵图可以发现节点集（V1，V2，V3，V4，V5，V6）存在属性高度相关性，但是该节点集中的节点分布在A、B两个集合内，在节点集C中，很明显节点集（V7，V8，V10）属性一样，但与节点集（V9，V11，V12）中节点的余弦相似度在0.53左右，为了寻找高度相似的节点集，采用阀值为0.95对图2中的网络拓扑图进行修正，得到原拓扑图的重构，如图5所示。图5中虚线表示节点间属性向量的余弦相似值极高，从而具有相似性，根据虚线的密集程度，对原始的拓扑结构进行了群体的进一步修正，一个蓝色区域表示一个亲密度基础上，属性值极似的群体。

基于网络亲密度所构造的网络拓扑图根据用户与用户之间的亲密关系划分出来的群体，但是通过这样的方式聚合出来的群体未必真正有内在的联系。为此，本文采用加入每个单个节点的内在属性的方式，这里的属性可以是每个用户的兴趣爱好，又或者是用户的需求等因素，根据不同的挖掘目的和要求，动态地给这些属性分配权重，来挖掘群体的内在关联。通过加入属性并对它们分配权重的方式，把看似有联系的群体分割成了两个不同的群体，而看似没有联系的群体聚合在了一起。

3 结束语

本文提出了一种基于节点属性的图聚类算法，原有的网络拓扑图是基于微博用户的网络亲密度进行挖掘的，本文提出的算法对原有的网络拓扑图进行了修正，加入了节点属性的概念，并根据不同的挖掘目的，为属性分配不同的权值，用来表示不同属性的重要程度。数据表明这种修正算法更符合实际的社群聚类方式。

参考文献

[1] AKCORA C G， CARMINATI B， FERRARI E. Network and profile based measures for user similarities on social networks [C]//Proceedings of the Information Reuse and Integration， 2011 IEEE International Conference on， 3-5 Aug. 2011. Las Vegas， 2011： 292-298.

[2] SHEN L， ZHOU Y M. A New User Similarity Measure for Collaborative Filtering Algorithm. [C]//Proceedings of the Computer Modeling and Simulation， 2010. Second International Conference on， 22-24 Jan. 2010， Sanya， Hainan， 2010： 375-379. doi： 10.1109/ICCMS.2010.67.endprint

[3] MOHAJIREEN M， ELLEPOLA C， PERERA M， et al. Relational similarity model for suggesting friends in online social networks [C]//Proceedings of the Industrial and Information Systems （ICIIS）， 2011 6th IEEE International Conference on. 16-19 Aug. 2011， Kandy， 2011：334-339. doi： 10.1109/ICIINFS.2011.6038090.

[4] 温菊屏， 钟勇. 图聚类的算法及其在社会关系网络中的应用 [J].计算机应用与软件， 2012，25（2）：161-163.

[5] KOHOUT J， NERUDA R. Two-Phase Genetic Algorithm for Social Network Graphs Clustering [C]//Proceedings of the Advanced Information Networking and Applications Workshops （WAINA）， 2013 27th International Conference on， 25-28 March 2013， Barcelona， 2013：197-202.

[6] KENLEY E C， CHO Y R. Entropy-Based Graph Clustering： Application to Biological and Social Networks [C]//Proceedings of the Data Mining （ICDM）， 2011 IEEE 11th International Conference on， 11-14 Dec. 2011， Vancouver， BC， 2011：1116-1121. doi： 10.1109/ICDM.2011.64.

[7] CRUZ J D， BOTHOREL C， POULET F. Layout Algorithm for Clustered Graphs to Analyze Community Interactions in Social Networks [C]//Proceedings of the Advances in Social Networks Analysis and Mining （ASONAM）， 2012 IEEE/ACM International Conference on， 2012， Washington， DC， USA. 2012：704-705. doi： 10.1109/ASONAM.2012.120.

[8] SALEM S， BANITAAN S， ALJARAH I， et al. Discovering Communities in Social Networks Using Topology and Attributes [C]//Proceedings of the Machine Learning and Applications and Workshops， 2011 10th International Conference on， 18-21 Dec. 2011， Honolulu， HI， 2011：40-43. doi： 10.1109/ICMLA.2011.57.

作者简介

黄涵霞，南京邮电大学物联网学院物流工程专业在读硕士研究生；主要研究方向为信息网络技术及其在物流中的应用。

胡燕萍，南京邮电大学物联网学院物流工程专业在读硕士研究生；主要研究方向为信息网络技术及其在物流中的应用。

孙知信，南京邮电大学教授、博士生导师；主要研究领域为计算机网络与安全；已主持和参加基金项目10余项；已发表论文50余篇，其中被SCI/EI检索40余篇。endprint

[3] MOHAJIREEN M， ELLEPOLA C， PERERA M， et al. Relational similarity model for suggesting friends in online social networks [C]//Proceedings of the Industrial and Information Systems （ICIIS）， 2011 6th IEEE International Conference on. 16-19 Aug. 2011， Kandy， 2011：334-339. doi： 10.1109/ICIINFS.2011.6038090.

[4] 温菊屏， 钟勇. 图聚类的算法及其在社会关系网络中的应用 [J].计算机应用与软件， 2012，25（2）：161-163.

[5] KOHOUT J， NERUDA R. Two-Phase Genetic Algorithm for Social Network Graphs Clustering [C]//Proceedings of the Advanced Information Networking and Applications Workshops （WAINA）， 2013 27th International Conference on， 25-28 March 2013， Barcelona， 2013：197-202.

[6] KENLEY E C， CHO Y R. Entropy-Based Graph Clustering： Application to Biological and Social Networks [C]//Proceedings of the Data Mining （ICDM）， 2011 IEEE 11th International Conference on， 11-14 Dec. 2011， Vancouver， BC， 2011：1116-1121. doi： 10.1109/ICDM.2011.64.

[7] CRUZ J D， BOTHOREL C， POULET F. Layout Algorithm for Clustered Graphs to Analyze Community Interactions in Social Networks [C]//Proceedings of the Advances in Social Networks Analysis and Mining （ASONAM）， 2012 IEEE/ACM International Conference on， 2012， Washington， DC， USA. 2012：704-705. doi： 10.1109/ASONAM.2012.120.

[8] SALEM S， BANITAAN S， ALJARAH I， et al. Discovering Communities in Social Networks Using Topology and Attributes [C]//Proceedings of the Machine Learning and Applications and Workshops， 2011 10th International Conference on， 18-21 Dec. 2011， Honolulu， HI， 2011：40-43. doi： 10.1109/ICMLA.2011.57.

作者简介

黄涵霞，南京邮电大学物联网学院物流工程专业在读硕士研究生；主要研究方向为信息网络技术及其在物流中的应用。

胡燕萍，南京邮电大学物联网学院物流工程专业在读硕士研究生；主要研究方向为信息网络技术及其在物流中的应用。

孙知信，南京邮电大学教授、博士生导师；主要研究领域为计算机网络与安全；已主持和参加基金项目10余项；已发表论文50余篇，其中被SCI/EI检索40余篇。endprint

[3] MOHAJIREEN M， ELLEPOLA C， PERERA M， et al. Relational similarity model for suggesting friends in online social networks [C]//Proceedings of the Industrial and Information Systems （ICIIS）， 2011 6th IEEE International Conference on. 16-19 Aug. 2011， Kandy， 2011：334-339. doi： 10.1109/ICIINFS.2011.6038090.

[4] 温菊屏， 钟勇. 图聚类的算法及其在社会关系网络中的应用 [J].计算机应用与软件， 2012，25（2）：161-163.

[5] KOHOUT J， NERUDA R. Two-Phase Genetic Algorithm for Social Network Graphs Clustering [C]//Proceedings of the Advanced Information Networking and Applications Workshops （WAINA）， 2013 27th International Conference on， 25-28 March 2013， Barcelona， 2013：197-202.

[6] KENLEY E C， CHO Y R. Entropy-Based Graph Clustering： Application to Biological and Social Networks [C]//Proceedings of the Data Mining （ICDM）， 2011 IEEE 11th International Conference on， 11-14 Dec. 2011， Vancouver， BC， 2011：1116-1121. doi： 10.1109/ICDM.2011.64.

[7] CRUZ J D， BOTHOREL C， POULET F. Layout Algorithm for Clustered Graphs to Analyze Community Interactions in Social Networks [C]//Proceedings of the Advances in Social Networks Analysis and Mining （ASONAM）， 2012 IEEE/ACM International Conference on， 2012， Washington， DC， USA. 2012：704-705. doi： 10.1109/ASONAM.2012.120.

[8] SALEM S， BANITAAN S， ALJARAH I， et al. Discovering Communities in Social Networks Using Topology and Attributes [C]//Proceedings of the Machine Learning and Applications and Workshops， 2011 10th International Conference on， 18-21 Dec. 2011， Honolulu， HI， 2011：40-43. doi： 10.1109/ICMLA.2011.57.

作者简介

黄涵霞，南京邮电大学物联网学院物流工程专业在读硕士研究生；主要研究方向为信息网络技术及其在物流中的应用。

胡燕萍，南京邮电大学物联网学院物流工程专业在读硕士研究生；主要研究方向为信息网络技术及其在物流中的应用。

孙知信，南京邮电大学教授、博士生导师；主要研究领域为计算机网络与安全；已主持和参加基金项目10余项；已发表论文50余篇，其中被SCI/EI检索40余篇。endprint