基于结构平衡理论与地位理论的符号预测算法

崔晓丽　薛乐洋　张鹏

摘要： 针对符号预测算法在预测准确率和算法复杂度方面难以均衡的问题，有效地融合社会学发展规律与网络局部特征，提出一种基于结构平衡理论与地位理论计算节点相似度的符号预测算法。为更好的结合上述两种理论对两节点相似度得分的贡献，引用调节因子，将基于两种理论的相似度得分按照调节因子的权重求和，相似度的得分的正负即为边符号预测的结果。最后将算法在多个不同数据集进行实验，与经典的CN算法和PSNBS算法在预测准确率与算法复杂度两个方面进行对比分析。结果显示该算法在预测准确率方面与经典算法非常接近，但在时间复杂度方面本文比经典算法低一个数量级，明显优于经典算法。

关键词： 结构平衡理论；地位理论；相似度；符号网络；符号预测

中图分类号： C94文献标识码： A

Signed Prediction Algorithm Based on Structural Balance Theory and Status Theory

CUI Xiaoli1， XUE Leyang1，2， ZHANG Peng 1

Abstract：Aiming at the difficulty of balancing the accuracy and complexity of the sign prediction algorithm， this paper effectively integrates the law of social development and the local characteristics of the network， and proposes a sign prediction algorithm based on structural balance theory and status theory to calculate the similarity of nodes. In order to better combine the contribution of the above two theories to the similarity score of the two nodes， this paper uses the regulator to sum the similarity score based on the two theories according to the weight of the regulator， and the positive or negative of the similarity score is the result predicted by the edge symbol. Finally， the algorithm is tested on several different data sets and compared with the classical CN algorithm and PSNBS algorithm in two aspects of prediction accuracy and algorithm complexity. The proposed algorithm is very close to the classical algorithm in terms of prediction accuracy， but in terms of time complexity， it is an order of magnitude lower than the classical algorithm.It is obviously better than classical algorithm.

Key words： structural balance theory; status theory; similarity; signed network; sign prediction

0 引言

社會由各种错综复杂的系统组成，随着科学技术的进步与发展，将这些复杂系统抽象成网络去研究和分析的思路得到学术界的普遍认可，例如常见的交通网络、社交网络、生物网络和电力网络。信息化快速发展的同时产生了许多情感交互信息（如点赞、评价、评分等），如何将这种非量化的信息引入到复杂网络中从而提升研究的深度和广度，符号网络为我们提供一个很好的研究思路。

符号网络是指网络中的边具有正号或者负号的属性［1］，其中，正边表示积极、朋友、支持等正向关系，负边表示消极、敌人、反对等负向关系。例如人与人之间可能是好友或者敌人的社交关系［2］、各个国家之间友好或敌对的关系［3］，这些事例都可以被抽象成符号网络。符号网络的相关研究目前主要集中在符号网络的传播、符号预测、平衡性以及社团划分4个方向，其中符号预测是更为基础性的问题，主要关注网络中边符号信息的还原与预测，研究符号预测问题能够为其他3个问题的研究提供理论基础。

目前，符号预测工作的相关研究成果已有很多，主要可以分为两类：基于矩阵的符号预测算法与基于分类的符号预测算法［4］。基于矩阵的符号预测算法将符号网络映射为矩阵，然后利用矩阵分解、矩阵填充等方式进行符号预测。Guha［5］提出的符号预测方法是通过信任传播模型进行预测，这是符号网络中符号预测问题最早的研究成果。Agrawal等［6］提出通过矩阵的奇异值分解、特征值分解或者和核函数分解的方法也可以有效进行符号预测。Hsieh等［7］结合弱结构平衡原理，通过低秩矩阵填充算法进行符号预测。基于分类的符号预测算法即将符号网络中的符号预测问题转化为分类问题，然后通过各种分类算法进行正负号预测。Leskovec等［8］提出一种结合结构平衡理论与地位理论的机器学习算法。Yang等［9］提出基于行为关系的相互作用模型，该模型通过无监督或半监督模型进行符号预测。Symeonidis等［10］定义了一个基于节点相似度的模型，该模型可以有效捕获局部图特征，从而进行符号预测。佘宏俊［11］提出的基于共同邻居的符号网络链接预测算法CN，结合节点符号密度和网络拓扑特征进行预测，提高了负边的预测准确率。张维玉等［12］提出一种结合结构平衡理论的机器学习算法，该算法首次引入PageTrust度量网络中节点的重要程度。刘苗苗等［13］提出一种基于结构平衡理论和相似度的新算法PSNBS，该算法计算基于结构平衡理论的Two-step路径和Three-step路径的相似度得分，引入影响因子λ调节不同路径得分贡献度，最后对相似度得分进行分类得出预测结果。

综上所述，目前被大家广泛接受较为经典的是CN算法和PSNBS算法，这两个算法在基于结构平衡理论与路径相似度预测时能够取得较高的预测准确率，并且随着选取结构平衡环中环边数的增加，其算法准确率也会提升，但是环数增加会使得算法复杂度快速升高。在快速发展的大数据时代，许多网络的边数达到百万以上，算法复杂度的升高将会带来很高的成本。因此，本文在结构平衡理论的基础上引入地位理论，期望在维持符号预测准确率的前提下降低算法复杂度。

1 算法介绍

1.1 结构平衡理论

1946年Heider［2］提出一种基于社会心理学的结构平衡理论，该理论对符号网络的发展具有重要意义。该模型将个体之间的相互关系分为积极和消极两种类型，描述并分析个体之间关系类型的演化规律。1956年Cartwright和Harary［14］将结构平衡理论推广至图论中，并通过数学语言将两类关系描述为符号网络，网络中用边的正、负符号分别表示积极关系和消极关系。2010年Leskovec等［15］将结构平衡理论推广至符号网络中的符号预测问题。

在无向符号网络中的结构平衡理论主要通过三角形的结构平衡讨论，由3个节点组成的三角形共有3条边，其中每条边有正号和负号两种可能性，共有4种三角形组合模式［16］。4种组合模式形成4个直观认识：1）朋友的朋友是我的朋友；2）朋友的敌人是我的敌人；3）敌人的朋友是我的敌人；4）敌人的敌人是我的朋友。

如图1所示，图1中a、b为结构平衡三角形，c、d为不平衡三角形。不平衡三角形不符合社会发展规律，人们总是尽量避免这种情况发生。因此，实际生活中结构平衡三角形的数量远大于不平衡的三角形的数量［17］。

1.2 地位理论

2010年Leskovec和Kleinberg等在文献［8］中通过大量分析有向网络中用户建立连接的倾向，提出了适用有向网络的新理论——地位理论。结构平衡理论可以视为朋友与敌人、支持与反对等多种关系的建模，其主要针对于无向符号网络的符号预测问题。与结构平衡理论不同，地位理论适用于刻画有向网络，相关研究表明，在有向网络符号预测问题中，引入地位理论可以有效提升其预测准确率［8，18-19］。

地位理论可以视为基于个体身份的判定，地位理论认为符号网络中边的符号受两节点之间边的方向以及两节点的地位影响，其理论如图2所示。地位理论与结构平衡理论两者都适用于由3个节点构成的三角形，图3中给出了8种地位理论认为合理的三角形关系组成模式。其中虚线表示节点A与节点B之间的连边符号是缺失的，两节点之间的符号倾向受节点地位的影响。

1.3 基于符号网络基础理论与相似度的算法

为了更好地平衡符号预测准确率与算法复杂度的关系，本文结合社会学发展规律与网络局部特征定义了两节点相似度的概念，通过节点相似度预测边符号，我们将此称之为PSNCN算法。首先，综合考虑两节点之间的共同邻居的数量以及共同邻居的度对于节点相似度的影响。在度量共同邻居度对两节点相似度影响时，假设共同邻居的度越小对两节点的相似度贡献越大；在度量共同邻居数量对两节点间相似度的影响时，假设共同邻居越多对两节点相似度贡献更大。其次，结合结构平衡理论与地位理论对网络符号的影响，定义两节点之間的相似度。在度量地位理论对节点相似度的影响时，先将网络中所有的负边转化为逆向的正边，然后使预测边符号与长度为2的路径所在的三角形尽可能满足地位理论。最后，为更好地结合上述两种理论对两节点相似度得分的贡献，引入调节因子，将基于两种理论的相似度得分按照调节因子的权重求和，最终相似度的得分的正负即为边符号预测的结果。

设G=V，E，S为符号网络中的有向无权图；其中V=v1，v2，…vn代表网络中所有节点组成的集合，E=e（vi，vj）代表由节点vi指向vj的有向边集合。在有向边集合E中，vi，vj∈V，e（vi，vj）∈0，1，若e（vi，vj）=1则说明节点对〈vi，vj〉存在有向边，否则不存在有向边。S=s（vi，vj）为有向边的符号集合。在符号集合S中，vi，vj∈V，svi，vj∈0，1，-1，若svi，vj=1，则节点对〈vi，vj〉之间的边符号为正；若svi，vj=-1，则节点对〈vi，vj〉之间的边符号为负；若svi，vj=0，则节点对〈vi，vj〉之间的边无符号。对于vi，vj∈V且svi，vj=0，将节点对〈vi，vj〉基于符号网络理论的相似度得分定义为CNScore2vi，vj，具体计算如式（1）所示。

2 结果与讨论

2.1 数据集

为了更好地验证PSNCN算法的预测准确率，本文下载（http：//snap.stanford.edu/）Epinions，Slashdot和Wikipedia三个数据集进行符号预测。这些数据集目前被广泛应用于各类符号网络的符号预测问题中，是研究符号网络的经典数据集，3个数据集基本信息（见表1）：1）Epinions：是一个大众消费者点评网站。该网站会为用户之间提供一个信任机制，允许用户创建有向符号链接来表达对其他用户信任或者不信任的态度。2）Slashdot：是一个以其特定的用户社区而闻名的资讯科技网站。在2002年，Slashdot引入了Slashdot Zoo特性，允许用户将彼此标记为朋友或敌人，由此形成一个用户间是朋友或敌人的符号网络。3）Wikipedia：是一个用多种语言编写而成的网络百科全书，该网络的用户可以申请成为维基百科的管理员，然后由维基百科的其他成员投支持、中立或反对的票。这就形成了一个有向的签名网络，其中节点代表维基百科的成员，边代表投票。

2.2 数据集划分及评价指标

采用k-折叠交叉验证法划分各数据集，即将数据集按边随机划分为k份，本实验中k主要取10，5，3。从E中取一份作为测试集Ete、剩余k-1份作为训练集Etr，并且满足Ete∪Etr=E和Ete∩Etr=。将以上实验重复k次，其中k份数据中的每一份数据都仅被选择一次，最后取k次预测准确率的平均值为算法符号预测准确率。这种方法的优点是可以使符号网络数据集中的每一条边都有一次机会被预测。为了更好地与各种经典算法进行对比分析，采用符号网络中常用的评价符号预测准确率的指标accuracy，该指标通过混淆矩阵来表示预测准确率，指标公式如式（6）所示，混淆矩阵如表2所示。

2.3 PSNCN算法的预测准确率

为了更好地验证评价模型效果，针对3个数据集抽取不同比例的边作为测试集进行试验，预测模型准确率，同时为更好地度量不同理论对于节点相似度贡献的不同程度，引入调节因子λ，图6中给出了在λ取不同值的情况下，PSNCN算法针对不同数据集以及不同比例测试集的预测准确率，实验中测试集占符号网络中边的比例为1/k，预测准确率值是k次独立实验的平均值，k值分别取10，5，3，PSNCN算法预测准确率结果如图5所示。

由图5可以看出，PSNCN算法预测准确率受调节因子λ的影响，且在本实验所选取的3个大型符号网络数据集中，随着λ的增大，预测准确率的数值均呈现出先增大后减小的趋势，在λ等于0.5附近时，预测准确率结果趋向最优。该准确率值的变化可以说明PSNCN算法在符号预测过程中，地位理论和结构平衡理论发挥了不同的作用。针对以上数据集在符号预测过程中测试集中边的数量占所有边的比例1/k取值越小，其预测准确率越高，但是预测准确率整体差距很小，数值较为接近。该变化说明PSNCN算法受已知信息的影响较小，在已知符号信息较少时仍保持较高的预测准确率。

2.4 PSNCN算法复杂度

2.4.1 PSNCN算法的时间复杂度分析

第1步：计算节点对〈vi，vj〉的共同邻居，首先寻找节点vi的所有邻居，然后判断其是否也为节点vj的邻居，因此其时间复杂度为Odi，其中di为节点i的度。然后查找测试集中所有待预测边的共同邻居，其复杂度为OE2〈d〉，其中，E为符号网络中边的总数量，〈d〉为平均度。

第2步：计算节点对的相似度得分，需对该节点对的所有共同邻居进行计算。节点vi为节点vj的邻居的概率为di/N，其中，N为符号网络中的节点数目。因此计算基于地位理论与结构平衡理论的相似度得分的时间复杂度为OE〈d〉/N。

综上，PSNCN算法第1步的时间复杂度更高，PSNCN算法时间复杂度为OE〈d〉。

2.4.2 PSNCN算法的空間复杂度分析

有向符号网络以E*3维邻接矩阵形式存储。矩阵的每行表示网络的一条边。前两列分别为起始节点及终结点，第3列表示连边的符号。计算中的中间数据均针对每个预测边存储，可以用L行矩阵表示。第1列存储BScore2信息，第2列存储RScore2信息，第3列加权结果CNScore2信息。另外，需存储每个节点的邻居集合，对每个节点以链表方式存储其连接点，使用空间为ONd=2E，该空间还使用4N空间存储每个节点的正出度、正入度、负出度、负入度。综上，PSNCN的空间复杂度为OE+OL+OV〈d〉，即OE。

2.5 与经典算法的准确率和时间复杂度对比

PSNCN算法通过结合符号网络理论与节点间路径信息计算节点相似度，从而预测符号网络中的边的未知符号。为了更好地验证PSNCN算法性能，将该算法的预测准确率及算法复杂度与符号预测的经典算法CN和PSNBS算法进行了对比实验。对比实验中，各算法采用相同的符号网络数据集（Epinions、Slashdot、Wikipedia）、相同的测试集比例、相同的评价指标accuracy。此外，PSNCN算法根据2.4章节结果，针对3个的数据集，λ的值分别设定为0.4，0.5，0.5。各算法的预测准确率统计结果如表3所示，算法复杂度如表4所示。

由表3可以看出，针对不同数据集以及同一数据集不同比例测试集，PSNCN算法与PSNBS算法的预测准确率明显高于CN算法，PSNCN算法比CN算法预测准确率平均值高0.01以上，这对于预测准确率已达到较高的算法是一个很大的提升。在PSNCN算法与PSNBS算法的预测准确率之间，PSNCN算法的预测准确率略低于PSNBS算法，但其准确率数值与PSNBS算法非常接近，特别在大型符号网络Epinions中，在测试集比例为10%的情况下，PSNCN算法的预测准确率仅比PSNBS算法预测准确率低0.002，在测试集比例为33.33%时，两者算法预测准确率差距最大仅为0.006。

由表4可知，3个算法的空间复杂度均为O|E|。在时间复杂度方面，CN算法与PSNCN算法的时间复杂度为O|E|〈d〉，PSNBS算法的时间复杂度为O|E|〈d〉2，PSNBS算法时间复杂度明显高于PSNCN算法。

通过与各算法预测准确率和算法复杂度对比分析，PSNCN算法与PSNBS算法的预测准确率能明显优于CN算法，PSNCN算法的预测准确率与PSNBS算法较为接近，但PSNBS算法时间复杂度明显高于PSNCN算法，特别是对于大型稠密符号网络，网络中节点的平均度〈d〉≈N，则PSNBS算法与PSNCN算法的时间复杂度则分别为O|E|N2和O|E|N，PSNBS算法的时间复杂度是PSNCN算法时间复杂度的N倍，时间复杂度的提升将会造成巨大的时间成本。综上所述，PSNCN算法能够更好地平衡预测准确率和算法复杂度。

3 结论

本文提出基于符号网络基础理论与相似度的符号预测算法PSNCN，该算法综合考虑结构平衡理论与地位理论以及路径信息定义两节点之间的相似度，改进了已有的结合结构平衡理论与相似度的算法的不足之处。PSNCN算法在多个大型符号网络数据集以及不同比例测试集上进行符号预测，并采用经典的准确率评价指标accuracy，将实验结果与目前经典的符号预测算法CN和PSNBS在预测准确率和算法复杂度两个方面进行对比分析。验证了本文算法PSNCN在取得较高的预测准确率的同时算法复杂度较低，且随着测试集比例的增加，仍取得较高的预测准确率。此外，如何将算法中节点相似度等相关信息应用到符号网络的社团划分及推荐算法中，从而帮助我们进行更精准的社团划分与推荐是我们下一步需要研究的内容。

参考文献：

［1］程苏琦，沈华伟，张国清，等.符号网络研究综述［J］.软件学报，2014，25（1）：1-15.

CHENG S Q， SHEN H W， ZHANG G Q， et al.Survey of signed network research［J］.Journal of Software，2014，25（1）：1-15.

［2］HEIDER F. Attitudes and cognitive organization［J］. The Journal of Psychology Interdisciplinary and Applied， 1946， 21（1）：107-112.

［3］GHOSN F， PALMER G， BREMER S A. The MID3 data set， 1993-2001： procedures， coding rules， and description［J］. Conflict Management and Peace Science， 2004， 21（2）：133-154.

［4］蓝梦微，李翠平，王绍卿，等.符号社会网络中正负关系预测算法研究综述［J］.计算机研究与发展，2015，52 （2）：410-422.

LAN M W， LI C P， WANG S Q， et al. Survey of sign prediction algorithms in signed social networks［J］.Journal of Computer Research and Development，2015，52（2）：410-422.

［5］GUHA R， KUMAR R， RAGHAVAN P， et a1. Propagation of trust and distrust［C］// Proc of the 13th Int Conf onworld wide Web.New York： ACM， 2004： 403-412.

［6］AGRAWAL P， GARG V K，NARAYANAM R. Link label prediction in signed social networks［C］//Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Beijing： AAAI，2013：2591-2597.

［7］HSIEH C J， CHIANG K Y， DHILLON I S. Low rank modeling of signed networks［C］//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York：ACM，2012：507-515.

［8］LESKOVEC J， HUTTENLOCHER D，KLEINBERG J.Signed networks in social media［C］//Proceedings of the SIGCHI International Conference on Human Factors in Computing Systems.New York：ACM，2010：1361-1370.

［9］YANG S H， SMOLA A J，LONG B， et al.Friend or frenemy？prediction signed ties in social networks［C］//Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval.New York：ACM，2012：555-564.

［10］ SYMEONIDIS P， TIAKAS E. Transitive node similarity：Prediction and recommending links in signed social networks［J］. Internet & Web Information Systems，2014，17（4）：743-776.

［11］ 佘宏俊，胡夢缘.基于符号网络的边值预测方法研究［J］.武汉理工大学学报（信息与管理工程版），2015，37 （5）：464-468.

SHE H J， HU M Y. Research of link prediction based on signed networks［J］. Journal of Wuhan University of Technology （Information & Management Engineering）， 2015，37（5）：464-468.

［12］ ZHANG W Y， WU B， LIU Y. Integrating multi-feature for link sign prediction in signed networks［J］. Journal of Beijing University of Posts and Telecommunications， 2014， 37（5）： 80-84.

［13］ 刘苗苗，郭景峰，陈晶.相似度与结构平衡论结合的符号网络边值预测［J］.工程科学与技术，2018， 50（4）： 161-169.

LIU M M， GUO J F， CHEN J. Link prediction in signed networks based on similarity and structural balance theory［J］.Advanced Engineering Sciences，2018，50（4）：161-169.

［14］ CA RTWRIGHT D， HARARY F. Structural balance： a generalization of Heiders theory ［J］. Psychological Review，1956，63（5）：27.

［15］ LESKOVEC J， HUTTENLOCHER D， K1EINBERG J. Predicting positive and negative links in online social networks［C］//Proc of the 19th Int Conf on World Wide Web. New York：ACM，2010：641-650.

［16］ SRINIVASAN A. Local balancing influences global structure in social networks［J］.Proc of the National Academy of Sciences of the United States of America， 2011， 108（5）：1751-1752.

［17］ EASLEY D， KLEINBERG J. Networks， Crowds， and Markets： Reasoning About a Highly connected world［M］. New York：Cambridge University Press，2010：119-152.

［18］ CHIANG K Y， NATARAJAN N， TEWARI A， et al. Exploiting longer cycles for link prediction in signed networks［C］// Proceedings of the 20th ACM Conference on Information and Knowledge Management.New York： ACM， 2011：1157-1162.

［19］ CHIANG K Y， HSIEH C J， NATARAJAN N， et al. Prediction and clustering in signed networks： a local to global perspective［J］. Journal of Machine Learning Research， 2013， 15（1）：1177-1213.

（責任编辑 耿金花）

收稿日期： 2022-03-09；修回日期：2022-06-07

第一作者： 崔晓丽（1995-），女，山东日照人，硕士研究生，主要研究方向为符号网络理论及应用。

通信作者： 张鹏（1981-），女，北京人，博士，副教授，主要研究方向为复杂系统，复杂网络。