1.一种基于社区检索的影响力社区搜索方法,其特征在于,包括以下步骤:
(1)获取社交网络拓扑图、需要搜索的社区数量r、以及社区中节点邻居个数的约束值k,该社交网络拓扑图中的每个节点代表一个用户实体,每条边代表两个用户实体之间的社交关系;
(2)从步骤(1)获取的社交网络拓扑图中确定每个节点的邻居个数和影响力值,从社区网络拓扑图中将邻居个数小于k的节点、以及与该节点相连的所有边删除,并将剩余的所有节点按照影响力值从大到小的顺序进行排列;
(3)根据步骤(2)的排列结果从社交网络拓扑图中删除影响力值小于阈值t的节点,从而形成更新后的社交网络拓扑图,其中阈值t的大小等于步骤(2)的排列结果中排在第(k+r)位的影响力值;
(4)针对步骤(3)更新后的社交网络拓扑图,根据其中各个节点的邻居个数和影响力值确定关键节点,选择其中影响力值相同的关键节点,并根据更新后的社交网络拓扑图对选择的关键节点进行更新;
(5)针对步骤(4)中更新后的关键节点,所有关键节点构成关键节点集合,根据集合中的每一个关键节点和步骤(3)更新后的社交网络拓扑图中剩余节点的邻居个数确定该关键节点对应的候选节点,每一个关键节点对应的所有候选节点构成该关键节点对应的候选节点集合;
(6)获取步骤(5)中得到的关键节点集合以及该关键节点集合中关键节点的数量m,判断步骤(5)获取的更新后的关键节点集合中关键节点的数量m是否大于或等于需要搜索的社区数量r,如果是则进入步骤(8),否则进入步骤(7);
(7)将阈值t的值更新为其当前值的2/3,并返回步骤(3);
(8)对步骤(5)更新后的关键节点集合中所有关键节点对应的候选节点集合进行处理,从而得到步骤(1)中社交网络拓扑图中的前r个影响力社区,过程结束。
2.根据权利要求1所述的影响力社区搜索方法,其特征在于,步骤(2)步骤中第i个节点pi的影响力值PageRank(pi)是采用以下公式获得:其中,N表示社交网络拓扑图中节点的总数,d表示阻尼系数,其取值为0.85,M(pi)表示第i个节点pi的所有邻居节点的集合,L(pj)表示第i个节点pj的邻居个数。
3.根据权利要求1所述的影响力社区搜索方法,其特征在于,步骤(4)包括以下子步骤:(4-1)根据步骤(3)更新后的社交网络拓扑图中各个节点的影响力值,获取最小影响力值对应的节点作为关键节点;
(4-2)针对步骤(4-1)中得到的关键节点,判断其数量是否为1,若为1,则过程结束,否则根据步骤(3)更新后的社交网络拓扑图判断这些节点之间的连通性,将彼此连通的节点合并为一个节点,从而完成对关键节点的更新。
4.根据权利要求1所述的影响力社区搜索方法,其特征在于,步骤(5)包括以下子步骤:(5-1)获取步骤(4)更新后的关键节点,并将其放入关键节点集合;
(5-2)在步骤(3)更新后的社交网络拓扑图中将该关键节点以及和它相连的边删除,从而得到二次更新后的社交网络拓扑图;
(5-3)从二次更新后的社交网络拓扑图中选择节点,获取其邻居个数,并判断其邻居的数量是否小于k,如果是则进入步骤(5-4),否则转入步骤(5-5);
(5-4)将该节点放入关键节点对应的候选节点集合,并从二次更新后的社交网络拓扑图中将该节点以及和它相连的边删除;
(5-5)重复上述步骤(5-1)至(5-4),直到二次更新后的社交网络拓扑图中的所有节点均被处理完毕为止。
5.根据权利要求1所述的影响力社区搜索方法,其特征在于,步骤(8)包括以下子步骤:(8-1)获取步骤(5)中得到的关键节点集合和关键节点集合中每个关键节点对应的候选点集合;
(8-2)选取关键节点集合中的一个节点和该节点对应的候选点集合,将这些节点在步骤(1)的社交网络拓扑图中对应的诱导子图作为影响力社区;
(8-3)从关键节点集合中删除该节点并删除该节点对应的候选节点集合;
(8-4)针对关键节点集合和对应候选集合中的剩余节点重复上述(8-1)至(8-3),直到两个集合都为空为止。
6.一种基于社区检索的影响力社区搜索系统,其特征在于,包括:
第一模块,用于获取社交网络拓扑图、需要搜索的社区数量r、以及社区中节点邻居个数的约束值k,该社交网络拓扑图中的每个节点代表一个用户实体,每条边代表两个用户实体之间的社交关系;
第二模块,用于从第一模块获取的社交网络拓扑图中确定每个节点的邻居个数和影响力值,从社区网络拓扑图中将邻居个数小于k的节点、以及与该节点相连的所有边删除,并将剩余的所有节点按照影响力值从大到小的顺序进行排列;
第三模块,用于根据第二模块的排列结果从社交网络拓扑图中删除影响力值小于阈值t的节点,从而形成更新后的社交网络拓扑图,其中阈值t的大小等于第二模块的排列结果中排在第(k+r)位的影响力值;
第四模块,用于针对第三模块更新后的社交网络拓扑图,根据其中各个节点的邻居个数和影响力值确定关键节点,选择其中影响力值相同的关键节点,并根据更新后的社交网络拓扑图对选择的关键节点进行更新;
第五模块,用于针对第四模块更新后的关键节点,所有关键节点构成关键节点集合,根据集合中的每一个关键节点和第三模块更新后的社交网络拓扑图中剩余节点的邻居个数确定该关键节点对应的候选节点,每一个关键节点对应的所有候选节点构成该关键节点对应的候选节点集合;
第六模块,用于获取第五模块得到的关键节点集合以及该关键节点集合中关键节点的数量m,判断m是否大于或等于需要搜索的社区数量r,如果是则进入第八模块,否则进入第七模块;
第七模块,用于将阈值t的值更新为其当前值的2/3,并返回第三模块;
第八模块,用于对第五模块更新后的关键节点集合中所有关键节点对应的候选节点集合进行处理,从而得到第一模块中社交网络拓扑图中的前r个影响力社区,过程结束。