基于隱空間映射的帶符號網絡上的頂點分類

盛俊 顧沈勝 陳崚

摘 要：社會網絡頂點分類在解決實際問題中有廣泛的應用，但絕大多數現有的網絡頂點分類算法都集中在無符號的網絡，而在邊上具有符號的社交網絡上的頂點分類算法卻很少，且負鏈接對于符號網絡分析的作用大于正鏈接。研究了符號網絡中頂點的分類問題。首先將正、負網絡映射到相對應的隱空間，提出基于隱空間的正負鏈接的數學模型;然后提出優化該模型的迭代算法，通過對隱空間矩陣和映射矩陣的迭代優化，來對網絡中的頂點進行分類。由帶符號的社會網絡數據集的實驗結果證明，該算法在數據集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.