基于隐空间映射的带符号网络上的顶点分类

盛俊 顾沈胜 陈崚

摘 要：社会网络顶点分类在解决实际问题中有广泛的应用，但绝大多数现有的网络顶点分类算法都集中在无符号的网络，而在边上具有符号的社交网络上的顶点分类算法却很少，且负链接对于符号网络分析的作用大于正链接。研究了符号网络中顶点的分类问题。首先将正、负网络映射到相对应的隐空间，提出基于隐空间的正负链接的数学模型;然后提出优化该模型的迭代算法，通过对隐空间矩阵和映射矩阵的迭代优化，来对网络中的顶点进行分类。由带符号的社会网络数据集的实验结果证明，该算法在数据集Epinions上得到结果的F1值在11以上，在数据集Slashdo上得到结果的F1值在23.8以上，与随机算法相比具有较高的精确度。

关键词：带符号网络;隐空间;映射;顶点分类

中图分类号：TP393.02; TP393.094

文献标志码：A

Abstract： Social network node classification is widely used in solving practical problems. Most of the existing network node classification algorithms focus on unsigned social networks，

while node classification algorithms on social networks with symbols on edges are rare. Based on the fact that the negative links contribute more on signed network analysis than the positive links. The classification of nodes on signed networks was studied. Firstly， positive and negative networks were projected to the corresponding latent spaces， and a mathematical model was proposed based on positive and negative links in the latent spaces. Then， an iterative algorithm was proposed to optimize the model， and the iterative optimization of latent space matrix and projection matrix was used to classify the nodes in the network. The experimental results on the dataset of the signed social network show that the F1 value of the classification results by the proposed algorithm is higher than 11 on Epinions dataset， and that is higher than 23.8 on Slashdo dataset，which indicate that the proposed algorithm has higher accuracy than random algorithm.

英文關键词Key words： signed network; latent space; projection; node classification

0 引 言

随着如Facebook、Twitter、LinkedIn、Epinions等一系列社会网络网站的迅速崛起，研究者将大量的精力投入到了社会机制的研究当中[1]，来分析用户的体验和行为模式。传统的社会网络分析主要只考虑了如Facebook和MySpace等无标记的社会网络，这些网络可以化作图模型，其中顶点代表实体，带权重的边就代表实体之间是否存在关系以及这个关系的重要性[2]。最近，对带符号的有向社会网络的研究正逐步兴起。在带符号的社会网络中，用户之间的关系既可以是正的（表明用户之间的信任），也可以是负的（表明用户之间的关系是不信任），比如：在Epinions网络[3]中用户可以根据他们的评价来决定信任或者不信任其他用户;在Slashdot网络[4]这个主要关注与技术相关新闻的网站上，用户们可以根据对文章的评论相互点击成为朋友（喜欢）或者敌人（不喜欢）。这些带符号的有向的社会网络都可以用不对称的邻接矩阵来表示： 如果其中的元素是1，那么这两个实体间的关系为正; 如果元素是-1，那么就说明这两个实体间的关系为负; 0则表示缺失。

在过去的十年中，在线社交网络的出现产生了大量关于用户的个人信息，如他们的活动、个人或团体之间的联系，以及他们的意见和想法等。这些信息使得社交网站在社会认同发展、社会交友活动中起了很大的作用[5]。这些数据中的有些具有类别性质的维度可以被建模为与个体相关的标签。这些标签在网络结构中表示为顶点上的类号，这些类号将网络的顶点划分成若干个类。这些类号有多种形式：人口标签（如年龄、性别和出生地点等）; 政治或信仰标签（如政治党派、宗教信仰等）; 其他还有兴趣爱好的标签、工作单位标签等。标签通常在网络上的用户配置文件中显示，或用于关联到其他网络中的相同类的对象（如照片、视频等）。

然而，由于大多数社交媒体用户都不愿意分享他们的信息，社交媒体网站只能收集非常有限的用户信息[6]，例如超过90%的Facebook用户不愿意透露他们的政治观点[6]。因此，社交网络中有部分用户所属的类别是不知道的，即这些顶点的标签是未知的。网络顶点分类就是要从已知用户的信息以及网络的链接结构来推断位置用户的标签信息[7-8]。这个问题不同于传统的分类问题，也不能直接用传统的机器学习的分类方法来解决。传统的基于机器学习的分类方法往往假设对象是独立的，只是采用传统的统计推断过程来进行分类，这样会导致推断的结果不精确;而在基于网络的顶点分类中，必须充分利用顶点间链接所反映的潜在的相关性结果来提高分类的质量。

许多现实世界的问题可以被建模为无符号社交网络中的顶点分类问题，它的目标是通过给网络提供一些有标签的用户[9]来预测未标记的社交网络中的未标记顶点的标签。近年来，人们已经提出一些关于顶点分类问题的方法[10]，这些算法主要有基于局部分类器的方法和随机游走方法[11]、基于局部分类器分类方法、使用局部社区信息来学习本地分类器、基于随机游走的方法模拟粒子在网络上进行随机游动来进行顶点分类等： 如Lu等[12]提出标签传播方法进行网络顶点的分类; Azran等[13]利用随机游走的半监督学习的方法进行网络顶点的多分类; Zhu等[14]利用基于高斯场合调和函数的半监督学习的方法进行顶点分类; Zhou等[15-16] 应用图的正则化方法，提出了有向图上的基于监督学习的顶点分类方法; Baluja等[17]提出了吸附（adsorption）方法进行顶点分类，并应用于YouTube网站的视频推荐之中; Nandanwar 等 [18]提出了一种基于邻居的结构的分类器，采用了一种基于懒惰随机游走的方法，根据顶点的度等结构特征，来决定邻居的类号; Taskar等[19]提出一种基于图的概率模型方法，使用判别分析来进行图上关系数据的分类; 王小攀等[20]提出了一种基于属类概率选择图近邻结构的方法， 利用高斯核函数计算近邻点的边权值，构造属类概率图，并将这种属类概率图与K近邻（KNearest Neighbors， KNN）图线性组合并嵌入标签传递算法框架中，得到一种基于双图结构的标签传递算法; 邵海军[21]提出基于Web数据修补技术与新型蚁群算法相结合的弱关联Web数据分类方法，对弱关联Web数据的关联性利用关联查询过程中的实时属性进行修补，然后再利用求解旅行商问题（Traveler Salesman Problem， TSP）规则对蚁群信息素更新、融合，并将融合结果运用于弱关联数据分类中，以实现Web数据的准确分类; Li等[22]提出基于信念网络的网页分类算法; Zhang等[23] 以及Kazienko等 [24]分别提出了标签相关和度量标签的网络多类分类方法; Zhang等 [25]利用顶点之间基于的相对信息熵的相似度对网络顶点进行分类。

目前，绝大多数的顶点分类算法都集中在无符号的社交网络或只有正链接的社交网络[9，12，15，26]上，然而大部分真实的符号社交网络中可以同时包含正面和负面的联系，例如：Epinions中包括信任和不信任的联系;Slashdot中有朋友和敌人的链接，但对于符号网络的顶点分类的研究工作却很少。传统的基于关联的网络分类算法将结构化的数据通过正相关相互联系对数据对象进行分类，而符号社会网络数据中，含有两类相反的相关关系，这将为顶点分类提供有效的信息，因此，如何在这种符号社会网络中，充分利用这两类相反的相关关系对用户进行分类是一个新的挑战。

近来对于符号网络的研究证明，负链接对于符号网络分析的作用大于正链接，因此，负链接在许多对于符号网络分析的任务中起着关键性的作用。本文研究符号网络中顶点的分类问题时，将正、负网络映射到一个相同的隐空间，提出基于隐空间的正负链接的数学模型，提出优化该模型的迭代算法，通过对隐空间矩阵和映射矩阵的迭代优化，来对网络中的顶点进行分类。由带符号社会网络数据集的实验结果证明，本文算法的预测结果具有较高的精确度。

5 结语

本文将正负网络映射到相对应的隐空间，设计出基于隐空间的正、负链接的数学模型，并提出了优化该模型的迭代算法，通过对隐空间矩阵和映射矩阵的迭代优化得到分类矩阵，从而对网络中的顶点进行分类。由带符号社会网络数据集的实验结果证明，本文算法的预测结果具有较高的精确度。

参考文献 （References）

[1] GUHA R， KUMAR R， RAGHAVAN P， et al. Propagation of trust and distrust[C]// Proceedings of the 13th International Conference on World Wide Web. New York： ACM， 2004： 403-412.

[2] SONG D J， MEYER D. Link sign prediction and ranking in signed directed social networks[J]. Social Network Analysis & Mining， 2015， 5（1）： 1-14.

[3] BURKE M， KRAUL R. Mopping up： modeling Wikipedia promotion decisions[C]// Proceedings of the 2008 ACM Conference on Computer Supported Cooperative Work. New York： ACM， 2008：27-36.

[4] KUNEGIS J， LOMMATZSCH A， BAUCKHAGE C. The Slashdot zoo： mining a social network with negative edges[C]// Proceedings of the 18th International Conference on World Wide Web. New York： ACM， 2009：541-550.

[5] 王新月，王興超，雷雳，等.社交网站在社会认同发展中的作用[J].心理科学进展， 2018， 26（11）： 2024-2034.（WANG X Y， WANG X C， LEI L， et al. The role of social networking sites in the development of social identity[J]. Advances in Psychological Science， 2018， 26（11）： 2024-2034.）

[6] ZHELEVA E， GETOOR L. To join or not to join： the illusion of privacy in social networks with mixed public and private user profiles[C]// Proceedings of the 18th International Conference on World Wide Web. New York： ACM， 2009： 531-540.

[7] ABBASI M A， TANG J，LIU H. Scalable learning of users preferences using networked data[C]// Proceedings of the 25th ACM Conference on Hypertext and Social Media. New York： ACM， 2014： 4-12.

[8] TANG L， LIU H. Relational learning via latent social dimensions[C]// Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 817-826.

[9] SEN P， NAMATA G， BILGIC M， et al. Collective classification in network data[J]. AI Magazine， 2008， 29（3）： 93.

[10] GETOOR L， DIEHL C P. Link mining： a survey[J]. ACM SIGKDD Explorations Newsletter， 2005， 7（2）： 3-12.

[11] BHAGAT S， CORMODE G， MUTHUKRISHNAN S. Node classification in social networks[C]// Social Network Data Analytics. Berlin： Springer， 2011： 115-148.

[12] LU Q， GETOOR L. Linkbased classification[C]// Proceedings of the 20th International Conference on International Conference on Machine Learning. Menlo Park， CA： AAAI Press， 2003： 496-503.

[13] AZRAN A. The rendezvous algorithm： multiclass semisupervised learning with Markov random walks[C]// Proceedings of the 24th International Conference on Machine Learning. New York： ACM， 2007：49-56.

[14] ZHU X， GHAHRAMANI Z， JOHN L， et al. Semisupervised learning using Gaussian fields and harmonic functions[C]// Proceedings of the 20th International Conference on Machine Learning. Menlo Park， CA： AAAI Press， 2003： 912-919.

[15] ZHOU D， BOUSQUET O， THOMAS N L， et al. Learning with local and global consistency[C]// Proceedings of the 16th International Conference on Neural Information Processing Systems. Cambridge， MA： MIT Press， 2003： 321-328.

[16] ZHOU D， HUANG J， SCHOLKOPF B. Learning from labeled and unlabeled data on a directed graph[C]// Proceedings of the 22nd International Conference on Machine Learning. New York： ACM， 2005： 1036-1043.

[17] BALUJA S， SETH R， SIVAKUMAR D， et al. Video suggestion and discovery for YouTube： taking random walks through the view graph[C]// Proceedings of the 17th International Conference on World Wide Web. New York： ACM， 2008： 895-904.

[18] NANDANWAR S， MURTY M N. Structural neighborhood based classification of nodes in a network[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2016： 1085-1094.

[19] TASKAR B， ABBEEL P， KOLLER D. Discriminative probabilistic models for relational data[C]// Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence. New York： ACM， 2002：485-492.

[20] 王小攀，胡艷.基于双图结构标签传递算法的高光谱数据分类[J].计算机与数字工程，2018， 46（10）： 2117-2122.（WANG X P，HU Y. Hyperspectral data classification based on double graph structure label transfer algorithm[J]. Computer and Digital Engineering， 2018， 46（10）： 2117-2122.）

[21] 邵海军. 弱关联Web数据分类方法优化研究与仿真[J].计算机仿真，2015，32（12）： 392-395.（SHAO H J. Research and simulation on the optimization of weak association Web data classification method[J]. Computer Simulation， 2015， 32（12）：392-395.）

[22] LI Y C， NIE X Q， HUANG R. Web spam classification method based on deep belief networks[J]. Expert Systems with Applications， 2018， 96： 261-270.

[23] ZHANG Z，WANG H，LIU L， et al. Multilabel relational classification via node and label correlation[J]. Neurocomputing， 2018， 292： 72-81.

[24] KAZIENKO P， KAJDANOWICZ T. Labeldependent node classification in the network[J]. Neurocomputing， 2012， 75（1）： 199-209.

[25] ZHANG Q， LI M Z， DENG Y. Measure the structure similarity of nodes in complex networks based on relative entropy[J]. Physica A： Statistical Mechanics and its Applications， 2018， 491：749-763.

[26] GIANVITO P， FRANCESCO S， DONATO M， et al. Multitype clustering and classification from heterogeneous networks[J].Information Sciences， 2018， 425：107-126.

[27] LESKOVEC J， HUTTENLOCHER D. Predicting positive and negative links in online social networks[C]// Proceedings of the 19th International Conference on World Wide Web. New York： ACM， 2010：641-650.