基于博弈理论的互联网虚拟空间用户可信度评价方法

摘要

本发明涉及一种基于博弈理论的互联网虚拟空间用户可信度评价方法，属于网络安全领域。本评价方法主要是：建立一个随机博弈模型，构建虚拟社会网络，引入用户于用户之间的交互关系影响因素：连接关系系数和语义关系系数，获取用户效用函数，再计算交互双方增益函数，求导确定纳什均衡，最后用叉乘法得到该结点的初始信用度。本方法充分采集数据信息，而计算机技术的高度精确性和准确逻辑判断能力可以代替人的一些费时费力的脑力劳动，使软件能够基于信息内容根据交互信息和语义信息自动得给每个用户可信度打分。

说明书

技术领域

本发明涉及一种基于博弈理论的互联网虚拟空间用户可信度评价方法，属于 网络安全领域。

背景技术

BBS是一个公共场所，用户彼此之间都不认识，因此可以自由地畅谈，由于 BBS很容易和方便地在世界各地被使用，并且能利用海量的通信背景为犯罪分子 提供掩护，因此成为对犯罪或恐怖组织最具吸引力的交流方式。利用信息抽取技 术可以鉴定犯罪团体，以及个体、组织和事件之间的关系。因此我们可以运用社 会网络分析方法，从BBS虚拟社会中抽取潜在犯罪网络。

一些新的技术已经应用到分析犯罪网络中。例如：COPLINK^{[1-3，10-13]}技术已 经应用到鉴定犯罪网络中的社团。还有，一些离散的或连续的马尔可夫模型被用 来在统计分析中预测未来的犯罪事件或过程^[4，5].，社会网络分析^[6，7]中的聚类、中 心度量方法、多维等级法和区块模型等方法被用来研究基于犯罪事件数据构建的 犯罪组织网络^[8，9]。一些可视化、自动的方法呈现了犯罪网络的演化过程^[8]。动态 社会网络分析方法被Daning Hu，Siddharth Kaza和Hsinchun Chen in用于到现 实社会中的麻醉毒品交易网络中，调查一些可疑的信息传输者^[11]。在这篇论文中， 我们结合社会网络和空间分析技术，研究社团之间的传输距离^[12].。近几年，针 对多种毒品运输和其他的潜在的市场运作方面的研究表示，潜在的网络具有一定 的灵活性，对执法机关的调查和干预也具有一定的弹性^[14]。

由于BBS是一个巨大的虚拟社会，每个用户都是一个潜在的犯罪者，用户之 间的交互关系通过发帖和回复建立，因此刑事调查人员希望通过这些线索获取每 个成员的潜在犯罪概率，以及用户之间的关系。这似乎听起来是一个不可能的任 务，因为调查人员必须花费大量的时间和精力搜索数据库，阅读犯罪报告，寻找 犯罪社团的线索，然后人工推断潜在犯罪网络里其他成员的犯罪概率。这些任务 都是既费时又费力的。

然而，目前还没有一项技术能够从BBS上抽取交互关系，并且自动地构建 潜在的犯罪网络。之前的相关研究^[13]借助已核实的部分信息并结合信念传播算法 来推断其他成员的犯罪概率。但是这些潜在的犯罪概率网络都是手工建立的。同 时，结点i的本地证据，以及结点i和结点j之间的相容函数都是随机产生的。 虽然实验结果证实了我们的假设，但是推广该方法还是有难度的。

发明内容

本发明所要解决的技术问题是针对上述背景技术的不足，提供了一种基于博 弈理论的互联网虚拟空间用户可信度评价方法，使软件能够根据互联网上用户的 交互信息和语义信息自动的给每个用户可信度打分。

本发明为实现上述发明目的采用如下技术方案：

基于博弈理论的互联网虚拟空间用户可信度评价方法包括如下步骤：

步骤1：建立一个随机博弈模型；

步骤2：构建虚拟社会网络；

步骤3：引入用户与用户之间的交互关系的两个影响因素：连接关系系数和 语义关系系数；

步骤4：获取用户效用函数；

步骤5：计算交互双方增益函数：

步骤6：对双方增益函数求导确定纳什均衡；

步骤7：评价用户信用等级，用叉乘法得到该结点的初始信用度。

所述基于博弈理论的互联网虚拟空间用户可信度评价方法，步骤1中的随机 博弈模型的建立如下：

定义三元组G＝[i，{A_i}，R_i]，其中玩家或用户集i＝{1，…，K}，用户i的可利用的 策略集A_i＝{C，L}，C表示犯罪分子，L表示合法者，用户i的效益函数

$R_i=\{U_i^{\mathrm{cc}},U_i^{\mathrm{cl}},U_i^{\mathrm{lc}},U_i^{\mathrm{ll}}\},$

其中，K为任意大于1的整数，表示当用户i和与用户i交互的用户都是犯罪 分子时用户i的效益函数，表示当用户i和与用户i交互的用户分别是犯罪分 子和合法者时用户i的效益函数，表示当用户i和与用户i交互的用户分别是 合法者和犯罪分子时用户i的效益函数，表示当用户i和与用户i交互的用户 都是合法者时用户i的效益函数。

所述基于博弈理论的互联网虚拟空间用户可信度评价方法，步骤2中的虚拟 社会网络包括：节点和边，

所述节点表示用户；

所述边表示它所连接的两个点有交互关系，即两个点代表的用户有交互关 系。

所述基于博弈理论的互联网虚拟空间用户可信度评价方法，步骤3中连接关 系系数和语义关系系数的定义如下：

M＝(t+1)·(e+1)        (1)

N＝(s+1)·λ           (2)

其中，M表示用户之间的连接关系系数，N表示用户之间的语义关系系数， t表示用户之间的共同回复关联度，e表示用户之间的相互回复关联度，s表示 用户之间语义关联度，λ表示用来均衡M和N的均衡因子。

所述基于博弈理论的互联网虚拟空间用户可信度评价方法，步骤4中效用函 数的定义如下：

h_i＝log₁₀(p_i·γ+r_i·τ) (3)

其中，σ表示犯罪分子之间的互益系数，δ表示合法用户之间的互益系数， p表示犯罪分子的语义系数，q表示合法用户的语义系数，α表示犯罪分子之间 的相对利益系数，β表示合法用户之间的相对利益系数，h_i表示用户i的活跃 度，p_i表示用户i的发帖数，r_i表示用户i的回复数，γ表示p_i的权值，τ表示r_i的 权值。

所述基于博弈理论的互联网虚拟空间用户可信度评价方法，步骤5中交互双 方增益函数的定义如下：

假设变量x、y分别为用户i、与用户i交互的用户的潜在犯罪概率，用户i的 增益函数如下：

$R_i(x,y)=U_i^{\mathrm{cc}}·x·y+U_i^{\mathrm{cl}}·x·(1-y)+U_i^{\mathrm{lc}}·(1-x)·y+U_i^{\mathrm{ll}}·(1-x)·(1-y)---\left(4\right)$

所述基于博弈理论的互联网虚拟空间用户可信度评价方法，步骤6中纳什均 衡的确定如下：用户i的增益函数对表示用户i潜在犯罪概率的变量求导，

k∈N(i)                (5)

其中，N(i)表示结点i的所有邻接结点，表示用户i在边e_ik上的分布概率。

所述基于博弈理论的互联网虚拟空间用户可信度评价系统，步骤7中节点出 初始可信度的确定如下：

${\phi }_i({ϵ}_i^c,{ϵ}_i^l)=(\frac{\underset{k\in N\left(i\right)}{\Pi }{\eta }_{x_{\mathrm{ik}}}}{\underset{k\in N\left(i\right)}{\Pi }{\eta }_{x_{\mathrm{ik}}}+\underset{k\in N\left(i\right)}{\Pi }(1-{\eta }_{x_{\mathrm{ik}}})},1-\frac{\underset{k\in N\left(i\right)}{\Pi }{\eta }_{x_{\mathrm{ik}}}}{\underset{k\in N\left(i\right)}{\Pi }{\eta }_{x_{\mathrm{ik}}}+\underset{k\in N\left(i\right)}{\Pi }(1-{\eta }_{x_{\mathrm{ik}}})})---\left(6\right)$

其中，N(i)表示结点i的所有邻接结点，表示用户i为犯罪分子的概率，表示 用户i为合法用户的概率。

本发明采用上述技术方案，具有以下有益效果：充分采集数据信息；计算机 技术的高度精确性和准确逻辑判断能力可以代替人的一些费时费力的脑力劳动； 使软件能够基于信息内容根据交互信息和语义信息自动得给每个用户可信度打 分。

附图说明

图1为两个用户之间随机博弈的示意图。

图2为结点叉乘得出事概率的示意图。

图3(a)为本发明所构建的原始潜在网络OPN。

图3(b)为本发明所构建的共同回复潜在网络TPN。

图3(c)为本发明所构建的共同回复潜在网络EPN。

图3(d)为本发明所构建的语义潜在网络SPN。

图3(e)为本发明所构建的k度原始潜在网络k-OPN。

图4(a)为每条边是纳什均衡。

图4(b)为节点1的相容函数。

图5为k-OPN中结点的初始概率的曲线图。

图6(a)为2003年的KPN，阈值k为20。

图6(b)为2003年的KPN，阈值k为10。

图7(a)为2003年数据样本一的本地证据。

图7(b)为2003年数据样本二的本地证据。

图中标号说明：

图1中，strategies表示策略集，criminal表示犯罪分子，legal表示合 法者，表示当用户A和用户B都是犯罪分子时用户A的效益函数，表示 当用户A和用户B分别是犯罪分子和合法者时用户A的效益函数，表示当用 户A和用户B分别是合法者和犯罪分子时用户A的效益函数，表示当用户A 和用户B都是合法者时用户A的效益函数，表示当用户A和用户B都是犯罪 分子时用户B的效益函数，当用户A和用户B分别是犯罪分子和合法者时用 户B的效益函数，表示当用户A和用户B分别是合法者和犯罪分子时用户B 的效益函数，表示当用户A和用户B都是合法者时用户B的效益函数。

图2中节点表示BBS上的用户，边表示两个结点之间发帖-回复的关系，图 2(a)、(b)、(c)中每条边上的数值表示两个结点之间的交互频率；图2(d)中， 每条边上的数值表示语义信息值；图2(e)中，每条边上标记是数值为连接关 系系数M和语义关系系数N的值，每个结点边的数据表示该结点的初始动机。

具体实施方式

下面结合附图对发明的技术方案进行详细说明：

从天涯论坛的国际观察板块采集2003年6月到2010年6月的数据，以此建 立数据库，其中包括了324666位用户，99735个主题，4712859条回复。数据库 中的用户都是在过去的八年中在国际观察板块发帖或回复份额成员。我们利用网 络爬虫程序下载网页的源代码，采集到的信息包括用户的姓名，主题id，主题 内容，回复内容，发帖日期和回复日期。我们利用正则表达式从网页源代码中抽 取关键信息。

基于博弈论的互联网虚拟空间用户可信度评价方法的实现如下：

步骤1：引入如如图1所示的博弈模型，两个玩家就是BBS上两个具有交互 关系的用户。他们在彼此都不认识，都在网上冲浪。他们不是被定义为犯罪分子 就是被定义为合法者。也就是A_i＝{C，L}。表示当用户A和用户B都是犯罪 分子时，用户A的效益函数。其他的可以以此类推。对用户k的效益函数可以表 示每个用户都知道，如果他们都选择成为合法用户，那 么每个人都会得到较高的增益(值100的效益)。如果两人都选择成为非法用户， 那么两个人都会得到增益(值为80的效益)。如果他们其中一人选择成为非法用 户，而选择另一个选择成为合法用户，那么非法用户会得到一个增益(值为20) 而另一个合法用户会得到较高的增益(值为50).由于两个用户分别来自世界的 不同地方并且彼此不认识，因此很难能够合作。在这个例子中，出于最大化支付 函数的自私策略，每个用户都会选择成为合法用户。很容易得到证实点(L，L)是 这场博弈中唯一的纳什均衡点，而且，这个均衡不是帕累托最优，因为选择(C，C) 对于两个玩家而言将产生更大的效益，然而这需要两个罪犯之间的合作。因此， 在这个例子中早个人理性很社会福利之间存在很明显的冲突。

如图2所示：由于在潜在网络中的结点拥有很多的邻接点，其本地证据会 被多个邻接结点所影响，因此该结点在某条边上的分布概率不能作为本地证据。 这里我们用叉乘得到该结点的初始概率，叉乘可能会扩大用户E的潜在犯罪概 率，这是允许的。因为我们研究的目的是帮助调查人员从大量数据中尽可能地找 到可疑者。尽管存在误差，但是这种方法从整体上看还是有效的。

步骤2：从数据库提取部分信息构建虚拟社会网络，包括如图1所示的原始 潜在网络(OPN)、共同回复潜在网络(TPN)、共同回复潜在网络(EPN)、语义潜 在网络(SPN)，

由于结点之间的关系很容易建立起来，因此在OPN中低权值的边没有参考价 值，因此引入了阈值，去除了权值小于k的边，如果某个结点的所有边都去除了， 那么该结点也将被移除。根据这种方法，构建了k度原始发帖-回复网络(k-OPN)， 如图1(e)所示，其中k＝1.连接类型和结点行为信息都可以从TPN，EPN和SPN 中提取；

步骤3：确定连接关系系数M和语义关系系数N：以边edge_1，6为例，边edge_1，6中，t_1，6＝0，e_1，6＝3，那么结合公式(1)得M_1，6＝(t_1，6+1)·(e_1，6+1)＝4。因为 所以N＝s_1，6·1.3≈9，其他边类似，

其中，计算的是平衡因子，avgt代表整个网络的平均共同回复系数；avg_e代表整个网络的相互回复系数；avg_abs(s)代表整个网络的语义系数绝对值的均数。

步骤4：确定效用函数：结点1的发帖数为20，回复数为245，结合公式(3) 得到h₁＝log₁₀(p₁·γ+r₁·κ)＝2.6484。定义γ为10，κ为1，根据相同的方法，我 们可以得到h₆＝2.1903，其他边类似。

$\left(\begin{array}{c}{U}_1^{\mathrm{cc}}=\sigma ·h_1·M_{\mathrm{1,6}}+p·N_{\mathrm{1,6}}=1\times 2.6484\times 4+0.5\times 9=15.0936\\ U_1^{\mathrm{cl}}=\alpha ·h_1·M_{\mathrm{1,6}}=0.2\times 2.6484\times 4=2.1187\\ U_1^{\mathrm{lc}}=\beta ·h_1·M_{\mathrm{1,6}}=0.3\times 2.6484\times 4=3.1781\\ U_1^{\mathrm{ll}}=\delta ·h_1·M_{\mathrm{1,6}}+q·N_{\mathrm{1,6}}=0.7\times 2.6484\times 4+1\times 9=16.4155\end{array}\right)$

$\left(\begin{array}{c}{U}_6^{\mathrm{cc}}=\sigma ·h_6·M_{\mathrm{1,6}}+p·N_{\mathrm{1,6}}=1\times 2.1903\times 4+0.5\times 9=13.2612\\ U_6^{\mathrm{cl}}=\alpha ·h_6·M_{\mathrm{1,6}}=0.2\times 2.1903\times 4=1.7522\\ U_6^{\mathrm{lc}}=\beta ·h_6·M_{\mathrm{1,6}}=0.3\times 2.1903\times 4=2.6284\\ U_6^{\mathrm{ll}}=\delta ·h_6·M_{\mathrm{1,6}}+q·N_{\mathrm{1,6}}=0.7\times 2.1903\times 4+1\times 9=15.1328\end{array}\right)$

k-OPN中结点的活跃系数如表1所示，其中，post-num表示发帖数，reply-num 表示回复数，liveness表示活跃系数。

  Node   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   Post num   20   2   2   4   5   8  ...   7   4   8   10   10   30   3   15   Reply-num   245   35   65   45   33   75  ...   55   25   85   145   100   95   65   145   liveness   2.65   1.74   193   193   1.92   2.19  ...   2.10   181   2.22   2.39   2.30   2.60   198   2.47

表1k-OPN中结点的活跃系数

步骤5：计算交互双方增益函数，假设变量x、y分别为用户1、与用户6 交互的用户的潜在犯罪概率，结合公式(4)得到用户1和用户6的增益函数：

$R_1(x,y)=U_1^{\mathrm{cc}}·x·y+U_1^{\mathrm{cl}}·x·(1-y)+U_1^{\mathrm{lc}}·(1-x)·y+U_1^{\mathrm{ll}}·(1-x)·(1-y)$

$R_6(x,y)=U_6^{\mathrm{cc}}·x·y+U_6^{\mathrm{cl}}·y·(1-x)+U_6^{\mathrm{lc}}·(1-y)·x+U_6^{\mathrm{ll}}·(1-x)·(1-y)$

步骤6：对增益函数求导确定纳什均衡，结合公式(5)得到：

${\eta }_{x_{\mathrm{1,6}}}=\frac{U_6^{\mathrm{cc}}-U_6^{\mathrm{lc}}}{U_6^{\mathrm{cc}}+U_6^{\mathrm{ll}}-U_6^{\mathrm{cl}}-U_6^{\mathrm{lc}}}=0.443,$${\eta }_{x_{\mathrm{6,1}}}=\frac{U_1^{\mathrm{cc}}-U_1^{\mathrm{lc}}}{U_1^{\mathrm{cc}}+U_1^{\mathrm{ll}}-U_1^{\mathrm{cl}}-U_1^{\mathrm{lc}}}=0.436$

同理可得其它边的纳什均衡。每条边的纳什均衡如图3(a)所示，同样的方 法的到节点1的相容函数，如图3(b)所示。

步骤7：算出各节点的初始概率。

将步骤4所得各值带入公式(6)

${\phi }_i({ϵ}_i^c,{ϵ}_i^l)=(\frac{\underset{k\in N\left(i\right)}{\Pi }{\eta }_{x_{\mathrm{ik}}}}{\underset{k\in N\left(i\right)}{\Pi }{\eta }_{x_{\mathrm{ik}}}+\underset{k\in N\left(i\right)}{\Pi }(1-{\eta }_{x_{\mathrm{ik}}})},1-\frac{\underset{k\in N\left(i\right)}{\Pi }{\eta }_{x_{\mathrm{ik}}}}{\underset{k\in N\left(i\right)}{\Pi }{\eta }_{x_{\mathrm{ik}}}+\underset{k\in N\left(i\right)}{\Pi }(1-{\eta }_{x_{\mathrm{ik}}})}),$得到k-OPN中结点 的初始概率。

最后，做一个仿真比较。从数据库中抽取2003年的数据，提取两个样本作 为研究。样本一中有105个用户，156条边，阈值k为20。样本二中包含了321 个用户，576条边，基于敏感分析的目的，我们把阈值k设为10。然后我们得到 了两个K-OPN。如图5(a)，在阈值k相对较小的情况下，构建网络是张稠密图。 根据博弈论原理，我们可以得到每个结点各自的本地证据，样本一和样本二的本 地证据如图6所示。

为了比较这两个样本的输出，我们利用显著性α＝0.05的卡方检验对结果进 行拟合度测试，确定用样本之间是否存在显著差异。当结点的犯罪概率大于0.75 时，我们认为该用户是犯罪分子。根据这条准则，我们在样本一中找到了6位犯 罪分子，在样本二中发现了41位犯罪分子。两个样本的实验结果显示在表3中。 根据结果，我们可以得到χ²＝4.02，v＝(2-1)(2-1)。查询卡方分布表，我们得 到当H₀＝0.05时，0.025＜P＜0.05。因此我们认为当潜在概率网络的规模大小不 一样时，他们的犯罪概率也存在着显著差异。卡方检验结果如表2所示：

表2卡方检验结果

为了对原始数据进行评估，我们邀请了南京警察局的相关专家到我们实 验室，他在执法岗位工作了上20年。他手工评估了样本一和样本二中每个 结点的犯罪概率和相容矩阵。假设我们运用算法找到了N个不同的个体，他 们的犯罪概率都大于0.75.我们也请该专家依据他的经验，选择相同数量的 个体。为了检测我们算法的有效性，我们定义一个精确率公式：

$\mathrm{precision}=\frac{{\Phi }_{\mathrm{expert}}\cap {\Phi }_{\mathrm{algorithm}}}{{\Phi }_{\mathrm{algorithm}}}\times 100\%$

其中Φ_exp ert是被专家选择出来的犯罪分子，Φ_alg orithm是根据我们的算法选择 出来的犯罪分子。结果显示Φ_exp ert几乎与Φ_alg orithm数目一样，我们算法的准 确率在样本一和样本二中分别达到了72.03％和63.87％。