一种社交网络中匿名用户身份的识别方法

摘要

本发明公开了一种社交网络中匿名用户身份的识别方法，特点是具体步骤如下：（1）将已知用户的社交网络中抽象成无向图；计算出目标节点Vi与其他任一节点Vj之间的最短路径，并进一步计算出表示该已知用户与目标用户的关系强度的用户权值；（2）将另一包含目标匿名用户的社交网络图抽象成无向图，利用深度优先搜索计算其他任一已知节点到起点节点的权值，利用深度优先搜索法分别计算起点节点与未知节点的权值平均值；（3）通过搜索权值平均值差距最小的两个节点，从而识别出已知用户社交网络中的目标用户即为另一包含目标匿名用户社交网络中的目标匿名用户，优点是不仅能够识别匿名用户身份，同时匹配的准确率高。

说明书

技术领域

本发明涉及社交网络中用户身份的识别方法，尤其是涉及一种社交网络中匿名用户身份的识别方法。

背景技术

在社交网络中存在着大量的用户，用户与用户之间的关联关系使得用户之间组成了一张巨大的社交网络。而现有的社交网络中用户身份的确认方法大部分都是匹配已知的用户账号，具体步骤为：（1）根据两个候选社交网络中的每个用户账号计算他们的关系环境评分；（2）将其中一个社交网络的每个账号与另一个社交网络账号进行匹配，通过计算好友亲密度和非好友疏远度结合用户环境评分得到各自的结果值；（3）对每个结果值进行排序；（4）选出得分最高的用户账号作为最终选中的用户。从结果来看，现有技术是建立在已知的用户和相应的属性值的基础上进行相应的评价值计算，这已经无法满足实现匹配匿名用户的需求，因为匿名用户的所有属性值是未知的，因此无法计入评价体系，就更加无法得到之后的评分结果值。

发明内容

本发明所要解决的技术问题是提供一种通过已知的社交网络中的账户匹配不同社交网络中的相应匿名账户，不仅能够识别匿名用户身份，同时匹配的准确率高的社交网络中匿名用户身份的识别方法。

本发明解决上述技术问题所采用的技术方案为：一种社交网络中匿名用户身份的识别方法，具体步骤如下：

（1）已知社交网络中用户权值计算

A．在已知用户的社交网络中，将用户作为具有属性的节点，用户与用户之间的关系作为节点与节点之间的边，将社交网络图抽象成无向图；

B．在无向图中，以目标节点Vi为起点，其他任一节点Vj为终点，通过Dijkstra算法计算出目标节点Vi与其他任一节点Vj之间的最短路径，计算最短路径上所有相邻节点的相似度；

C．若其他任一节点Vj与目标节点Vi直接相连，则以该两节点的相似度作为用户权值；若其他任一节点Vj与目标节点Vi不直接相连，则以该两节点最短路径上相邻两节点相似度的累乘作为该任一节点Vj与目标节点Vi的相似度，以该相似度作为用户权值；得到的用户权值表示该已知用户与目标用户的关系强度；

D．将计算得到的用户权值的节点以<目标节点Vi，已知节点Vj，权值>形式组成结果集输出，得到已知社交网络中各用户权值；

（2）包含目标匿名用户的社交网络中权值计算

A．在另一包含目标匿名用户的社交网络图中，将已知用户作为具有属性的已知节点，匿名用户作为未知属性的未知节点，用户与用户之间的关系作为节点与节点之间的边，将社交网络图抽象成无向图；

B．选取任意已知节点为起点节点Wi，对其他任一已知节点Wj进行深度优先搜索得到相应的权值，以<起点节点Wi，已知节点Wj，权值>形式组成结果集输出；

C．利用深度优先搜索法分别计算起点节点Wi到所有未知节点X的相应距离值，将所有距离值相加除以未知节点X的个数，得到起点节点Wi与未知节点的权值平均值，以<起点节点Wi，未知节点X，权值平均值>形式组成结果集输出；

（3）匿名用户输出

A．从步骤（2）B中的结果集中选取起点节点Wi属性与步骤（1）D中的结果集中已知节点Vj属性相同的各组，分别将各组<起点节点Wi，已知节点Wj，权值>中的权值除以<目标节点Vi，已知节点Vj，权值>中的权值，将各比值取平均值，以<起点节点Wi，目标节点Vi，权值平均值 >形式组成结果集输出；

B．将<起点节点Wi，目标节点Vi，权值平均值 >与步骤（2）C中得到的<起点节点Wi，未知节点X，权值平均值>进行比较，搜索权值平均值差距最小的两个节点，该目标节点Vi即为未知节点X，从而获得已知用户社交网络中的目标用户即为另一包含目标匿名用户社交网络中的目标匿名用户，其中i=1，2，3，…，n，j=1，2，3，…，n，i与j之和为无向图中所有节点个数。

步骤（2）中节点相似度具体计算方法如下：

从目标节点Vi到其他任一节点Vj，沿着最短路径的方向，以相邻两节点度数和减一的倒数作为相邻两节点间的相似度，计算得到的相似度表示两用户之间的关系强度；相邻节点相似度计算公式如下所示：

与现有技术相比，本发明的优点在于：本发明首次公开了一种社交网络中匿名用户身份的识别方法，该方法在匿名用户的在识别过程中主要经历了寻找最短路径，权值计算，匹配三个过程。

在寻找最短路径阶段，该方法采用了Dijkstra算法。利用该算法，可以得到两个节点之间的最短路径，在该节点的最短路径上经过的节点越多，相似度累乘之后的结果越小，权值越小。这表明了距离越远的节点之间对于身份识别的贡献也越小。

在相似度计算中主要分为两种情况:与目标节点直接相连的节点，与目标节点不直接相连的节点。其中与目标直接相连的节点，以目标节点与相邻节点度数和减一的倒数作为两者的相似度，并将该相似度作为相邻节点的权值。与目标节点不直接相邻的节点我们通过计算在两个节点之间的最短路径上，两两相邻节点的相似度，以这些相似度的累乘结果作为不相邻节点的权值。这样充分保证了节点度数越大，结果值越小，权值越小。在评价值准确的基础上，再利用深度优先遍历算法匹配得到的目标结果，可以保证最终匹配结果的准确率。

附图说明

图1为本发明实施例无向图。

具体实施方式

以下结合附图实施例对本发明作进一步详细描述。

具体实施例

一种社交网络中匿名用户身份的识别方法，具体步骤如下：

（1）已知社交网络中用户权值计算

A．在已知用户的社交网络中，将用户作为具有属性的节点，用户与用户之间的关系作为节点与节点之间的边，将社交网络图抽象成无向图；

B．在无向图中，以目标节点Vi为起点，其他任一节点Vj为终点，通过Dijkstra算法计算出目标节点Vi与其他任一节点Vj之间的最短路径，计算最短路径上所有相邻节点的相似度；具体计算方法如下：

从目标节点Vi到其他任一节点Vj，沿着最短路径的方向，以相邻两节点度数和减一的倒数作为相邻两节点间的相似度，计算得到的相似度表示两用户之间的关系强度；相邻节点相似度计算公式如下所示:

；

C．若其他任一节点Vj与目标节点Vi直接相连，则以该两节点的相似度作为用户权值；若其他任一节点Vj与目标节点Vi不直接相连，则以该两节点最短路径上相邻两节点相似度的累乘作为该任一节点Vj与目标节点Vi的相似度，以该相似度作为用户权值；得到的用户权值表示该已知用户与目标用户的关系强度；

例如以图1无向图为例说明节点之间相似度的计算：以A，B，G，F四个用户说明用户相似度算法：A用户与G用户之间不存在相互链接的路径，因此A,G相似度为0，则G的权值为0；A，B直接直接相连则相似度为1/(1+2-1)=1/2,则B的权值为1/2；A，F用户之间没有直接相连，但存在多条路径A→B→F,A→B→C→E→F多条路径。在众多的路径中选择由A到F之间最短的路径A→B→F。则A,B之间的相似度为1/(1+2-1)=1/2,而B,F之间的相似度为1/(3+4-1)=1/6，.则A，F之间的关系强度为(1/2)*(1/6) =1/12，F的权值为1/12；

D．将计算得到的用户权值的节点以<目标节点Vi，已知节点Vj，权值>形式组成结果集输出，得到已知社交网络中各用户权值；

（2）包含目标匿名用户的社交网络中权值计算

A．在另一包含目标匿名用户的社交网络图中，将已知用户作为具有属性的已知节点，匿名用户作为未知属性的未知节点，用户与用户之间的关系作为节点与节点之间的边，将社交网络图抽象成无向图；

B．选取任意已知节点为起点节点Wi，对其他任一已知节点Wj进行深度优先搜索得到相应的权值（权值计算方法同上述步骤（1）），以<起点节点Wi，已知节点Wj，权值>形式组成结果集输出；

C．利用深度优先搜索法分别计算起点节点Wi到所有未知节点X的相应距离值，将所有距离值相加除以未知节点X的个数，得到起点节点Wi与未知节点的权值平均值，以<起点节点Wi，未知节点X，权值平均值>形式组成结果集输出；

（3）匿名用户输出

A．从步骤（2）B中的结果集中选取起点节点Wi属性与步骤（1）D中的结果集中已知节点Vj属性相同的各组，分别将各组<起点节点Wi，已知节点Wj，权值>中的权值除以<目标节点Vi，已知节点Vj，权值>中的权值，将各比值取平均值，以<起点节点Wi，目标节点Vi，权值平均值 >形式组成结果集输出；

B．将<起点节点Wi，目标节点Vi，权值平均值 >与步骤（2）C中得到的<起点节点Wi，未知节点X，权值平均值>进行比较，搜索权值平均值差距最小的两个节点，该目标节点Vi即为未知节点X，从而获得已知用户社交网络中的目标用户即为另一包含目标匿名用户社交网络中的目标匿名用户，其中i=1，2，3，…，n，j=1，2，3，…，n，i与j之和为无向图中所有节点个数。

该方法在匿名用户的识别过程中不同节点所起到的作用不同，为了定量的描述不同节点在匿名用户识别工程中所作贡献大小，我们为每个节点赋予不同的权值。权值的大小反应了在后期识别工作中该节点贡献大小。而权值的大小主要受以下几方面的影响：与待识别的匿名用户的距离，节点度的数量(代表的是用户好友数量)，与待识别匿名用户的亲密程度等因素影响。在这些因素中，距离匿名用户越近，与匿名用户越亲密，在识别用户身份时起到的作用越大，相应的权值也就越大，而节点度的数量越大，在识别用户身份时贡献越小，权值也就越小。因此，该方法提出使用节点相似度算法来计算节点之间的相似度，并将相似度的值作为该节点的权值。在节点相似度算法中该方法用相邻节点度数和减一的倒数作为两节点的相似度，这保证了度数越大（朋友越多），节点相似度越低（权值越小）。并且使用累乘的结果作为不相邻节点的相似度，由于相似度均小于1，距离越远累乘越多，则相似度越小（权值越小）。这保证了距离越远的节点，贡献度也越小。所以说该算法充分的考虑到了节点度的问题以及节点与匿名用户距离的问题。真正实现了度数越大，距离越远节点的权值越小。在评价值准确的基础上，再利用深度优先遍历算法匹配得到的目标结果，可以保证最终匹配结果的准确率。

当然，上述说明并非对本发明的限制，本发明也并不限于上述举例。本技术领域的普通技术人员在本发明的实质范围内做出的变化、改型、添加或替换，也应属于本发明保护范围。