一种基于社区划分的在线社交网络海量数据存储方法

摘要

本发明公开一种基于社区划分的在线社交网络海量数据存储方法，从社交网络的图结构出发，首先根据节点度大小将网络分成名人用户层和普通用户层，再对每一层利用模块度优化的方法进行社区划分。设计一种小集团结伴策略对初始网络进行预处理，形成一个超网，采用边权重优先方案逐步合并超节点以提高模块度。社区划分完成之后，优先存储普通用户数据，将同一社区的用户数据存储在相同服务器节点上，对于名人用户数据优先考虑选择存放在粉丝最多的服务器，其次考虑存放在自身社区所在的服务器节点。设计名人用户数据多副本存储，以减少单台服务器的负载。利用社区划分方法存储社交网络数据，可以提高访问的局部性，减少通信耗费。

说明书

技术领域

本发明涉及一种数据存储方法，具体涉及一种基于社区划分的在线社交网络 海量数据存储方法。

背景技术

以用户创造内容为主的Web2.0已经渗透到人们日常生活的方方面面，大量 在线社交网站迅速兴起，国外的如Facebook、Twitter，国内的如微博、人人网 等已经成为人们分享和获取信息的主要平台。人们通过社交网络互动交流，产生 的数据和访问规模呈爆炸式增长，给数据的存储和管理带来严峻挑战。

目前网站的架构中基本采用传统的分布式存储方案，如哈希、一致性散列等 技术。例如Twitter使用Gizzard，通过将特定范围的数据映射到特定的机器上 来实现数据的划分，Facebook使用的Cassandra通过使用用户ID的hash值来 划分数据，而Amazon使用的Dynamo通过一致性散列来划分数据。这些划分方案 将用户数据随机地放置在集群的各服务器中，方法简单易行，然而这样的数据切 分方式忽略了社交网络的社区结构性质，在系统运行期间会增加额外的通信代 价，而且访问时延较大。

研究发现社交网络中人与人的好友关系图是具有社区结构特征的网络，即社 区内部节点之间的边比较稠密，而社区之间的边比较稀疏，已有分析发现 Facebook中的社区结构便是按照年级或宿舍划分的学生集体。社交网络中用户 的交互对象大多是和自己在同一社区的好友，例如同一专业、同一公司等。用户 基本的操作主要是发布信息和浏览信息，用户登录时，系统先查阅其关注的好友 列表，然后把他们最近发布的信息显示在该用户的主页；用户发布信息时，系统 先查阅其粉丝列表，然后将该信息更新到这些粉丝的主页。这样的业务流程不仅 会涉及到用户本身的数据，还会涉及到用户的好友数据，浏览时还可能涉及到好 友的好友这样的多跳关系。从网络结构角度来看，用户与少量几跳以内的好友联 系会比较紧密，具有典型的社区性。如果社交网络中某个用户的同一社区内的好 友散布在多台服务器上，那么查询和更新操作需要向多台服务器发送请求，对于 具有海量用户的社交网络来说这样的通信代价太高。

发明内容

发明目的：为解决现有技术中存在的不足，本发明提供一种基于社区划分的 在线社交网络海量数据存储方法。

技术方案：本发明的一种基于社区划分的在线社交网络海量数据存储方法， 包括以下步骤：

（1）获取社交网络结构；

（2）将步骤（1）中所得的社交网络结构分为名人用户网络层和普通用户网 络层；

（3）对步骤（2）中的每一层网络进行社区划分；

（4）按照社区大小进行数据存储；

（5）将名人用户进行多副本存储。

进一步的，所述步骤（1）中的获取社交网络结构的具体步骤如下：

（11）将社交网络中的用户抽象成网络中的节点，则用户之间的关注与被关 注的好友关系抽象为有向边，即用户i关注用户j，表示有一条边从节点i指向节 点j，定义A是这个网络的邻接矩阵，A_ij表示节点i指向节点j的边的权重，不 同的应用场景中，权重代表的意义不同，可以根据实际情况设置权重的值，例如 可以均设置为1；

（12）将上述有向网络转换成无向网络，调整两个节点之间的权重，若用户 i与用户j互相关注，则A_ij为2；若两个用户互不关注，则A_ij为0；若两个用户中 只存在单向的关注关系，则A_ij为1，最后设置A_ji=A_ij。

进一步的，所述步骤（2）中的具体步骤为：设定粉丝数量阈值为K，粉丝 数量大于K的社交网络用户为名人用户，粉丝数量小于K的社交网络用户为普通 用户，原网络便可以分为普通用户网络层和名人用户网络层，统称为G。

进一步的，采用模块度优化方法对步骤（2）中所得普通用户网络层和名人 用户网络层分别进行社区划分，模块度值越高表明该划分越能体现网络的社区结 构，那么社区划分就变成了一个模块度优化的问题，即从所有可能的划分中寻找 一个划分，使得该划分具有最大的模块度；然而如果把单个节点作为计算单位， 对于具有海量用户的社交网络来说计算量非常大。

本发明采用一种小集团结伴策略，先让局部区域范围内的节点结伴形成一个 紧密的小集团，再将这些小集团作为网络新节点，称之为超节点，超节点构成的 关系网络即一个超网，再对超网通过模块度优化的方法进行社区划分，具体方法 如下：

（31）假设初始网络有n个节点，编号为i(i=1,2,...,n)，每个节点的度分 别为k_i，依据节点度优先方法，优先让度大的节点选择h跳以内的好友为一个小 集团，再从剩余的节点中找到节点度最大的节点，重复结伴操作，直至所有节点 都被包含在一个小集团中，对每个小集团编号C_i，即初始的社区编号；

（32）结伴操作完成后，将每个小集团封装成一个超节点，超节点与超节点 之间边的权重设定为内部子节点之间的权重之和，形成超网G₀，即初始的网络 结构；

（33）通过模块度优化的方法，将超节点合并，超节点之间连边的权重越大， 则说明两个超节点内部的节点联系越紧密；设t时刻网络结构为G_t，邻接矩阵为 A_t；

根据公式$Q=\frac{1}{2m}\mathrm{\Sigma i},j[A_{\mathrm{ij}}-\frac{k_i{k}_j}{2m}]\delta (C_i,C_J),$计算此时模块度为Q_t，公式中 k_t=∑_iA_ij，m为网络中所有连边的权重之和，即k_i是节点i连边 的权重之和，即k_t=∑_jA_ij，C_i表示节点i所在的社区编号，δ(x,y)是一个关于x 和y的函数,当x=y时值为1，反之为0；

（34）t+1时刻的合并超节点操作中，采用权重优先策略，优先将权重大的 边两端的超节点合并，计算合并后的模块度Q_new；如果Q_new≥Q_t，则选择合并， Q_t+1=Q_new，形成网络Q_t+1；反之不合并，继续选择边权重次大的两个超节点合 并；

（35）重复上述合并、调整网络的过程，直至模块度的值基本稳定为止，稳 定状态时相邻两个时刻的模块度的值相差不大于ε值，即Q_t+1-Q_t≤ε。

进一步的，所述步骤（4）中的数据存储方法为按照社区大小存储数据，具 体步骤为：设有n_c个社区并按照数据量大小排序，编号记为C_i(i=1,2,...,n_c)， 有n_s台服务器(n_c>n_s)；首先存储普通用户数据，对每个社区依次查找适合的服 务器，找到满足待存社区存储需求的第一台服务器存储，然后存储名人用户数据， 其存储策略优先选择存放在粉丝数最多的服务器节点，其次考虑存放在自身社区 所在的服务器节点。

进一步的，所述步骤（5）的具体步骤为：根据粉丝的社区分布，名人用户 的数据另外设置一定数量的存储副本，副本数据和部分粉丝节点存储在同一台服 务器上；把副本放置在粉丝数量较多的几个服务器上，其他粉丝由主数据节点直 接管辖；名人用户发布信息时，主数据节点将数据发送给副本节点，然后主数据 节点和副本节点再将数据发送给各自管辖的粉丝用户。

有益效果：本发明与现有技术相比具有以下优点：

（1）本发明适用于社交网络海量数据存储和管理，设计了一种通过社交网 络图结构的社区划分方法来切分数据，这种方法改进传统的基于一致性散列等分 布式存储方式，使得相同社区的用户存储在同一台服务器上，用户的相关数据操 作就可以在本地完成，减少因好友太分散而造成的服务器之间的通信耗费。

（2）本发明根据好友数量将用户分为名人用户和普通用户，并针对名人用 户多副本存储策略，把副本数据分布存储在粉丝较多的服务器节点上，在名人用 户推送数据时可以减少单台服务器的压力，有效提高系统性能，分担单台服务器 的负载。

（3）同一社区的用户之间联系更紧密，兴趣爱好等相似度较高，根据社区 结构性质可以很容易扩展社交网络的功能，如好友推荐、信息推送等。

附图说明

图1为本发明中针对名人用户多副本存储方案示意图；

图2为本发明中社区划分方法流程图。

具体实施方式

下面对本发明技术方案进行详细说明，但是本发明的保护范围不局限于所述 实施例。

本发明的一种基于社区划分的在线社交网络海量数据存储方法，包括以下步 骤：

（1）获取社交网络结构；

（2）将步骤（1）中所得的社交网络结构分为名人用户网络层和普通用户网 络层；

（3）对步骤（2）中的每一层网络进行社区划分；

（4）按照社区大小进行数据存储；

（5）将名人用户进行多副本存储。

上述步骤（1）中的获取社交网络结构的具体步骤如下：

将社交网络中的用户抽象成网络中的节点，则用户之间的关注与被关注的好 友关系抽象为有向边，即用户i关注用户j，表示有一条边从节点i指向节点j， 定义A是这个网络的邻接矩阵，A_ij表示节点i指向节点j的边的权重，不同的应 用场景中，权重代表的意义不同，可以根据实际情况设置权重的值，例如可以均 设置为1；

（12）将上述有向网络转换成无向网络，调整两个节点之间的权重，若用户 i与用户j互相关注，则A_ij为2；若两个用户互不关注，则A_ij为0；若两个用户中 只存在单向的关注关系，则A_ij为1，最后设置A_ji=A_ij。

所述步骤（2）中的具体步骤为：设定粉丝数量阈值为K，粉丝数量大于K的 社交网络用户为名人用户，粉丝数量小于K的社交网络用户为普通用户，原网络 便可以分为普通用户网络层和名人用户网络层，统称为G。

采用模块度优化方法对步骤（2）中所得普通用户网络层和名人用户网络层 分别进行社区划分，模块度值越高表明该划分越能体现网络的社区结构，那么社 区划分就变成了一个模块度优化的问题，即从所有可能的划分中寻找一个划分， 使得该划分具有最大的模块度；然而如果把单个节点作为计算单位，对于具有海 量用户的社交网络来说计算量非常大。

本发明采用一种小集团结伴策略，先让局部区域范围内的节点结伴形成一个 紧密的小集团，再将这些小集团作为网络新节点，称之为超节点，超节点构成的 关系网络即一个超网，再对超网通过模块度优化的方法进行社区划分，具体方法 如下：

（31）假设初始网络有n个节点，编号为i(i=1,2,...,n)，每个节点的度分 别为k_i，依据节点度优先方法，优先让度大的节点选择h跳以内的好友为一个小 集团，再从剩余的节点中找到节点度最大的节点，重复结伴操作，直至所有节点 都被包含在一个小集团中，对每个小集团编号C_i，即初始的社区编号；

（32）结伴操作完成后，将每个小集团封装成一个超节点，超节点与超节点 之间边的权重设定为内部子节点之间的权重之和，形成超网G₀，即初始的网络 结构；

（33）通过模块度优化的方法，将超节点合并，超节点之间连边的权重越大， 则说明两个超节点内部的节点联系越紧密；设t时刻网络结构为G_t，邻接矩阵为 A_t；

根据公式$Q=\frac{1}{2m}\mathrm{\Sigma i},j[A_{\mathrm{ij}}-\frac{k_i{k}_j}{2m}]\delta (C_i,C_J),$计算此时模块度为Q_t，公式中 k_t=∑_iA_ij，m为网络中所有连边的权重之和，即k_i是节点i连边 的权重之和，即k_t=∑_jA_ij，C_i表示节点i所在的社区编号，δ(x,y)是一个关于x 和y的函数,当x=y时值为1，反之为0；

（34）t+1时刻的合并超节点操作中，采用权重优先策略，优先将权重大的 边两端的超节点合并，计算合并后的模块度Q_new；如果Q_new≥Q_t，则选择合并， Q_t+1=Q_new，形成网络Q_t+1；反之不合并，继续选择边权重次大的两个超节点合 并；

（35）重复上述合并、调整网络的过程，直至模块度的值基本稳定为止，稳 定状态时相邻两个时刻的模块度的值相差不大于ε值，即Q_t+1-Q_t≤ε。

上述步骤（4）中的数据存储方法为按照社区大小存储数据，具体步骤为： 设有n_c个社区并按照数据量大小排序，编号记为C_i(i=1,2,...,n_c)，有n_s台服务 器(n_c>n_s)；首先存储普通用户数据，对每个社区依次查找适合的服务器，找到 满足待存社区存储需求的第一台服务器存储，然后存储名人用户数据，其存储策 略优先选择存放在粉丝数最多的服务器节点，其次考虑存放在自身社区所在的服 务器节点。

所述步骤（5）的具体步骤为：根据粉丝的社区分布，名人用户的数据另外 设置一定数量的存储副本，副本数据和部分粉丝节点存储在同一台服务器上；把 副本放置在粉丝数量较多的几个服务器上，其他粉丝由主数据节点直接管辖；名 人用户发布信息时，主数据节点将数据发送给副本节点，然后主数据节点和副本 节点再将数据发送给各自管辖的粉丝用户。