[科普中国]-在线社交网络结构平衡性

社交网络的社会关系中存在两类关系：正关系和负关系。正关系是指一个用户与另一个用户之间的友谊或一个用户对另一个用户的支持、赞同等正面情感因素。负关系是指一个用户和另一个用户之间的敌对关系，或一个用户反对、不信任另外一个用户。这种社交网络中的正负关系是普遍存在并且对社交网络的环境、结构、演化等方面都起着很重要的作用。例如，Wikipedia的用户能够对管理员提名者进行投票表示同意或反对，Epinions的用户能够声明对某个人的信任与否，Slashdot的用户能够声明某个人是自己的朋友还是敌人。如果把正关系的边用正号表示，负关系的边用负号表示，一个基本问题是全网络或局部网络的符号是如何影响一条边的符号的？这个问题的研究意义在于了解社交网络中的负关系产生的基本原理。

Guha等人首先提出了单条边的符号预测问题1，即假设整个有向网络的拓扑结构已知，并且除一条边之外的所有边的符号也已知，如何预测那条边的符号。这个问题的形式化定义如下：有向图G=（V,E），s（x,y）从节点x指向节点y的有向边（x,y）的符号，即如果（x,y）的符号为正，s（x,y）=1，如果符号为负，s（x,y）=−1，如果x和y之间没有有向边，那么s（x,y）=0。

Jure Leskovec2等人又利用经典的结构平衡性理论进行符号预测。结构平衡性理论认为某些社会网络关系比其他社会网络关系更为常见和稳定。该理论主要研究三人间的友好和敌对关联，认为我敌人的朋友是我的敌人的社会关系比我朋友的朋友是我敌人更为常见，也更稳定。也就是说，如果w和边（u，v）形成了三角关系，那么三角关系中出现朋友关系的个数必然是奇数。换句话说，如果定义如下的函数fbalance：

fbalance：{types—τ}→{+1,−1,0},

其中τ表示某种三角关系（w,u,v），fbalance（τ）=s̅（u,w）s̅（v,w）。结果显示，结合结构平衡性理论的logistic回归模型能更好地在Epinions和Slashdot上进行符号预测。