社交网络已经成为人们生活中不可缺少的重要组成部分。当某人对特定个人或者群好友发布1条消息,如果他的好友有意或无意对该条消息进行转发,消息中的隐私信息就可能被泄露给未授权的用户。
在社交网络平台中,用户无论是以群分享还是以私密聊天的方式将信息发给好友时,都不希望出现未经允许的非法传播,但是在目前的社交网络中,很难制止这类非法传播。虽然信息的发布者可以通过设置传播对象,仅对指定的好友发布信息,然而由于目前社交网络普遍具有转发信息的功能,对接收信息的对象再次转发信息缺乏控制,从而导致信息发布者的信息存在被泄露的风险。
信息在社交网络传播过程中,如果能对信息传播过程中的用户节点进行预测,推测信息传播链中可能的泄露节点,就能发现隐私信息泄露节点。但由于收集隐私信息的非法用户往往与发布信息的用户之间不存在显式的社交关系,因此通常需要采用信任推断方法(搜索信任路径)来发现2个用户之间的信任关系,这样才能进一步预测泄露信息的用户。
常见的搜索信任路径的方法可以分为广度遍历以及深度遍历方法[1]。然而,在大规模的社交网络中,寻找一条可靠的信任路径来推断信任值非常耗时且难度很大。如何加快在社交网络中搜索非直连用户之间的信任路径的速度,并有效聚合出信任值,是一个研究难点。Kim等[2]指出,基于所有信任路径来评估目标用户的信任值,比仅仅基于最短路径来推断信任值更加准确。Shekarpour等[3]提出限制搜索深度或者限制搜索宽度,来加快信任路径的搜索。但是,这些策略会减少信任传播的覆盖范围,并且由于盲目去除信任路径,可能导致最可靠的路径丢失,使得基于信任的推理精度降低,而且这些方法仍相当耗时。对于信任路径搜索速度慢以及可靠路径丢失的问题,Fernández等[4]采用学习自动机成功地解决了路径最短的优化问题,加快了路径搜索速度;Moradabadi等[5]利用学习自动机,根据网络中的权值信息来估计每个测试连边的权值,降低了算法的时间复杂度;Ghavipour等[6]利用分布式学习自动机寻找信任路径,从而推断出2个间接连接用户的信任值。
同时,由于社交网络中的信息传播受到诸多因素影响[3],仅靠推断得到的信任关系并不足以预测泄露节点,还需要进一步推断信息传播过程中节点之间是否产生链路,这就需要进行链路预测。链路预测是描绘社会互动的一种有效方法[7]。在社交网络中,链路表示2个节点或用户之间任何类型的联系,比如评论、转发、关注和收藏等。目前,链路预测采用的方法通常基于网络结构相似性、概率模型和机器学习等[7]。Liben-Nowell等[8]首次提出了社交网络的链路预测问题,总结了多种基于网络拓扑结构的相似性指标,并验证了这些相似性指标在社交网络中的链路预测效果。Liu等[9]提出了一种与节点的度相关的聚类路径,这种方法使用共同近邻来预测链路关系。Muniz等[10]提出了结合全局相似性指标和基于内容测度的指标。然而,全局相似性指标在大型社交网络的背景下,由于指数维度较高,因此计算复杂而且费时。Fu等[11]利用线图的方式来描述社交网络结构,分别采用随机森林(random forest,RF)、支持向量机(support vector machine,SVM)、梯度上升决策树(gradient boosting decision tree,GBDT)算法来验证链路预测结果。然而,在信息传播过程当中,往往存在着多个节点对原始信息进行转发,信任的传递会受到这些转发节点的影响,使用机器学习的方式很难对此进行分类。因此,采用单一的链路预测方法难以满足预测要求。
可见,采用学习自动机可以在社交网络中很好地找到信任路径,但在大型社交网络中其计算量巨大,难以实际应用。在链路预测中,存在使用全局相似性指数进行链路预测计算成本高,而基于局部相似性指数预测准确度不够高的问题。为了解决上述问题,本文针对信息转发的线性传播和群传播模型,提出采用基于估计器的分布式学习自动机的信任推断(estimator based distributed learning automata for trust inference, EDLATrust)算法来计算非直连节点之间信任值,采用节点对特征和极端梯度提升算法(extreme gradient boosting, XGBoost)预测非直连节点对的链接关系,从而推断信息传播过程中可能的信息泄露节点。
1 分布式学习自动机与XGBoost算法 1.1 分布式学习自动机学习自动机[4]是一个在未知随机环境中进行自适应决策的抽象模型。对于一个目标函数,可使用学习自动机通过不断与随机环境进行交互来学习最优值。自动机的学习过程如下:学习自动机在每个瞬间,从一个有限的允许动作集中选择一个动作,该动作指导自动机与环境之间的交互。同时,自动机根据从环境中反馈的信号更新其动作概率分布,并通过迭代将需要被惩罚的动作降到最低,以收敛到最佳的动作。
本文采用收敛性更好的可变结构的学习自动机(variable structure learning automata, VSLA)。用四元组〈α, β, p, T 〉表示VSLA。其中:α={α1, α2, …, αr}代表了动作集合;β={β1, β2, …, βr}代表了从随机环境中得到反馈的反馈集合;p={p1, p2, …, pr}代表了对动作集合的奖惩概率集合;T表示下一个动作的更新策略,即p(t + 1)=T[α(t), β(t), p(t)]。r表示的是自动机可选择的动作上限。如果惩罚概率随时间变化,则随机环境称为非平稳环境,否则称为平稳环境。同时,根据反馈信号的有限性,如果反馈信号只取0和1两个二进制值则自动机模型称为P-模型,如果允许反馈信号在区间[0, 1]内取有限数量的值,则称为Q-模型。在本文中,由于节点的奖励概率分布不随时间变化,自动机为平稳环境,同时由于学习自动机的下一个动作需要在其众多邻居节点中选择,反馈信号在[0, 1]之间取值,因此自动机模型为Q-模型。
分布式学习自动机如图 1所示,它将各个自动机联合起来解决一个特定的问题。图 1中,Ai、Aj、Ak、Al分别表示单个学习自动机,αij、αil、αjk、αlk表示分布式学习自动机选择的动作。从源点Ai开始,可以激活Aj自动机也可以激活Al来到达目标点Ak。在社交网络的信任推断路径中,由于存在数量众多的节点,不能单一地使用一个学习自动机来搜寻到一条满足条件的最优路径,因此需要将这些节点分别作为一个个独立的自动机联合起来完成路径的搜索。分布式学习自动机用四元组〈A, E, T, A0〉表示。其中:A代表一系列自动机的集合,E⊂A×A代表自动机的一系列动作,T表示分布式学习自动机下一个动作的更新策略,A0表示将分布式学习自动机激活的根自动机。每次根自动机被激活时,它会根据相应动作的概率来选择一条边进行输出。被激活的自动机会随机选择一个动作来激活另一个自动机。该过程将重复进行,根据随机环境的响应,被激活的自动机会更新自己动作的概率,直到目标自动机被激活。
分布式学习自动机通过求解下一个动作的概率来选择下一个节点,
$ p_{i}(t+1)= \begin{cases}p_{i}(t)+\lambda\left[1-p_{i}(t)\right], & j=i; \\ (1-\lambda) p_{i}(t), & j \neq i.\end{cases} $ | (1) |
其中:i表示要奖励的自动机;j表示要惩罚的自动机;pi(t+1)表示选择第i个自动机的概率;t表示当前时刻;λ表示奖惩参数,在0~1之间。如果自动机的下一个动作是奖励则满足式(1)中j=i,如果下一个动作是惩罚则满足式(1)中j≠i。
1.2 XGBoost算法XGBoost[12]是由陈天奇等基于GBDT和RF算法提出的,因其出众的训练速度和准确率,在预测领域得到广泛应用。XGBoost属于Boosting算法,通常采用分类回归树(classification and regression tree,CART)集合,通过在损失函数中引入正则项来控制算法的复杂度,防止过拟合。
XGBoost的目标函数为
$ \mathrm{Obj}^{p}=\sum\limits_{i=1}^{q} l\left(y_{i}, \hat{y}_{i}^{p}\right)+\sum\limits_{j=1}^{p} \varOmega\left(f_{j}\right) . $ | (2) |
其中:Objp表示第p次迭代的目标函数;q表示样本数量;l()表示可微分的损失函数;Ω(f) 是正则化项,
$ \varOmega(f)=\gamma N+\frac{1}{2} \lambda \sum\limits_{k=1}^{N} \omega_{k}^{2}. $ | (3) |
其中:N为节点数,ω为每个节点的权重值,γ和λ是用来控制正则化程度的2个常数。第p次迭代的
$ \hat{y}_{i}^{p}=\hat{y}_{i}^{p-1}+f_{p}\left(x_{i}\right) . $ | (4) |
$ \begin{gathered} \mathrm{Obj}^{p}=\sum\limits_{i=1}^{q}\left[l\left(y_{i}, \hat{y}_{i}^{p-1}\right)+g_{i} f_{p}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{p}^{2}\left(x_{i}\right)\right]+ \\ \left(\gamma N+\frac{1}{2} \lambda \sum\limits_{j=1}^{N} \omega_{j}^{2}+C\right) . \end{gathered} $ | (5) |
其中:
对ωj求偏导,可以计算得到叶子节点j的最优权重ωj*,
$ \omega_{j}^{*}=-\frac{g_{j}}{h_{j}+\lambda}. $ | (6) |
社交网络是由个人或组织组成的社会结构,是复杂网络的一种。一个社交网络图可表示为G(V, H), 一个有权无向社交网络的拓扑结构如图 2所示。图中:圆圈表示用户,又称为节点,v∈V;直线表示用户间的好友关系,又称边,h∈H;节点vi与节点vj之间的关系(如信任关系)可以用权重wij来表示。
![]() |
图 2 社交网络拓扑图 |
一个社交网络可以用权重矩阵来量化。定义权重矩阵为W,如式(7)所示。矩阵中的元素值既可以表示社交网络边的权重大小,也可以表示整个社交网络的连接关系。比如,wij=0表示节点vi与vj不存在关系,反之则表示vi与vj存在关系,关系大小为wij。
$ \boldsymbol{W}=\left[\begin{array}{ccc} w_{01} & \cdots & w_{0 j} \\ \vdots & & \vdots \\ w_{i 1} & \cdots & w_{i j} \end{array}\right]. $ | (7) |
考虑到在社交网络的信息传播中,信息M由某一节点发布,最终经过传播路径达到若干节点。定义信息传播过程有4种节点:源节点S(source node)是信息M发布的源头;风险节点R(risk node)是经过直接或间接转发获得信息M的节点;观察节点O(observation node)是指不应获得信息M,但却被观察到拥有信息M的节点;邻居节点N(neighbor node)是指与节点直连的好友节点。通常,当用户在观察节点O发现信息M时,意味着信息M由某个风险节点R发生了泄露,该风险节点成为泄露节点。
2.3 社交网络中源节点信息的发布方式社交网络中从源节点S发出的信息M通常有3种权限属性,即全部好友可见、部分好友可见、特定个人可见,这3类消息分别记为Mpublic、Mprivate、Mspecial。其中:全部好友可见属于公共信息,转发或者分享不会造成信息泄露;部分好友可见、特定个人可见属于私密信息共享,在转发或者分享中可能会造成信息的泄露。本文将主要针对一个有权无向网络中,这2种信息传播方式中的泄露问题进行研究。
2.4 信息传播方式当信息M以特定个人可见(Mspecial)的方式传播时,定义这种信息传播方式为线性传播;当信息M以部分好友可见(Mprivate)的方式传播时,定义为群传播;当信息M以这2种方式传播时,称为混合传播方式。混合传播方式由线性传播和群传播方式组成。
2.4.1 线性传播方式图 3给出了线性传播方式示意图。源节点S发出的信息M,按传播属性,应在R1、R2、R3之间均按Mspecial形式进行传播,传播方向用红色箭头表示。
![]() |
图 3 信息的线性传播方式(红色节点R1表示泄露节点,黄色节点S表示信息源,绿色节点O表示观察点) |
当由于某种原因,信息M在R1节点处发生泄露,信息以Mspecial形式被逐节点传播到N4、N5和O节点,观察者在O节点发现信息M。这种情况意味着从源节点S发出的信息M被R1泄露,并传播到了观察节点O。
2.4.2 群传播方式图 4给出了群传播方式示意图。源节点S发出的信息M,按传播属性,应以Mprivate形式传播给R1—R4,传播方向用红色箭头表示。
![]() |
图 4 信息的群传播方式(红色节点R1表示泄露节点,黄色节点S表示信息源,绿色节点O表示观察点) |
当由于某种原因,信息M在R1节点处发生泄露,信息以Mprivate形式被传播到O1、O2和O3节点,观察者在这3个观察节点都发现信息M。这种情况意味着从源节点S发出的信息M被R1泄露,并传播到了观察节点O1、O2和O3,传播过程用红色箭头表示。
3 基于EDLATrust的非直连节点信任推断在社交网络中,信任是一个重要的概念,它极大地影响着用户的决策。人们通常依据信任度来决定与他人互动的程度。在一个社交网络中,即使2个用户之间没有连接关系,但通过社交网络关系网,至少存在1条路径,一个用户仍然可以信任另一个用户。比如,甲信任乙,乙信任丙,那么甲也将信任丙。在这样的信任传递过程中,所构成的传播路径即是信任路径。
信任推断是指在社交网络的非直连用户对之间,通过发现信任路径推断出节点对之间的信任值。为了推断2个非直连用户之间的信任关系,通常采用信任推断算法[2]。信任推断算法中有2个重要的因素:信任路径和聚合方法。目前,信任推断常用的方法有信任直接传递、信任转置传递、信任聚合等[13]。
信任推断过程往往通过搜索用户之间的信任路径来进行。对于信任路径搜索速度慢、准确性低等问题,可以采用分布式学习自动机算法[14],它在不考虑任何搜索约束的情况下,可以智能地去除不可靠的路径以及不能到达终点用户的路径。这样,由于保留了可计算的剩余路径,既保持了算法的预测覆盖率,又降低了算法的时间复杂度。
然而,学习自动机的准确率和收敛速度不能相互统一,拥有较大学习步长的学习自动机可以带来更快的收敛速度,但却会降低准确率;而学习步长较小的自动机虽然准确率较高,但收敛速度慢。估计器是帮助解决此类问题的有效方法,本文提出了基于估计器的分布式学习自动机。
3.1 基于估计器的分布式学习自动机估计器是指自动机与外部随机环境之间交互后动作选择的评估函数。估计器中存储的信息可以看作是学习自动机与外部随机环境的历史交互经验,经量化后可以被用来有效地促进学习自动机的收敛。本文提出采用基于确定性置信区间(upper confidence bound, UCB)[15]估计器的分布式学习自动机(estimator based distributed learning automata, EDLA),以加快分布式学习自动机收敛速度和提高算法的准确率。
UCB采用强化学习中乐观估计的方式,将置信区间的上界当作对行为奖励概率的估计值,反映在当前置信度下,奖励概率可能到达的上限。UCB估计器可以将估计值控制在1个可控的随机扰动中,并且不用人为地进行参数设置。
估计器用d(t)来表示,
$ d_{i}(t)=\left\{1+\frac{Z_{i}(t)-W_{i}(t)}{\left(W_{i}(t)+1\right) F_{2\left(W_{i}(t)+1\right), 2\left(Z_{i}(t)-W_{i}(t)\right), 0.005}}\right\}^{-1}. $ | (8) |
其中:i表示选择奖励的学习自动机,t表示当前时刻,Zi是动作αi被选择的次数,Wi是αi 得到奖励的次数,F2(Wi(t)+1), 2(Zi(t)-Wi(t)), 0.005是F分布2(Wi(t)+1)和2(Zi(t)-Wi(t))维自由度的0.005右尾概率。
采用UCB,EDLA根据式(9)和(10)选择下一个节点:
$ p_{j}(t+1)=\max \left\{p_{j}(t)-\varDelta, 0\right\}, $ | (9) |
$ p_{M}(t+1)=1-\sum\limits_{j \neq M} p_{j}(t+1) . $ | (10) |
其中:j表示要惩罚的自动机,pj表示要奖励的动作的概率,pM表示要惩罚的动作的概率。
$ \begin{gathered} W_{i}(t+1)=W_{i}(t)+\beta(t), \\ Z_{i}(t+1)=Z_{i}(t)+1 . \end{gathered} $ | (11) |
$ d_{i}(t+1)=\frac{W_{i}(t+1)}{Z_{i}(t+1)} . $ | (12) |
对所有j≠i:
$ W_{j}(t+1)=W_{j}(t), Z_{j}(t+1)=Z_{j}(t). $ | (13) |
$ d_{j}(t+1)=d_{j}(t) . $ | (14) |
$ d_{M}(t)=\max \left\{d_{i}(t)\right\} . $ | (15) |
Wi(t+1)是下一次动作αi得到奖励的次数,β(t)表示t时刻的反馈,Zi(t+1)是动作αi下一次被选择的次数,di(t+1)是下一次动作αi的估计值。
3.2 信任聚合函数在社交网络的信息传播链路上,各个节点对之间的信任值,除了受到链路中上一个节点的影响,还受到其邻居节点的影响。信任聚合函数可以将来自于链路中多个节点的信息进行聚合,从而得到节点对之间的信任值。根据邻居节点的性质,信任聚合函数可以分为2种[16]:
1) CFAvg聚合方式。当某节点不受极端邻居节点(该节点的邻居数量特别多或者大部分邻居对该节点都极度信任或者不信任)的影响时,采用CFAvg聚合方式,节点对之间的信任值为
$ \operatorname{trust}_{B E}=\overline{\operatorname{trust}}_{B}+\frac{\sum\limits_{v_{m} \in \mathrm{Nei}_{E}} W_{m}\left(\operatorname{trust}_{m E}-\overline{\operatorname{trust}}_{m}\right)}{\sum\limits_{v_{m} \in \mathrm{Nei}_{E}} W_{m}} . $ | (16) |
其中:B表示起始点;E表示终止点;vm表示B的一个邻居节点,m表示邻居节点编号;trustBE表示起始点B与终止点E之间的信任值;
2) MCAvg聚合方式。当某节点受到极端邻居节点的影响,采用MCAvg聚合方式,节点对之间的信任值为
$ \operatorname{trust}_{B E}=\overline{\operatorname{trust}}_{B}+\frac{\sum\limits_{v_{m} \in \mathrm{Nei}_{E}} W_{m}\left(\text { trust}_{m E}-\overline{\text { trust}}_{m}\right)}{\left|\mathrm{Nei}_{E}\right| \max _{\text {trust }}} . $ | (17) |
其中:|Neik|表示邻居节点数量,maxtrust表示所有trustmE的最大值。
3.3 EDLATrust评估预测算法假设源节点S、风险节点R及观察节点O之间的信息传播模型是已知的,但观察节点O和风险节点R之间的连接关系及信任情况(信任值)未知。为了从观察节点O溯源信息泄露的风险节点R,根据社交网络信息传播模型,首先需要推断非直连节点(风险节点R和观察节点O)之间的信任值,进而预测O与R之间的链接关系。如果某个风险节点R和观察节点O之间的连接概率最大,则认为该风险节点R成为泄露节点的概率最大。
为了推断非直连节点之间的信任值,本文提出EDLATrust信任值推断算法。该算法采用基于估计器的EDLA寻找社交网络上2个非直连节点之间的信息传播路径;基于该路径,采用聚合函数计算观察节点和风险节点之间的信任值。图 5给出EDLATrust信任推断算法的原理图。
![]() |
图 5 采用EDLATrust对信任值进行推断的原理图 |
在EDLATrust算法中,输入信息为传播链路上一非直连节点对,采用基于估计器的分布式学习自动机寻找信任值推断路径。其中,分布式学习自动机路径推断中,节点的选择依赖于外部随机环境。估计器中存储有学习自动机与外部随机环境的历史交互经验信息,经量化后指导学习自动机下一个路径的选择,直至最终找到一条满足条件的路径。基于该路径,由信任聚合函数推断得到非直连节点对之间的信任值。
4 基于节点对特征和XGBoost算法的节点链路关系预测 4.1 节点对特征信息在社交网络里以转发的形式传播,若采用共同邻居(common neighbors, CN)指数、Salton(SA)指数、Jaccard(JAC)指数、中心提升指数(hub promoted index, HPI)等基于公共邻居的相似性作为节点连通关系预测的特征,存在一定局限性。因为仅利用公共邻居的相似性特征,往往不能有效地判断两个非直连节点间的信息传播关系。
为了进一步描述节点之间的信任转发状态,本文基于信息传播模型,结合文[16]提出3个节点对特征:节点间的吸引程度F、平均信任程度TW和邻居数量程度KT。其中:特征F表示两节点之间的吸引程度,F值越高,表示两节点越有可能产生链接关系;特征TW表示某一节点对其周围邻居节点的信任值的影响,TW值越低,代表影响越小,信息易从该节点泄露;特征KT表示起始节点与终止节点对其邻居的平均信任程度,KT值越小,代表平均信任程度低,信息易从该节点对泄露。
3个特征的定义如式(18)—(20)所示:
$ F=\frac{\operatorname{trust}_{B E} \cdot k_{B} \cdot k_{E}}{\operatorname{len}_{B E}+1} $ | (18) |
$ \mathrm{TW}=\sum\limits_{m \in \mathrm{Nei}_{B}} \operatorname{trust}_{B E} \cdot W_{m}+\lg \frac{\overline{\operatorname{trust}}_{B}}{10-\overline{\operatorname{trust}}_{B}} . $ | (19) |
$ \mathrm{KT}=\frac{2}{2+\mathrm{e}^{-\frac{\text { trust}_{B E}}{k_{B}}}+\mathrm{e}^{-\frac{\text { trust}_{B E}}{k_{E}}}} \text {. } $ | (20) |
其中:k表示度,即当前节点的邻居节点的数量;lenBE表示起始节点和终止节点之间的信任路径长度;Wm表示起始节点对邻居节点m的信任权重;
基于EDLATrust推断非直连节点对R-O间的信任值和节点对特征,采用XGBoost算法预测R-O节点对存在链路的概率,从而找到链路中最有可能成为泄露节点的风险节点,即链路中概率最大的点。
基于节点对特征和XGBoost算法进行节点链路关系预测(泄露节点预测)的模型的训练流程如图 6a所示,预测流程如图 6b所示。
![]() |
图 6 基于节点对特征和XGBoost算法的节点链路关系预测流程图 |
5 EDLATrust算法描述
EDLATrust算法如图 7所示,泄露节点预测算法如图 8所示。
![]() |
图 7 EDLATrust算法 |
![]() |
图 8 泄露节点概率预测算法 |
6 实验与结果
本文仿真实验在Python 3.7中进行。计算机操作系统为Windows 10,CPU为Core i7-8750H,内存为8.0 GB。为证明泄露节点预测的有效性,进行了4个实验来验证所改进的基于估计器的分布式学习自动机的性能和所提出信息传播模型对信息泄露源进行预测的有效性。实验结果均是10次独立实验后求取的平均值。
6.1 数据集描述实验采用真实网络数据集Epinions、Facebook、MovieLens。其中:Epinions数据集(http://www.trustlet.org/wiki/Epinions_datasets) 是评估信任推断的常用数据集之一,Facebook数据集(http://snap.stanford.edu/data/ego-Facebook.html)是从Facebook应用程序的参与者中收集得到的,MovieLens数据集(https://grouplens.org/datasets/movielens/)是GroupLens研究组在美国明尼苏达大学收集得到的。后两个数据集用于对比实验。这3个数据集都包含了用户之间真实的信任值和用户之间的连接关系。从3个数据集中分别随机采取1 000个用户及其10 000条边进行实验。
6.2 评价指标为了评估EDLATrust信任值推断精度和XGBoost预测精度,采用以下4个指标:
1) 平均绝对误差MAE。
$ \mathrm{MAE}=\frac{\sum\limits_{e_{i j} \in V^{\prime}}\left|\tau_{i j}^{\prime}-\tau_{i j}\right|}{\left|V^{\prime}\right|}. $ | (21) |
其中:V′表示非直连节点对集合,|V′|表示非直连节点对的数量,τ'ij表示EDLATrust算法得到的节点对之间信任度的估计值,τij是实际估计值。
2) 精度Precision,在实验4中表示查准率。
$ \text { Precision }=\frac{\mathrm{TP}}{\mathrm{TP}+\mathrm{FP}}. $ | (22) |
其中:TP表示正确分类的正样本数量,FP表示错误分类的正样本数量。
3) 召回率Recall,在实验4中表示查全率。
$ \text { Recall }=\frac{\mathrm{TP}}{\mathrm{TP}+\mathrm{FN}}. $ | (23) |
其中FN表示错误分类的负样本数量。
4) Fscore。Fscore为精度Precision和召回率Recall之间的调和平均数,
$ \text { Fscore }=\frac{2 \times \text { Recall } \times \text { Precision }}{\text { Recall }+\text { Preciosin }}. $ | (24) |
本实验用于寻找分布式学习自动机的分辨率参数n和估计器初始化次数num。为保证算法在精度高的条件下,迭代次数较少,实验输入权重矩阵和非直连节点对。通过控制变量法,设初始参数n=30,num=50,分别改变参数大小对算法进行测试。实验采用Epinions数据集,聚合函数采用MCAvg。实验结果见表 1和2。
n | MAE | Precision | Recall | Fscore |
30 | 0.142 | 0.738 | 0.689 | 0.713 |
40 | 0.143 | 0.708 | 0.723 | 0.739 |
50 | 0.141 | 0.808 | 0.841 | 0.824 |
60 | 0.137 | 0.745 | 0.761 | 0.753 |
70 | 0.131 | 0.761 | 0.761 | 0.761 |
100 | 0.138 | 0.740 | 0.661 | 0.698 |
num | MAE | Precision | Recall | Fscore |
10 | 0.150 | 0.755 | 0.673 | 0.712 |
20 | 0.156 | 0.691 | 0.717 | 0.717 |
30 | 0.137 | 0.813 | 0.830 | 0.821 |
40 | 0.152 | 0.745 | 0.761 | 0.753 |
50 | 0.141 | 0.824 | 0.737 | 0.778 |
60 | 0.147 | 0.706 | 0.783 | 0.742 |
从表 1中可以看到,当参数n=50时,MAE为0.141,但此时Precision、Recall与Fscore都最大,分别为0.808,0.841,0.824。从表 2中可以看到,当估计器的初始化次数num=30时,MAE最小为0.137,并且此时Precision、Recall、Fscore都为最大,分别达到了0.813、0.830、0.821。因此,在选择参数n=50、num=30的情况下,分布式学习自动机能够达到最好的性能。
6.3.2 实验2为了验证所改进的基于估计器的分布式学习自动机的性能,将本实验将所提算法与文[6]中的DLA-CFAvg和DLA-MCAvg算法进行对比。实验在Epinions数据集上进行,输入所有非直连节点,对比不同聚合函数下DLA和EDLA算法的性能,实验结果见表 3和4。其中,平均收敛次数是指10次实验下的收敛次数的平均值。
Precision | Recall | Fscore | 平均收敛次数 | |
EDLA-CFAvg | 0.765 | 0.684 | 0.722 | 10.412 |
DLA-CFAvg | 0.714 | 0.634 | 0.672 | 27.350 |
Precision | Recall | Fscore | 平均收敛次数 | |
EDLA-MCAvg | 0.884 | 0.809 | 0.844 | 19.093 |
DLA-MCAvg | 0.857 | 0.732 | 0.722 | 29.946 |
从表 3可见,EDLA-CFAvg的Precision,Recall和Fscore分别比DLA-CFAvg提升7.06%、7.95%、7.53%,同时平均收敛次数下降61.93%。从表 4可见,EDLA-MCAvg算法的Precision、Recall、Fscore比DLA-MCAvg分别提升了3.10%、10.50%、17.03%,平均收敛次数下降36.24%。与原始DLA算法相比,EDLA算法得到的信任值精度提高,加入UCB估计器后,收敛速度更快。
为了进一步说明不同传播路径长度对EDLA-CFAvg与EDLA-MCAvg算法的影响,实验对比不同传播路径长度下的算法性能。在此实验中信息传播链长度的范围为2~6,实验结果如图 9所示。从图 9a、9b、9c中可以看到,改进的EDLA-CFAvg和EDLA-MCAvg算法在2到6次转发下的Precision、Recall、Fscore大部分优于DLA-CFAvg和DLA-MCAvg算法,并且EDLA-MCAvg算法在4、5次转发下的Precision、Recall、Fscore都最佳,因此EDLATrust算法采用MCAvg聚合函数的准确性最高。
![]() |
图 9 在不同转发链的长度下各个算法之间的性能比较 |
此外,从图 9d中可以看出,改进算法的平均收敛次数大幅小于原始算法,并且受转发次数的影响较小。总体而言,改进的EDLA-CFAvg和EDLA-MCAvg算法在不同长度的信息转发链上的性能更好。
6.3.3 实验3为了验证链路预测算法的有效性,本实验将XGBoost与CatBoost、LightGBM算法进行比较。实验在Epinions数据集上进行,特征采用F、TW、KT,进行10次独立实验,预测结果如图 10所示。
![]() |
图 10 不同分类算法的预测结果对比 |
从图 10中可以看到,XGBoost算法的Precision、Recall、Fscore都最高,分别为0.960、0.897、0.929。可见,在进行预测时,选择XGBoost算法是合理的。
6.3.4 实验4为了验证所提EDLATrust算法的有效性,本实验在3个不同数据集Epinions、Facebook、MovieLen下,对EDLATrust算法与TidalTrust[17]、GFTrust[18]、DLATrust[6]算法进行比较。
从表 5—7中可以看出,在3个数据集下EDLATrust推断算法的Precision、Recall和Fscore都是最高的,可见所提EDLATrust算法是有效的。
算法 | Epinions | MovieLen | |
TidalTrust | 0.615 | 0.622 | 0.522 |
GFTrust | 0.867 | 0.500 | 0.846 |
DLATrust | 0.857 | 0.871 | 0.896 |
EDLATrust | 0.884 | 0.891 | 0.955 |
算法 | Epinions | MovieLen | |
TidalTrust | 0.800 | 0.548 | 0.521 |
GFTrust | 0.700 | 0.870 | 0.786 |
DLATrust | 0.732 | 0.831 | 0.724 |
EDLATrust | 0.809 | 0.934 | 0.700 |
算法 | Epinions | MovieLen | |
TidalTrust | 0.695 | 0.582 | 0.521 |
GFTrust | 0.774 | 0.635 | 0.815 |
DLATrust | 0.722 | 0.850 | 0.800 |
EDLATrust | 0.844 | 0.912 | 0.808 |
6.3.5 实验5
为了进一步验证所提F、TW和KT特征的普遍有效性,本实验在3个不同数据集Epinions、Facebook、MovieLen下,将所提特征与传统CN、SA、JAC、HDI、Leicht-Holme-Newman (LHN)指数、Adamic-Adar (AA)指数特征进行对比。实验采用XGBoost算法进行预测,结果见表 8—10。
特征 | Epinions | MovieLen | |
CN | 0.600 | 0.684 | 0.795 |
SA | 0.766 | 0.790 | 0.714 |
JAC | 0.746 | 0.737 | 0.633 |
HDI | 0.825 | 0.740 | 0.714 |
LHN | 0.675 | 0.632 | 0.795 |
AA | 0.667 | 0.842 | 0.837 |
本文特征 | 0.970 | 0.937 | 0.900 |
特征 | Epinions | MovieLen | |
CN | 0.164 | 0.329 | 0.365 |
SA | 0.790 | 0.236 | 0.278 |
JAC | 0.672 | 0.763 | 0.489 |
HDI | 0.727 | 0.466 | 0.493 |
LHN | 0.648 | 0.521 | 0.540 |
AA | 0.593 | 0.356 | 0.508 |
本文特征 | 0.891 | 0.776 | 0.793 |
特征 | Epinions | MovieLen | |
CN | 0.258 | 0.444 | 0.560 |
SA | 0.778 | 0.364 | 0.400 |
JAC | 0.707 | 0.750 | 0.552 |
HDI | 0.773 | 0.572 | 0.583 |
LHN | 0.661 | 0.571 | 0.643 |
AA | 0.628 | 0.500 | 0.632 |
本文特征 | 0.929 | 0.849 | 0.843 |
从表 8—10中可以看到,由于CN、SA、JAC、HDI、LHN、AA特征需要依赖共同邻居来判断非直连节点之间的信任关系,但在信任传播模型中,共同邻居并不是判断其信任关系的关键因素。因此,采用这些特征作为预测特征时,在3个数据集Epinions、Facebook、MovieLen下Precision、Recall和Fscore都在0.7以下。
采用本文所提特征,Precision、Recall与Fscore都大于0.8,说明根据这些特征能够更准确地进行信任关系推断,在不同数据集下的结果也表明了本文所提特征具有良好的通用性。
6.3.6 实验6为了验证在2种信息传播模型中,所提的信息泄露源预测算法的有效性,本实验基于Epinions、Facebook、MovieLen数据集,通过随机选取信息源,然后根据信息传播模型形成信息传播链。其中,传播链上的非源节点表示为风险节点R。由于原数据集中没有给出观察节点,实验首先模拟选取最有可能成为观察节点的节点。设观察节点具有属性(k, val)。k表示观察节点的度,即当前节点的邻居节点的数量;val表示当前节点对其他邻居的平均信任值,即其邻居节点的平均信任值。为了满足度越大信息越容易泄露以及平均信任值越低信息越容易泄露这2条基本假设,实验首先选择k在11~50范围内,且val在1~2.5之间,数量为50的节点作为观察节点,然后应用XGBoost算法,分别计算R-O节点对新特征并作为输入,预测与观察节点产生最大概率的风险节点,即为最可能的信息泄露节点。
线性传播模型下泄露节点预测结果如表 11—13所示。其中NR表示节点R的数目。
NR | Epinions | MovieLen | |
1 | 1.000 | 0.991 | 0.929 |
2 | 0.889 | 0.991 | 0.895 |
3 | 0.842 | 0.981 | 0.901 |
4 | 0.739 | 0.969 | 0.896 |
5 | 0.731 | 0.956 | 0.860 |
6 | 0.724 | 0.949 | 0.855 |
NR | Epinions | MovieLen | |
1 | 0.833 | 0.828 | 0.824 |
2 | 0.800 | 0.809 | 0.790 |
3 | 0.842 | 0.805 | 0.762 |
4 | 0.739 | 0.787 | 0.797 |
5 | 0.760 | 0.746 | 0.659 |
6 | 0.750 | 0.664 | 0.481 |
NR | Epinions | MovieLen | |
1 | 0.909 | 0.902 | 0.873 |
2 | 0.842 | 0.890 | 0.839 |
3 | 0.842 | 0.884 | 0.825 |
4 | 0.739 | 0.869 | 0.759 |
5 | 0.760 | 0.838 | 0.746 |
6 | 0.737 | 0.781 | 0.616 |
从表 11、12中可以看到,在线性传播模型下,随着整个信息传播链中的风险节点R数目的增加,Precision和Recall都呈现下降趋势。其中NR在1~3的范围内,该预测算法的Precision以及Recall比较高,NR在3~6的范围内,Fscore下降幅度明显,相较于NR=3,在3个数据集下的降幅分别达到了12.47%、11.65%、25.33%。
好友数量 | Epinions | MovieLen | |
1~5 | 1.000 | 0.960 | 0.859 |
6~10 | 0.867 | 0.951 | 0.833 |
11~15 | 0.813 | 0.935 | 0.808 |
16~20 | 0.700 | 0.937 | 0.769 |
21~25 | 0.696 | 0.914 | 0.588 |
25以上 | 0.692 | 0.900 | 0.341 |
好友数量 | Epinions | MovieLen | |
1~5 | 0.818 | 0.805 | 0.933 |
6~10 | 0.765 | 0.782 | 0.928 |
11~15 | 0.722 | 0.765 | 0.909 |
16~20 | 0.700 | 0.720 | 0.857 |
21~25 | 0.727 | 0.441 | 0.767 |
25以上 | 0.720 | 0.450 | 0.667 |
好友数量 | Epinions | MovieLen | |
1~5 | 0.900 | 0.875 | 0.894 |
6~10 | 0.813 | 0.858 | 0.878 |
11~15 | 0.765 | 0.842 | 0.855 |
16~20 | 0.700 | 0.814 | 0.833 |
21~25 | 0.698 | 0.594 | 0.665 |
25以上 | 0.706 | 0.600 | 0.451 |
从表 14—16中可以看到,在群传播模型下,Precision和Recall随着好友数量的增加而下降。在群好友数量1~5的范围内,Epinions、Facebook和MovieLen 3个数据集下,Precision分别为1、0.960、0.859,预测效果最好。当群好友数量在6~15个之内,该预测算法仍有较好的预测效果。好友数量超过15个之后,3个数据集下的Fscore分别降到0.700、0.814、0.833左右,特别在Epinions数据集中降幅明显,好友数量在1~20范围内降幅达到了22.22%。
综上所述,在线性传播模型中传播链的长度在4以内,或者在群传播模型中群好友数量在15个之内,本文所提出的信息泄露节点预测算法能较好地预测出信息传播过程中的泄露节点。
7 总结本文基于分布式学习自动机,结合UCB估计器,提出了基于UCB估计器的分布式学习自动机的信任推断算法EDLATrust。该算法能够推断非直连节点之间的信任值,在保证精确度的情况下,进一步提高了算法的收敛速度。针对信息传播模型中信息会在多节点间转发传播,仅利用公共邻居的相似性特征往往并不能有效地判断2个非直连节点间的信息传播关系的问题,提出了3个适合信息传播模型的节点对特征。针对信息传播模型中泄露节点预测问题,利用非直连节点之间的3种特征结合XGBoost算法进行节点链接关系预测,利用预测概率可以有效辅助推断信息传播过程中的信息泄露节点。未来,将基于泄露点预测算法,进一步考虑泄露路径的影响,以保护用户的隐私安全。
[1] |
KIM Y A. An enhanced trust propagation approach with expertise and homophily-based trust networks[J]. Knowledge-Based Systems, 2015, 82: 20-28. DOI:10.1016/j.knosys.2015.02.023 |
[2] |
KIM Y A, SONG H S. Strategies for predicting local trust based on trust propagation in social networks[J]. Knowledge-Based Systems, 2011, 24(8): 1360-1371. DOI:10.1016/j.knosys.2011.06.009 |
[3] |
SHEKARPOUR S, KATEBI S D. Modeling and evaluation of trust with an extension in semantic web[J]. Journal of Web Semantics, 2010, 8(1): 26-36. DOI:10.1016/j.websem.2009.11.003 |
[4] |
FERNÁNDEZ E. Learning automata-based CPU non-intensive calculation of dedicated and shared protected paths in bandwidth-guaranteed networks[J]. Computer Communications, 2017, 103: 130-140. DOI:10.1016/j.comcom.2016.10.010 |
[5] |
MORADABADI B, MEYBODI M R. Link prediction in weighted social networks using learning automata[J]. Engineering Applications of Artificial Intelligence, 2018, 70: 16-24. DOI:10.1016/j.engappai.2017.12.006 |
[6] |
GHAVIPOUR M, MEYBODI M R. Trust propagation algorithm based on learning automata for inferring local trust in online social networks[J]. Knowledge-Based Systems, 2018, 143: 307-316. DOI:10.1016/j.knosys.2017.06.034 |
[7] |
DAUD N N, HAMID S H A, SAADOON M, et al. Applications of link prediction in social networks: A review[J]. Journal of Network and Computer Applications, 2020, 166: 102716. DOI:10.1016/j.jnca.2020.102716 |
[8] |
LIBEN-NOWELL D, KLEINBERG J. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019-1031. DOI:10.1002/asi.20591 |
[9] |
LIU Y Y, ZHAO C L, WANG X J, et al. The degree-related clustering coefficient and its application to link prediction[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 454: 24-33. DOI:10.1016/j.physa.2016.02.014 |
[10] |
MUNIZ C P, GOLDSCHMIDT R, CHOREN R. Combining contextual, temporal and topological information for unsupervised link prediction in social networks[J]. Knowledge-Based Systems, 2018, 156: 129-137. DOI:10.1016/j.knosys.2018.05.027 |
[11] |
FU C B, ZHAO M H, FAN L, et al. Link weight prediction using supervised learning methods and its application to yelp layered network[J]. IEEE Transactions on Knowledge & Data Engineering, 2018, 30(8): 1507-1518. |
[12] |
CHEN T, GUESTRIN C. XGBoost: A scalable tree boosting system[C]// The 22nd ACM SIGKDD International Conference. New York, USA, 2016: 785-794.
|
[13] |
UREN~A R, KOU G, DONG Y C, et al. A review on trust propagation and opinion dynamics in social networks and group decision making frameworks[J]. Information Sciences, 2019, 478: 461-475. DOI:10.1016/j.ins.2018.11.037 |
[14] |
REZVANIAN A, RAHMATI M, MEYBODI M R. Sampling from complex networks using distributed learning automata[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 396: 224-234. DOI:10.1016/j.physa.2013.11.015 |
[15] |
GE H, JIANG W, LI S H, et al. A novel estimator based learning automata algorithm[J]. Applied Intelligence, 2015, 42(2): 262-275. DOI:10.1007/s10489-014-0594-1 |
[16] |
BASTAMI E, MAHABADI A, TAGHIZADEH E. A gravitation-based link prediction approach in social networks[J]. Swarm and Evolutionary Computation, 2019, 44: 176-186. DOI:10.1016/j.swevo.2018.03.001 |
[17] |
KIANINEJAD M, KABIRI P. A strategy for trust propagation along the more trusted paths[C]// 2018 3rd Conference on Swarm Intelligence and Evolutionary Computation. Bam, Iran, 2018: 1-6.
|
[18] |
JIANG W J, WU J, LI F, et al. Trust evaluation in online social networks using generalized network flow[J]. IEEE Transactions on Computers, 2016, 65(3): 952-963. DOI:10.1109/TC.2015.2435785 |