一种社交网络社区的索引和查询方法   0    0

本发明公开了一种社交网络社区的索引和查询方法。本发明步骤如下：步骤(1)、社交网络的抽象；步骤(2)、k‑核心社区的树形索引的构建；步骤(3)、建立社交网络图顶点‑树节点的对应关系；步骤(4)、用户顶点u所属社区的查询。本发明通过对社交网络中的社区建立索引结构，提高了查询特定结点所属社区的效率，这对大规模社交网络中的社区检索技术发展具有积极意义。本发明通过构建一个社交网络中所有社区的树形结构，用树形结构存储社区之间的嵌套关系。在一次性构建了整个社交网络的社区索引结构以后，就可以高效快捷地进行针对某个用户结点的所属社区查询。

1.一种社交网络社区的索引和查询方法，其特征在于针对社交网络中用户所属社区的查询特点，通过构建树形索引结构，提供一种高效的检索方法，在构建索引结构后，之后的查询中不需要再次遍历用户所属的所有社区，通过访问树形索引即可返回查询结果；具体步骤如下：步骤(1)、社交网络的抽象；步骤(2)、k‑核心社区的树形索引的构建；步骤(3)、建立社交网络图顶点‑树节点的对应关系；步骤(4)、用户顶点u所属社区的查询；
步骤(1)所述的社交网络的抽象，具体实现如下：
将一个社交网络图G(V,E)中的所有用户及用户之间的关系抽象，用顶点的集合V表示用户；用户之间的关系表示为两个顶点之间的边，用边的集合E来表示；
步骤(2)所述的k‑核心社区的树形索引的构建，具体实现如下：
对于社交网络图G(V,E)中的任一顶点v，顶点v的核心号码是指在所有包含顶点v的k‑核心社区中，最大的k值作为该顶点v的核心号码；
树形索引的构建步骤包括社交网络图G中k‑核心社区的解构，即分解社交网络图G，获得社交网络图G中所有顶点的核心号码；然后从根节点的0‑核心社区出发，依次构建树形索引；
所述的社交网络图G中k‑核心社区的解构的具体实现如下：
k‑核心社区的解构的基本过程是在社交网络图G中，按照顶点的度数，迭代删除所有度数小于k的顶点，以及该顶点相邻的边，那么剩下的图就是k‑核心社区；
所述剩下的图所包含的顶点的核心号码就至少大于等于k；
2‑1‑1使用列表Core表示每个顶点的核心号码，列表Core中元素格式为(v,ck),其中v表示顶点，ck表示顶点v的核心号码；初始化列表Core为空；
使用数组degree存储遍历到的顶点的当前度数，例如degree[v]表示遍历到的顶点v的当前度数；
2‑1‑2统计社交网络图G中所有顶点的度数；并对所有顶点根据其度数进行升序排序；
2‑1‑3若社交网络图G非空，取社交网络图G中升序排序后度数最小的顶点v，进行以下操作：
将当前顶点v的当前度数degree[v]赋值到顶点v的核心号码ck，插入Core列表，即在Core列表中插入(v,degree[v])；
对于顶点v的每个邻接顶点u进行以下操作：
如果degree[u]>degree[v]则degree[u]＝degree[u]‑1，即确定顶点v的核心号码后，其邻接顶点u的度数减1；
从社交网络图G中删除顶点v，重新对顶点集合V中所有顶点按度数排序，重复步骤2‑1‑
3‘
所述的构建k‑核心社区的树形索引的具体实现如下：
2‑2‑1将Core列表按每个元素的核心号码进行升序排序；
2‑2‑2初始化根节点root，根节点包含信息(0,Vk0，Vk0‑else)；其中，0表示根节点的k值为0，Vk0是社交网络图G中所有k‑核心号码为0的顶点集合，Vk0‑else为所有k‑核心号码非0的顶点集合；
初始化临时树节点node，节点包含信息(q,Vkq，Vkq‑else)；其中，q表示临时树节点node的k核心号码值为q，Vqk是社交网络图G中所有k‑核心号码为q的顶点集合，Vkq‑else为所有k‑核心号码非q的顶点集合；
2‑2‑3初始化队列nodeQueueA；
2‑2‑4将根节点root推入队列nodeQueueA中；
2‑2‑5当队列nodeQueueA非空时，进行以下操作：
使用临时树节点node保存队列弹出的头部元素nodeQueueA.pop()；
对树节点node包含的节点集合node.Vk‑else中所有节点，在社交网络图G中查找由这些顶点构成的连通子图,得到连通子图集合{Gsub1,Gsub2,…Gsubn}；
对连通子图集合{Gsub1,Gsub2,…Gsubn}中子图根据顺序进行以下操作：
①取子图Gsubi中所有顶点，并将所有顶点按其k‑核心号码进行排序；其中i为自然数，取值为1，2…n中的一个值；
②将所以顶点中的最小k‑核心号码值,设置为临时变量i；
生成一个新的树节点node‑sub，该树节点node‑sub包含信息(i,Vki，Vki‑else)，此处树节点node‑sub的i值就是前述最小k‑核心号码值，集合Vki包含子图Gsubi中核心号码为i的所有顶点，集合Vki‑else包含这个连通子图中核心号码非i的顶点；
③将新生成树节点node‑sub置为树节点node的子节点；
④然后将树节点node‑sub推入队列；
对上述所有子图进行步骤①～步骤④的操作，将树节点node包含的顶点集合node.Vk‑else置空；
所述步骤(3)建立社交网络图顶点‑树节点的对应关系，具体实现如下：
使用一个有序列表MAP存储社交网络图顶点‑树节点的对应关系，对步骤(2)中构建的树形索引进行深度优先遍历，获得社交网络图顶点‑树节点的对应关系后，向列表MAP添加该对应关系；
从根节点root出发对树形索引进行深度优先遍历，具体实现为：
3‑1初始化堆栈nodeStack；
3‑2初始化临时树节点node；
3‑3将根节点root压入堆栈；
3‑4当堆栈nodeStack非空时执行以下操作：
3‑4‑1使用临时树节点node保存堆栈顶部值nodeStack.top；
3‑4‑2遍历临时树节点node中社交网络图的顶点，为每个顶点在列表MAP中添加社交网络图顶点‑树节点对应关系；
3‑4‑3弹出堆栈顶部元素：nodeStack.pop()；
3‑4‑4遍历临时树节点node的孩子节点，如果一个序号为i的孩子节点childi非空，则压入堆栈nodeStack：nodeStack.push(node‑>childi)；
3‑5完成遍历以后，以顶点ID为关键字对列表MAP进行排序；
所述步骤(4)所述的用户顶点u所属社区的查询，具体实现如下：
4‑1初始化临时树节点node；
4‑2查询列表MAP，获得顶点u在树形索引中的节点位置，并将该节点位置赋予临时树节点node；
4‑3对临时树节点node进行广度优先遍历，返回以临时树节点node为根节点的子树中包含的所有顶点的并集，执行以下操作：
4‑3‑1初始化队列nodeQueue；
4‑3‑2初始化临时树节点node；
4‑3‑3初始化返回值k＝node.k；
4‑3‑4初始化返回的顶点集合
4‑3‑5将临时树节点node推入队列nodeQueue；
4‑3‑6当队列nodeQueue非空时执行以下操作：
使用临时树节点node保存弹出的队列头部元素nodeQueue.pop()；
合并临时树节点node包含的顶点至集合Vu；
遍历临时树节点node的孩子节点，如果一个序号为i的孩子节点childi非空，则压入队列nodeQueue：nodeQueue.push(node‑>childi)；
4‑4返回顶点u的k值和所属的社区所包含的顶点集合Vu。