一种基于索引在用户电影网络中探测关键社区的方法

技术领域

本发明属于多媒体数据探测技术领域，尤其涉及一种基于索引在用户电影网络中探测关键社区的方法。

背景技术

随着人们文化生活的逐渐丰富，电影开始与人们的娱乐生活变得密不可分。现在的社会网络中存在着许多的兴趣小组，电影爱好小组也是其中的一个重要组成部分。所以，在社会网络中，用户电影这一类网络模型的研究对于发现社会网络中的兴趣关键社区有着重要意义。但用户电影网络具有一定的特殊性，它们由两组互不相交的集合组成，即，用户集合和电影集合，所以不能使用简单的网络结构来表现。因此，我们将用户电影网络建模为一个二部图G＝(U，L，E)，由两组互不相交的上层用户集合U和下层电影集合L组成，其中边只能连接来自不同集合的用户和电影，即边集E中边的两个端点只能一个存在用户集合U中，另一个存在电影集合L中。

作为网络分析中的一个基本问题，关键社区的探测已经得到了广泛的研究。然而，一般的模型都只关注于实体之间关系连接的内聚性，而忽略了另一个重要特征，即不同种实体之间的交互权重。在实际生活中，用户电影网络的边通常具有一定的权重，即用户对于电影的评分，该评分反映了用户对电影的兴趣程度，是社会网络中检测关键社区的一个重要指标。所以，忽略这个特征将使我们失去一个非常有用的信息。

发明内容

为了找到同时满足用户观看电影部数约束和评分约束的关键社区，本发明在用户电影网络上提出了一种新的关键社区模型，即(k，s)-社区模型，它满足三个条件：用户层的每个用户至少观看k部电影；电影层的每部电影的总评分不小于s，其中总评分为其所有相连用户的评分之和；社区是极大的，即不存在任何规模大于它的社区满足前两个条件。

本发明利用(k，s)-社区模型的嵌套特征开发了高效的基于索引的探测算法，能够在大型用户电影网络中迅速找到(k，s)-社区模型。此外，本发明提出的索引结构还可以减少索引的构建成本，达到空间消耗和查询效率之间的平衡。

本发明解决其技术问题的技术方案具体如下：一种基于索引在用户电影网络中探测关键社区的方法，所述关键社区为(k，s)-社区模型，满足三个条件：用户层的每个用户至少观看k部电影；电影层的每部电影的总评分不小于s，其中总评分为其所有相连用户的评分之和；社区是极大的，即不存在任何规模大于它的社区满足前两个条件；该方法包括：

步骤一，根据(k，s)-社区的嵌套特性，对用户电影网络G进行索引构建，包括：

(a)创建索引表和压缩表，所述索引表和压缩表均以k作为行序号，以s作为列序号，分别存储压缩后剩余的用户电影对象和压缩方向，所述压缩包括s方向的行压缩和k方向的列压缩；将索引表和压缩表初始化为空；

(b)从k＝0开始迭代计算；

(c)初始化s＝0；

(d)通过在(k，s)-社区上移除不满足观看部数大于等于k+1次的用户得到(k+1，s)-社区并进行更新，更新即，移除用户连接的每个电影的总评分更新为原总评分减去该移除用户对电影的评分；同理，移除不满足总评分大于等于s+1的电影得到(k，s+1)-社区并进行更新，更新即，移除电影连接的每个用户的观看部数更新为原部数减一；

(e)如果发现(k+1，s)-社区被包含在(k，s+1)-社区中，说明(k，s+1)-社区更大，将(k，s)-社区压缩到(k，s+1)-社区可以减少存储的用户数和电影数更多，即行压缩的效果更好；因此，索引表项[k][s]存储压缩(k，s)-社区到(k，s+1)-社区后剩余的用户电影集合，压缩表项[k][s]存储压缩方向“→”；

(f)如果发现(k，s+1)-社区被包含在(k+1，s)-社区中，说明(k+1，s)-社区更大，将(k，s)-社区压缩到(k+1，s)-社区可以减少存储的用户数和电影数更多，即列压缩的效果更好；因此，索引表项[k][s]存储压缩(k，s)-社区到(k+1，s)-社区后剩余的用户电影集合，压缩表项[k][s]存储压缩方向“↓”；

(g)如果(e)、(f)均不成立，那么同时做行压缩与列压缩；索引表项[k][s]存储压缩(k，s)-社区到(k，s+1)-社区与(k+1，s)-社区后剩余的用户电影集合，压缩表项[k][s]存储压缩方向“→”和“↓”；

(h)将s的值加1，然后重复步骤(d)～(h)直到s存在的最大值；

(i)将k的值加1，然后重复步骤(c)～(i)直到k存在的最大值；

步骤二，根据给定的k，s值对索引表进行访问，将索引表项[k][s]中记录的用户及电影添加到(k，s)-社区用户电影集合中，再根据压缩表项[k][s]中记录的压缩方向访问下一个索引表项，并将其中记录的用户及电影添加到(k，s)-社区用户电影集合中；迭代交替访问索引表和压缩表，直到访问的压缩表项中的压缩方向为空时，停止迭代；

步骤三，输出(k，s)-社区用户电影集合中所有用户和电影组成的子社区，即待探测的(k，s)-社区。

进一步地，所述(k，s)-社区的嵌套特性具体为：给定一个用户电影网络G，如果有k'≥k且s'≥s，那么(k’，s’)-社区是嵌套在(k，s)-社区中的。

进一步地，所述步骤二包括：

(a)将(k，s)-社区用户电影集合初始化为空集；

(b)根据k，s值找到索引表中对应的索引项[k][s]，然后将索引项[k][s]中记录的用户和电影添加到(k，s)-社区用户电影集合中；

(c)根据k，s值得到压缩表中对应的压缩方向；

(d)如果方向仅为“→”，那么接下来找到索引表项[k][s+1]并将其中记录的用户和电影添加到(k，s)-社区用户电影集合中；

(e)如果方向仅为“↓”，那么接下来找到索引表项[k+1][s]并将其中记录的用户和电影添加到(k，s)-社区用户电影集合中；

(f)如果有两个方向“→”和“↓”，那么接下来找到索引表项[k][s+1]和索引表项[k+1][s]，将其中记录的用户和电影添加到(k，s)-社区用户电影集合中并保证用户电影集合中用户和电影不重复出现；

(g)根据当前新找到的索引表项更新k，s值，重复步骤(c)～(g)，直到访问的压缩表项中的压缩方向为空时，停止迭代。

本发明还公开一种服务器，所述服务器包括处理器和存储器，所述存储器中存储有至少一条指令、至少一段程序、代码集或指令集，所述至少一条指令、所述至少一段程序、所述代码集或指令集由所述处理器加载并执行以实现上述基于索引在用户电影网络中探测关键社区的方法中的步骤。

本发明还公开一种计算机可读存储介质，所述存储介质中存储有至少一条指令、至少一段程序、代码集或指令集，所述至少一条指令、所述至少一段程序、所述代码集或指令集由处理器加载并执行以实现上述基于索引在用户电影网络中探测关键社区的方法中的步骤。

本发明的有益效果为：为了获取更有效的用户社区信息，本发明提出了新颖的(k，s)-社区模型，即关键社区中的用户在满足观看的电影部数达到一定要求的同时其中的每部电影还具有一定量的评分。考虑到大型网络处理和查询的复杂性，本发明提出了基于索引的探测算法，可以在大型用户电影网络中迅速找到(k，s)-社区模型，并且可以减少索引构建的空间成本开销。因此，基于索引在用户电影网络中探测关键社区的方法的应用对挖掘社交网络中的高质量电影兴趣团体和帮助用户进行电影推荐及电影评价分析有着极大的收益。

附图说明

图1是本发明基于索引在用户电影网络中探测关键社区的方法流程图；

图2是原始用户电影网络示意图；

图3是原始用户电影网络的索引表示意图；

图4是原始用户电影网络的压缩表示意图。

具体实施方式

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图对本发明的具体实施方式做详细的说明。

在下面的描述中阐述了很多具体细节以便于充分理解本发明，但是本发明还可以采用其他不同于在此描述的其它方式来实施，本领域技术人员可以在不违背本发明内涵的情况下做类似推广，因此本发明不受下面公开的具体实施例的限制。

本申请提出的一种基于索引在用户电影网络中探测关键社区的方法，包括巧妙的索引构造策略和高效的基于索引的(k，s)-社区探测算法。下面详细说明每部分的实现过程。

所述的索引构造策略是指利用(k，s)-社区模型的嵌套特性来构造索引，并且该特性还可以用来帮助减少索引构建成本，具体包括以下内容：

引理1，给定一个用户电影网络G，如果有k'≥k且s'≥s，那么(k'，s')-社区是嵌套在(k，s)-社区中的。

证明：如果在用户电影网络中存在一个子社区为(k'，s')-社区，且有k'≥k，s'≥s。那么根据该模型的定义，因为k'≥k且s'≥s，所以(k'，s')-社区是一个非极大的(k，s)-社区或者是一个极大的(k，s)-社区，包含在极大(k，s)-社区中。因此，引理1是正确的。

所述的高效的基于索引的(k，s)-社区探测算法，如图1所示，具体包括以下步骤：

步骤一，根据引理1对用户电影网络G进行索引构建，包括：

(a)创建索引表和压缩表，所述索引表和压缩表均以k作为行序号，以s作为列序号，分别存储压缩后剩余的用户电影对象和压缩方向，所述压缩包括s方向的行压缩和k方向的列压缩；将索引表和压缩表初始化为空；

(b)从k＝0开始迭代计算；

(c)初始化s＝0；

(d)通过在(k，s)-社区上移除不满足观看部数大于等于k+1次的用户得到(k+1，s)-社区并进行更新，更新即，移除用户连接的每个电影的总评分更新为原总评分减去该移除用户对电影的评分；同理，移除不满足总评分大于等于s+1的电影得到(k，s+1)-社区并进行更新，更新即，移除电影连接的每个用户的观看部数更新为原部数减一；

(e)如果发现(k+1，s)-社区被包含在(k，s+1)-社区中，说明(k，s+1)-社区更大，将(k，s)-社区压缩到(k，s+1)-社区可以减少存储的用户数和电影数更多，即行压缩的效果更好；因此，索引表项[k][s]存储压缩(k，s)-社区到(k，s+1)-社区后剩余的用户电影集合，压缩表项[k][s]存储压缩方向“→”；

(f)如果发现(k，s+1)-社区被包含在(k+1，s)-社区中，说明(k+1，s)-社区更大，将(k，s)-社区压缩到(k+1，s)-社区可以减少存储的用户数和电影数更多，即列压缩的效果更好；因此，索引表项[k][s]存储压缩(k，s)-社区到(k+1，s)-社区后剩余的用户电影集合，压缩表项[k][s]存储压缩方向“↓”；

(g)如果(e)、(f)均不成立，那么同时做行压缩与列压缩；索引表项[k][s]存储压缩(k，s)-社区到(k，s+1)-社区与(k+1，s)-社区后剩余的用户电影集合，压缩表项[k][s]存储压缩方向“→”和“↓”；

(h)将s的值加1，然后重复步骤(d)～(h)直到s存在的最大值；

(i)将k的值加1，然后重复步骤(c)～(i)直到k存在的最大值；

步骤二，根据给定的k，s值对索引表进行访问，将索引表项[k][s]中记录的用户及电影添加到(k，s)-社区用户电影集合中，再根据压缩表项[k][s]中记录的压缩方向访问下一个索引表项，并将其中记录的用户及电影添加到(k，s)-社区用户电影集合中；迭代交替访问索引表和压缩表，直到访问的压缩表项中的压缩方向为空时，停止迭代；具体包括以下子步骤：

(a)将(k，s)-社区用户电影集合初始化为空集；

(b)根据k，s值找到索引表中对应的索引项[k][s]，然后将索引项[k][s]中记录的用户和电影添加到(k，s)-社区用户电影集合中；

(c)根据k，s值得到压缩表中对应的压缩方向；

(d)如果方向仅为“→”，那么接下来找到索引表项[k][s+1]并将其中记录的用户和电影添加到(k，s)-社区用户电影集合中；

(e)如果方向仅为“↓”，那么接下来找到索引表项[k+1][s]并将其中记录的用户和电影添加到(k，s)-社区用户电影集合中；

(f)如果有两个方向“→”和“↓”，那么接下来找到索引表项[k][s+1]和索引表项[k+1][s]，将其中记录的用户和电影添加到(k，s)-社区用户电影集合中并保证用户电影集合中用户和电影不重复出现；

(g)根据当前新找到的索引表项更新k，s值，重复步骤(c)～(g)，直到访问的压缩表项中的压缩方向为空时，停止迭代。

步骤三，输出(k，s)-社区用户电影集合中所有用户和电影组成的子社区，即待探测的(k，s)-社区。

以下以图2所示的用户电影网络为示例描述本发明实现效果。图3和图4分别为图2的索引表和压缩表，其构建过程，以索引表项[1][2]以及对应压缩表项[1][2]的生成为例：由于(1，3)-社区用户电影集合为{a1，a2，a3，a4，m1，m3，m4，m5}，(2，2)-社区用户电影集合为{a2，a3，a4，m2，m3，m4，m5}，可得(1，3)-社区不包含(2，2)-社区，且(2，2)-社区也不包含(1，3)-社区，所以此时需要同时进行行压缩和列压缩，并在对应的压缩表项[1][2]中记录压缩方向“→，↓”。同时，由于(1，2)-社区减去(1，3)-社区与(2，2)-社区并集的用户电影集合为空，因此对应的索引表项[1][2]为空。

下面介绍基于索引的(k，s)-社区的查询过程，以(2，3)-社区为例：初始化(2，3)-社区用户电影集合为空集，先找到索引表项[2][3]，将其中记录的用户和电影{a4，m5}添加到(2，3)-社区集合中，此时(2，3)-社区用户电影集合为{a4，m5}；然后找到对应压缩表项[2][3]得到压缩方向“→”，根据此方向找到索引表项[2][4]，因为其中记录的用户和电影为空，所以此时(2，3)-社区用户电影集合仍为{a4，m5}；然后找到对应压缩表项[2][4]得到压缩方向“→”，根据此方向找到索引表项[2][5]，将其中记录的用户和电影{a2，a3，m3，m4}添加到(2，3)-社区用户电影集合中，此时(2，3)-社区用户电影集合为{a2，a3，a4，m3，m4，m5}；最后找到对应压缩表项[2][5]，发现为空，迭代结束。因此，(2，3)-社区用户电影集合内的a2，a3，a4，m3，m4，m5及其边组成的子社区，即为(2，3)-社区。可以发现与图2所示原始用户电影网络示意图相比，{a2，a3，a4，m3，m4，m5}组成的(2，3)-社区中用户与电影的关系更为密切且其中电影的评分更高，是该网络中的一个高质量电影兴趣团体，可以帮助进行电影推荐和电影评价分析。

此外，本发明在六个网络上进行了广泛的实验，以评估所提出方法的有效性和高效性。为了评估所提出方法的性能，我们通过改变参数k和s进行实验。本发明用算法消耗时间和索引空间成本来衡量所提出方法的有效性。对于每个设置，本发明运行200次并取平均值。所有程序均在标准的c++中实现，所有实验均在配备Intel Xeon 3.2GHz CPU和32GBRAM主内存的PC上进行。实验表明，本发明提出的基于索引的算法比基础算法快了42倍。

以上所述仅是本发明的优选实施方式，虽然本发明已以较佳实施例披露如上，然而并非用以限定本发明。任何熟悉本领域的技术人员，在不脱离本发明技术方案范围情况下，都可利用上述揭示的方法和技术内容对本发明技术方案做出许多可能的变动和修饰，或修改为等同变化的等效实施例。因此，凡是未脱离本发明技术方案的内容，依据本发明的技术实质对以上实施例所做的任何的简单修改、等同变化及修饰，均仍属于本发明技术方案保护的范围内。