基于最大团发现的特定Twitter用户群体的挖掘方法

摘要

本发明公开了一种基于最大团发现的特定Twitter用户群体的挖掘方法，包括以下步骤：S1、基于最大团的推文集合筛选，并获取用户群，进行用户群体挖掘；S2、获取用户群体后的相关分析。本发明提出一种根据用户所传播信息的关系进行用户群体挖掘方法，对一系列信息传播过程进行相关网络构建，并提取其中相关性最高的信息传播集合，再选择其中参与信息传播的用户群体，使用该方法能够较为快速地获取发送相同信息的用户群体。本发明还可以很大程度地降低特定Twitter用户群体挖掘的算法复杂度，缩小用户群体挖掘需要遍历的用户数目，提高求解问题的速度。

说明书

技术领域

本发明涉及一种基于最大团发现的特定Twitter用户群体的挖掘方法。

背景技术

社交网络21世纪以来取得了迅速发展和广泛应用，Twitter、FaceBook、QQ、微信、微 博等社交网络平台已经成为了研究信息传播的有效工具。研究在这些社交网络平台上信息 的传播特征与模式以构建信息传播网络模型，对抑制敏感信息扩散、预测信息传播、最大 化信息传播影响力、舆情分析与检测等实际问题的分析与解决具有重要作用。

Twitter自2006年创建以来，至今已拥有1.87亿日活跃用户，其具有实时、快速、多语 言等特性，这些特性使得Twitter平台中传播的信息会与同一时间现实社会中发生的时间密 切相关并会对其产生相当大的影响。

Twitter在政治、经济等方面具有相当大的影响力，因此对其进行信息传播的研究是由 重要意义的。以用户之间的关注关系为基础，通过分析关注关系的结构和用户之间的互动 行为，研究用户群体中的影响力用户，从而通过控制这些用户来达到促进信息传播或者抑 制信息传播的目的。

在Twitter分析研究中，通常将Twitter关系网络抽象为社交网络模型进行研究，将Twitter 中的用户或其他研究对象抽象为节点，用户或对象之间的关系抽象为边，构成社交网络图 模型。例如以Twitter平台中的用户作为节点，关注关系作为连边，构建起Twitter用户关系 网络；以推文转发关系作为连边可以构建起推文信息传播网络。对Twitter社交网络模型的 结构和布局进行分析，可以进一步得出研究对象之间的相关性质，例如用户之间的关注关 系连边稠密性反映出用户之间对应关系的紧密性。在社交网络分析研究中，如果网络中一 部分节点之间具有紧密的联系，则认为这些节点属于一个社团结构。如果网络图结构中的 任意节点两两相连，构成的图结构称为完全图。在网络中寻找完全图的问题称为最大团问 题，最大团即一个网络中的最大完全子图。在社交网络中，最大团反映了社交网络用户节 点之间存在着某种紧密的关系，根据这种紧密关系能够进行更加深入的分析研究，解决实 际社交网络中特定用户识别的实际问题。

目前对于用户群体挖掘的主要研究大多基于社交网络的网络结构和属性两大要素来进行， 同时现有的研究认为用户群体的网络结构特征与社区类似，因此也有很多研究采用社区发现 技术来对关联紧密的用户群体进行挖掘。

基于社交网络的网络结构的用户群体挖掘技术是从不同的角度来对网络进行划分，而基 于属性的用户群体挖掘算法是利用用户属性信息来对用户节点进行聚类或者分类，再将聚类 或分类的结果放到不同的群体集合中。这两种用户群体挖掘的技术都有各自的优点，但前者 必须获取所有相关用户进行社交网络构建，才能根据结构来对用户群体进行划分；而后者忽 略了用户之间的连接关系，会使得用户群体获取不全面。

发明内容

本发明的目的在于克服现有技术的不足，提供一种根据用户所传播信息的关系进行用 户群体挖掘方法，对一系列信息传播过程进行相关网络构建，并提取其中相关性最高的信 息传播集合，再选择其中参与信息传播的用户群体，使用该方法能够较为快速地获取发送 相同信息的用户群体的基于最大团发现的特定Twitter用户群体的挖掘方法。

本发明的目的是通过以下技术方案来实现的：基于最大团发现的特定Twitter用户群体 的挖掘方法，包括以下步骤：

S1、基于最大团的推文集合筛选，并获取用户群，进行用户群体挖掘；

S2、获取用户群体后的相关分析。

进一步地，所述步骤S1具体实现方法为：

S11、参数定义：将推文关系图定义为G＝(V，E)的形式，其中V是图中节点的集合，V中 的每个节点v表示一条推文；E是边的集合，E中的每条边e＝(v，u，w)表示推文节点v与u之 间存在相同的参与转发的用户，w为边的权重，表示推文节点v与u有w个相同的转发用户；

推文关系图是一个有权无向图，通过TwitterAPI根据关键字采集到的多条原始推文作 为节点的集合V，同时采集所有原始推文的转发用户并计算各条原始推文相同的转发用户得 到边的集合E；设图中连边权值的最小值为x，则称推文关系图为x阶推文关系图；

S12、构建推文关系图：

推文筛选：将转发量小于1000的原始推文过滤掉，仅对转发量大于等于1000的原始 推文进行推文关系图的构建；

连边及边权值筛选：以原始推文作为节点，对所有的原始推文节点根据有相同转发用 户的规则进行连边的建立，构建出一个推文关系图；对推文关系图连边进行筛选，保留权 值大于x的连边，得到一个x阶的推文关系图；

S13、用户群体挖掘：在推文关系图中联系紧密的部分中寻找推文集合以及对应的转发 用户群体，使用连通片中的最大团结构来寻找连接最紧密、由最多相同用户转发的推文集 合；在从推文关系图所提取的最大团结构中，任意的两条推文都均有大于等于推文关系图 阶数x的相同转发用户；在给定推文条数n的前提下，提取所有n个节点的完全子图结构中 边权值和最大的完全子图结构，这n个节点对应的原始推文集合就是所求的推文集合；

得到推文集合之后，仅对各条原始推文对应的转发推文的用户集合求交集，得到目标 用户群体，这个用户群体内的用户共同转发了相同的多条推文。

进一步地，所述步骤S2具体实现方法为：构建用户群体对不同推文的转发网络、构建 用户群体的关注网络。

本发明的有益效果是：本发明提出一种根据用户所传播信息的关系进行用户群体挖掘方 法，对一系列信息传播过程进行相关网络构建，并提取其中相关性最高的信息传播集合，再 选择其中参与信息传播的用户群体，使用该方法能够较为快速地获取发送相同信息的用户群 体。本发明还可以很大程度地降低特定Twitter用户群体挖掘的算法复杂度，缩小用户群体挖 掘需要遍历的用户数目，提高求解问题的速度。

附图说明

图1为本实施例中第一个数据集构建推文关系图的结果；

图2为本实施例中第二个数据集构建100阶推文关系图的结果。

具体实施方式

在对Twitter中推文信息传播进行研究的过程中(Twitter中所传播的信息为推文，下文 均以推文作为替代描述)，需要针对特定用户群体，挖掘与识别群体内部具有不同信息传 播行为的用户，及其在信息传播过程中承担的角色。因此，首先需要在海量的Twitter数据 中，挖掘满足特定要求的用户群体，才能够进一步对群体中的用户进行分析。但在实际情 况中，难以在推文采集过程中，直接对用户进行筛选，发现特定的用户群体。因此本发明 提出了基于最大团发现的特定Twitter用户群体挖掘方法，在构建推文传播网络模型的基础 上，生成推文关系图模型，进一步在推文关系图中寻找最大团，获取的相关推文集合，以 便于挖掘特定目标用户群体，为研究特定用户群的传播行为提供相应的数据支撑。

下面结合附图和具体实施例进一步说明本发明的技术方案。

基于最大团发现的特定Twitter用户群体的挖掘方法，包括以下步骤：

S1、基于最大团的推文集合筛选，并获取用户群，进行用户群体挖掘；具体实现方法 为：

S11、参数定义：将推文关系图定义为G＝(V，E)的形式，其中V是图中节点的集合，V中 的每个节点v表示一条推文；E是边的集合，E中的每条边e＝(v，u，w)表示推文节点v与u之 间存在相同的参与转发的用户，w为边的权重，表示推文节点v与u有w个相同的转发用户；

推文关系图是一个有权无向图，通过TwitterAPI根据关键字采集到的多条原始推文作 为节点的集合V，同时采集所有原始推文的转发用户并计算各条原始推文相同的转发用户得 到边的集合E；设图中连边权值的最小值为x，则称推文关系图为x阶推文关系图；

S12、构建推文关系图：本实施例中使用了从Twitter采集得到的两个推文数据集用于 推文关系图构建，并在构建推文关系图之后进行用户群体的挖掘。

推文筛选：由于基于关键字采集到的原始推文和转发推文数量庞大，且在所有原始推 文中，转发量小的推文数量会占相当大的一部分，因此在构建推文关系图中需要先筛选掉 转发量小的原始推文，将转发量小于1000的原始推文过滤掉，仅对转发量大于等于1000 的原始推文进行推文关系图的构建；

连边及边权值筛选：以原始推文作为节点，对所有的原始推文节点根据有相同转发用 户的规则进行连边的建立，构建出一个推文关系图(接近于完全图)；这是因为Twitter上 有一些十分活跃的用户，这些用户的数量不多，却会转发每一条感兴趣的原始推文，就会 使得所构建的推文关系图中有许多权值为个位数的连边，提高了可视化的难度。因此需要 对推文关系图连边进行筛选，保留权值大于x的连边，得到一个x阶的推文关系图；

对两个数据集分别构建推文关系图的结果如图1和图2所示所示。图1为第一个数据 集构建推文关系图的结果。图1(a)为800阶推文关系图中的连通片，图1(b)为1000 阶推文关系图中的几个连通片。可以观察到，800阶推文关系图中的连通片虽然只有一个， 但是可以明显地看到有两个比较明显的紧密社团，而当阈值提高到1000时，图中的推文节 点会明显地分为三个连通片。对1000阶推文关系图里三个连通片中节点对应的推文内容进 行观察，可以发现，各个连通片中节点所表示的推文内容都分别有一致的倾向，且两个最 大的连通片之间的推文内容倾向几乎完全相反。

图2为第二个数据集构建100阶推文关系图的结果，在图中可以观察到，一些推文节 点之间有紧密的连接关系(图中用方框圈出部分)，各个部分内部的节点所表示的推文主 题或是比较相近，或是都由一个或几个关注者数量很多的Twitter用户发布。

S13、用户群体挖掘：基于以上两个数据集构建的推文关系图，可以在推文关系图中联 系紧密的部分中寻找推文集合以及对应的转发用户群体，使用连通片中的最大团结构来寻 找连接最紧密、由最多相同用户转发的推文集合；在从推文关系图所提取的最大团结构中， 任意的两条推文都均有大于等于推文关系图阶数x的相同转发用户，缩小了挖掘用户群体的 范围；以图1(b)中的1000阶推文关系图为例，在两个大的连通片中找到的最大团的节点 数即原始推文数分别为496和64，在这样数量级的推文中，使用遍历的方式寻找转发了多 条推文的最大用户群体的复杂度不会很高。在给定推文条数n的前提下，提取所有n个节点 的完全子图结构中边权值和最大的完全子图结构，这n个节点对应的原始推文集合就是所求 的推文集合；

得到推文集合之后，仅对各条原始推文对应的转发推文的用户集合求交集，得到目标 用户群体，这个用户群体内的用户共同转发了相同的多条推文。

S2、获取用户群体后的相关分析；进行用户群体挖掘后，就可以针对这个用户群体进 行一系列信息传播分析，如：构建用户群体对不同推文的转发网络、构建用户群体的关注 网络。

构建转发网络后可以对单个用户在不同推文转发网络中的位置进行观察分析，可以发 现同一个用户在不同的信息传播中可能处于不同的位置，即用户u转发了两条推文A、B， 在A中u可能只进行了转发而没有引起其他人对这条推文的转发，而在B中u转发了这条推文 却引起了许多人的关注，这就有了传播影响力的差异。

构建用户关注网络后可以结合关注网络的结构来对用户在关注网络中的影响力进行评 估，一般使用复杂网络中的方法对网络中的节点进行参数计算，将所得的参数用于评估节 点的影响力。

除了上述的方法，还可以结合信息的传播是否结合了关注关系来对用户进行分析，以 达到识别高影响力用户的目的。

本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的 原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通 技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体 变形和组合，这些变形和组合仍然在本发明的保护范围内。