软件２０１３年第３４卷第１期 ＳＯＦＴＷＡＲＥ 国际ＩＴ传媒品牌 微博社交网络中面向机构的用户挖掘 张振华，刘瑞芳 （北京邮电大学信息与通信工程学院，北京１００８７６） 摘要：本文提出了一种在微博社交平台中挖掘与目标机构相关用户的方法。待发掘的用户主要包括对目标用户有浓厚兴趣和 处于目标机构相关社交圈子中的用户。本文爬取了测试机构的若干官方账户的两层粉丝的社交网络数据，利用社交网络的拓扑结 构计算用户对目标机构的兴趣度，并在该数据集上进行去噪、压缩处理后，应用社交挖掘算法，划分出网络中的社交圈子，最后 通过定义社区的Ｒ＠Ｎ指标来选取相关社区。实验结果现实，在得到的所有社交圈子中，均仍然存在大量噪声，但每个社区的地理 位置信息等能够体现出较为一致的特点，通过Ｒ＠Ｎ指标能够有效的区分出相关社区。 关键词：社交网络；微博；用户挖掘；机构 中图分类号：ＴＰ３９１．４１ 文献标识码：Ａ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１００３—６９７０．２０１ ３．Ｏ１．０４１ Ｏｒｇａｎｉｚａｔｉｏｎ Ｍｅｍｂｅｒｓ Ｍｉｎｉｎｇ ｏｎ Ｍｉｃｒｏ－Ｂｌｏｇｓ ＺＨＡＮＧ Ｚｈｅｎ・ｈｕａ，ＬＩＵ Ｒｕｉ—ｆａｎｇ （Ｓｃｈｏｏｌ ｏｆｌｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｂｅｉｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＰｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｂｅｉｊｉｎｇ，Ｃｈｉｎａ，１００８７￣ ［Ａｂｓｔｒａｃｔ］Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｎｏｖｅｌ ａｐｐｒｏａｃｈ ｔｏ ｍｉｎｅ ｒｅｌｅｖａｎｔ ｕｓｅｒｓ ｏｆ ｏｒｇａｎｉｚａｔｉｏｎｓ ｉｎ ｍｉｃｒｏ—ｂｌｏｇｓ，ｉｎｃｌｕｄｉｎｇ ｕｓｅｒｓ ｗｈｏ ｅｉｔｈｅｒ ｄｉｓｐｌａｙ ｓｔｒｏｎｇ ｉｎｔｅｒｅｓｔ ｔｏｗａｘｄ ｏｒｇａｎｉｚａｔｉｏｎｓ ｏｒ ｂｅｌｏｎｇ ｔｏ ｒｅｌａｔｅｄ ｃｏｍｍｕｎｉｔｉｅｓ ｏｆ ｔｈｅ ｏｒｇａｎｉｚａｔｉｏｎｓ．Ｉｔ ｃａｌｃｕｌａｔｅｓ ｔｈｅｉｒ ＮＳｃｏｒｅ ｔｏ ｆｉｎｄ ｕｓｅｒｓ ｗｈｏ ｄｉｓｐｌａｙ ｉｎｔｅｒｅｓｔ ｔｏ ｔｈｅ ｏｒｇａｎｉｚａｔｉｏｎ ｂａｓｅｄ ｏｎ ｔｈｅ ｐｒｏｐｅｒｔｙ ｏｆ ｔｈｅ ｓｏｃｉａ１．ｎｅｔｗｏｒｋ．Ａｆｔｅｒ ｅｌｉｍｉｎａｔｉｎｇ ｔｈｅ ｎｏｉｓｅ ａｎｄ ｉｒｒｅｌｅｖａｎｔ ｕｓｅｒｓ ｏｆ ｔｈｅ ｎｅｗｏｒｔｋ ｎｄ ａａｐｐｌｙ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｎ ｈｅｔ ｎｅｔｗｏｒｋ，ｔｈｅ ｍｅｔｈｏｄ ｄｉｓｃｒｉｍｉｎａｔｅｓ ｔｈｅ ｒｅｌｅｖａｎｔ ｃｏｍｍｕｎｉｔｉｅｓ ｂａｓｅｄ ｏｎ ｈｅｉｔｒ Ｒ＠Ｎ ｓｃｏｒｅ ｒｅｓｕｌｔ． ［Ｋｅｙ ｗｏｒｄｓ］Ｓｏｃｉａｌ Ｎｅｗｏｒｔｋ；Ｍｉｃｒｏ－ｂｌｏｇ；Ｕｓｅｒ Ａｎａｌｙｓｉｓ；Ｏｒｇａｎｉｚａｔｉｏｎ ０引言 微博是２１世纪以来新兴的一种基于ＷＥＢ ２．０的信息发布 本文将基于微博的社交网络中面向挖掘某个机构相关的用 户群体，如学校的学生，某时尚品牌的消费者等等。针对该问题， 文章将采用基于社交网络距离和社区发现两种方式来进行挖掘。 本文的创新点也在于通过社交发现和分析用户兴趣度，在微博 社交网络中有针对的挖掘与某一机构相关的用户群体。 和共享平台。自首个微博平台Ｔｗｉｔｔｅｒ ２００６年诞生后４年内， 其用户数量就已达到７５００万 。更有数据显示，中国国内的著 名微博平台，新浪微博，自２００９年８月，也仅用了不到４年的 时间，就已突破了３亿注册用户 。在微博中，用户可以方便的 通过共享见闻、发布评论、位置签到等方式随时发布个人状态， 也能通过关注其他微博用户及时获取各种资讯、八卦和好友动 本文小节１界定与目标机构相关的用户的具体定义；小节 ２介绍实验数据的采集范围和基本情况；小节３介绍用户对目标 机构兴趣度的计算；小节４通过基于社区发现的方法发现与目 态等。由于其独特的功能设计和易用性，微博得以在短时间内 取得重大成功。 微博采用了独特的单向关注模式，用户可以有选择的关注 标机构存在现实联系群体的步骤；小节５总结全文。 １与机构相关的用户 在微博平台中，用户之间通过一条条单向的关注关系相互 他们感兴趣的用户，建立单向的收听关系。此外该平台也吸引 连接，这些连接的拓扑结构反映了这张社交网络中节点的性质。 了大量的社会精英、媒体机构和普通大众等各类人群，形成了 用户在微博社交网络中与目标机构的相关性可以有许多表现形 独特的社区结构。微博中社交关系可以看作是一种现实世界社 式，本文主要关注以下两类用户： 交关系在虚拟世界的扩展。Ｊａｖａ等人 通过研究分析，将微博 用户关注的用户为三类人群：信息源、好友圈子和信息获取者。 第一，对目标机构的兴趣度较高的用户。在微博平台中， 用户的关注和被关注情况都是可以获取到的。用户的关注关系一 般代表着出用户的信息获取倾向，即能体现用户的兴趣。因此在 而由此形成的社交网络由此也就具有了重要的发掘价值。 作者简介：张振华（１９８８一），男，研究生，主要研究方向：网络信息检索、智能信息处理。 通信联系人：刘瑞芳，副教授，主要研究方向：网络信息检索、智能信息处理。 １２１‘ 软件杂志欢迎推荐投稿：ｈｔｔｐ：／／ｗｗｗ．ｃｃｏｍｓｏｆｔ．ｃｏｒｎ／ 软件（您的文章得到院士的关注） 张振华等：微博社交网络中面向机构的用户挖掘 常用的社区发掘算法 有最小切割法 Ｊ、 层次聚类法、Ｇｉｒｖａｎ－Ｎｅｗｍａｎ算法 Ｊ、模度 值最大化算法（ｍｏｄ￣ａｍｙ） 等。最小切割 法试图通过将一个图分成预定数量的大小相仿 的子社区，同时使得社区间的边数最少。该方 法较为简单易行，但具有很大的局限性，仅适 合发掘特定结构的关系图，发掘结果的通用性 较差。层次聚类算法，即通过传统的层次聚类 的方法，将每个节点视作一个社区，并依次合 并最相似的社区，最终形成一个树形结构。 在所有社区发掘算法中，Ｍ．Ｎｅｗｍａｎ提 出的基于模度值最大化的快速社区发现算法是 较为有效的一种算法，该算法提出了模度值的 概念，来衡量社交关系图中节点间是否有明显 社交结构，并采取贪婪策略不断和合并各个子 一一一 一 社区，以来寻找使整个社交关系图的模度值最 大的社区划分。此外，概算法的另一优点是执 行速度较快，在有ｎ个点和１ＴＩ条边中图中， 其最坏的时间复杂度为０（（ｍ＋ｎ） ｎ）。在处理 较大规模数据时较其他算法具有明显的优势。 本文也正是基于这一原因在本节选取该算法。 ４．２与目标机构相关的社区发掘 本节是基于如下的假设，某一个官方账户 在现实社会中常常会具有大量相关的成员，这 些成员在现实生活中上形成了一个相对稳固的 社交圈子，其中，会有相当一部分会在微博社 交网络上继续关注该机构的官方账户，并将其与其他成员的部 些对目标机构兴趣度较低的用户，以减少数据爬取过程中的引 分社交关系带到微博平台中。许多目标机构相关的成员在微博 入的噪声用户，例如一个学校的学生的好友群中，既有同伴同学， 中即使没有关注官方账户，也可以通过其好友的社交关系来评 也会有父母亲朋等，后者易形成噪声数据。经过压缩后用户关 估该用户的与目标机构的关系。这些有着共同好友关系的且对 系网的大小为： 目标机构有较高兴趣度的社区就是我们需要挖掘的相关社区。 表２双向关系图的压缩 由于社交发现算法是一项复杂度较高的计算过程，而且原 网络中也存在着大量的噪声，为了提高数据的计算速度和准确 度，本文首先对双向关系图进行两步压缩。 首先进行初次压缩，将图中所有粉丝数大于１００００的节点 及其相关的边删除，这些节点往往是媒体机构或社会名人，而 经过两次压缩后，实验社交网络已经达到了适宜的大小， 且往往引入了大量的无关的第二层粉丝，形成了噪声数据。然后， 对该图应用模度值最大化算法后，得到了一系列社区关系图， 对经过初次压缩的社交关系图进行二次压缩，具体方法是依次 社区聚类的大小分布如图３： 删除关注官方账户数量小于Ｔ１的第一层粉丝及相关的边，然后 可以看出，数据的中得到的社区大部分的大小都小于４００， 再删除关注第一层粉丝数量小于Ｔ 的第二层粉丝及相关的边， 这些社区经观察，大多为噪声社区，社区内部的成员的用户兴 Ｔｌ和Ｔ２在实验中分分别取２和３，Ｔ，取值一般小于Ｔ２，以保证 趣度（ＮＳｃｏｒｅ）值均比较低。出去这些大小较小的社区外，实验 对第二层粉丝的过滤更为严格。二次压缩的思想是去掉图中那 也得到了一些体积较大的社区，包含的成员的数量在５００－５５００ １２３・ 软件杂志欢迎推荐投稿：ｈｔｔｐ：／／ｗｗｗ．ｃｃｏｍｓｏｆｔ．ｃｏｒｎ／ 软件 （您的文章得到院士的关注） 左右。 张振华等：微博社交网络中面向机构的用户挖掘 最高的部分用户的兴趣度分布却非常不同。这个现象表明了社 交网络中目标机构在两层社交关系中会与多个社区相连通，而 ４．３相关社区的评估 为了评估社区的相关性，实验还收集了社区发现关系图中 每个社区又会分别在各自的社交范围内进一步延伸，引入一些 所有用户的基本信息，包括地理位置、用户名和个人描述等， 各自社区中的噪声节点。对每个社区区分噪声节点的方法是根 此外，实验还分别计算了每个用户的对目标机构的兴趣度，并 据每个社区的用户兴趣度设定阈值进行过滤。但每个社区的过 将每个社区内用户按照兴趣度降序排列，并计算每个社区的评 滤阈值应当有所不同，一般来讲，通过社区的Ｒ＠Ｎ值，并结合 价指标如下： 其用户信息，基本上可以确定与目标机构在现实中有较强关联 的几个社交圈子，对相关社交圈子可设定较为宽松的阈值，而 尺＠Ⅳ： 即实验计算每个社区兴趣度最高的Ｎ个用户兴趣度平均值， 来评估每个社区的相关度，试验中Ｎ选取４０。下表描述了实验 其他不能体现明显相关性的社区则设定相对严格的阈值，仅获 取兴趣度最高的部分用户即可。 ５结论 本文主要描述了一种新的在微博社交网络中发掘与某一机 构相关的用户群体的方法，文章主要定义了两类与机构相关的 用户，分别是对目标机构有较强兴趣度的用户和在社交网络中 体现相关社交圈子中的用户。对于两种不同的用户，文章分别 利用用户社交网络拓扑结构，计算用户与目标机构的兴趣度。 并利用社区发现方法并集合每个社区的Ｒ＠Ｎ指标来发现与目标 用户的社交圈子，通过比较用户的相关信息和用户兴趣度，能 够有效的发现相关圈子，并从中获取相关用户。 得到的相关社区和几个不相关社区的描述： 表３相关社区发现结果 参考文献 ［１】（（Ｔｗｉｔｔｅｒ活跃用户数已达１．４亿将在日积极扩张》．ｈｔｔｐ：／／ ｎｅｔ．ｃｈｉｎａｂｙｔｅ．ｃ０ｍ／２４７／ｌ２３ｌ２７４７．ｓｈｔｍｌ ［２］新浪微博注册用户突破３亿每日发博量超过ｌ亿条》．ｈｔｔｐ：／／ ｎｅｗｓ ｘｉｎｈｕａｎｅｔ．ｃｏｍ／ｔｅｃｈ／２０１２－０２／２９，ｃ一１２２７６９０８４．ｈｔｍ ［３】Ｊａｖａ，Ａ．，ｓｏｎｇ，Ｘ．．Ｗｈｙ ｗｅ Ｔｗｉｔｔｅｒ：Ｕｎｄｅｒｓｔａｎｄｉｎｇ ｍｉｃｒｏｂｌｏｇｇｉｎｇ ｕｓａｇｅ ａｎｄ ｃｏｍｍｕｎｉｔｉｅｓ．ＷｅｂＫＤＤ／ＳＮＡ－ ＫＤＤ ０７ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ９ｔｈ ＷｅｂＫＤＤ ａｎｄ １ｓｔ ＳＮＡ— ＫＤＤ ２００７ ｗｏｒｋｓｈｏｐ ｏｎ Ｗｅｂ ｍｊｎｊｎｇ ａｎｄ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ａｎａｌｙｓｉｓ．ＡＣＭ Ｎｅｗ Ｙｏｒｋ，ＮＹ，ＵＳＡ．２００７：５６－６５ 由于目标机构的官方账户的数量为４９个，社区Ａ中由于具 ［４】Ｍ．Ｅ．Ｊ．Ｎｅｗｍａｎ．Ｄｅｔｅｃｔｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ 有３６个官方账户，其Ｒ＠Ｎ值明显高于其他社区，且通过用户 个人描述，也能从该社区中发现较多目标机构的成员；社区Ｂ 中也包含了一定数量的官方账户，且兴趣度最高的人群的用户 信息也能体现出明显的相关性，但较社区Ａ次之；社区Ｃ和社 ｎｅｔｗｏｒｋｓ．Ｅｕｒ．Ｐｈｙｓ．Ｊ．Ｂ，２００４，３８（２）：３２１－３３０ 【５】维基百科，ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ，ｈｔｔｐ：／／ｅｎ．￣ｉ３ｄｐｅｄｉａ．ｏｒｇ／ ｗｉｋｉ／Ｃｏｍｍｕｎｉｙ＿ｓｔｔｒｕｃｔｕｒｅ ［６】Ｍ．Ｇｉｒｖａｎ ａｎｄ Ｍ．Ｅ．Ｊ．Ｎｅｗｍａｎ．Ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｓｏｃｉａｌ ａｎｄ ｂｉｏｌｏｇｉｃａｌ ｎｅｔｗｏｒｋｓ．Ｐｒｏｃ．Ｎａｔ／．Ａｃａｄ．Ｓｃｉ． 区Ｄ的相关性则更低，仅一部分用户具有一定相关性；社区Ｅ 中则较难发现相关用户，而且该社区用户的整体兴趣度均较低。 ＵＳＡ，２００２，９９（１２）：７８２１－７８２６ ［７】Ｍ．Ｅ．Ｊ．Ｎｅｗｍａｎ（２００４）．Ｆａｓｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｏｍｍｕｎｉｃｙ ｓｔｒｕｃｔｔｕｒｅ ｉｎ ｎｅｔｗｏｒｋｓ．Ｐｈｙｓ．Ｒｅｖ．Ｅ，２００４， 此外，通过观察，每个社区的成员中均会有大量的兴趣度 很低的用户，社区用户按兴趣度降序排列后，其分布曲线依然 是呈明显的长尾分布，但是得到的社区中，每个社区中兴趣度 ６９（６）：０Ｉ５６１３３ 软件杂志欢迎推荐投稿：ｈｔｔｐ：／／ｗｗｗ．ｃｃｏｍｓｏｆｔ．ｃｏｒｎ／ －１２４
