在社会网络中实现社区发现的方法

摘要

本发明提供一种在社会网络中实现社区发现的方法，包括：对一社会网络中的任一节点，计算所述社会网络中的其他节点对该节点的依赖性，找出依赖性最大的k个节点作为该任一节点的k近邻；从所述社会网络中选取一个未经处理的节点，然后执行下一步，直到所述社会网络中的节点都已经被处理；判断所述未经处理的节点的k个最依赖的节点是否满足k社区要求，如果满足，输出该社区后重新执行前一步骤，如果不满足，从所述未经处理的节点的k个最依赖的节点所组成的集合中选取一个子集，对该子集继续做是否满足k社区要求的判断，直到找出满足k社区要求的社区或者所有子集都已经被尝试过，然后重新执行前一步骤。

主权项

1.一种在社会网络中实现社区发现的方法，包括：步骤1)、对一社会网络中的任一节点，计算所述社会网络中的其他节点对该节点的依赖性，找出依赖性最大的k个节点作为该任一节点的k近邻；其中，所述的计算所述社会网络中的其他节点对该节点的依赖性包括：步骤1-1)、对于每个节点v∈V(G)，计算其中，G表示图，表示节点v在网络G下的重要性取值；步骤1-2)、断开节点u的链接生成G_u，并计算步骤1-3)、计算节点v对节点u的依赖函数dep(v→u)；步骤2)、从所述社会网络中选取一个未经处理的节点，然后执行下一步，直到所述社会网络中的节点都已经被处理；步骤3)、判断所述未经处理的节点的k个最依赖的节点是否满足k社区要求，如果满足，输出该社区后重新执行步骤2)，如果不满足，从所述未经处理的节点的k个最依赖的节点所组成的集合中选取一个子集，对该子集继续做是否满足k社区要求的判断，直到找出满足k社区要求的社区或者所有子集都已经被尝试过，然后重新执行步骤2)；其中，所述的k社区要求包括将所述未经处理的节点的k个最依赖的节点依次判断是否为所述未经处理的节点的k近邻，当所有k个最依赖的节点都是k近邻时，即被认为是k社区。