社群網路的研究已經變成近幾年來最熱門的議題之一。在社群網路裡兩個使用者之間的互動關係可以是正面的也可以是負面的，在有這兩種關係的社群網路我們稱為有號社群網路。在這篇論文中，我們目標是利用正向以及負向的關係來預測連結的正負性。然而，在先前的研究裡對於預測連結正負性的議題中，我們觀察到有一種我們稱為聚集模糊(aggregation ambiguity)的現象。這個現象的意思是當正向資訊和負向資訊差不多的時候，在有號社群網路裡面我們比較難去預測連結的正負性。為此我們提出了一個以社群信心度(social confidence)為基礎的鄰近信心聚合演算法Proximity Confidence Aggregator (PCA) 來解決這個問題。我們的方法同時還結合了網路架構裡使用者跟連結關係的資訊，而這些資訊分別以局部特性跟廣域特性的方式來擷取。在我們的實驗中，我們所使用的有號社群網路有四個:維基百科的修定資訊、維基百科裡管理員的投票資訊以及Slashdot跟Epinions這兩個社群網站的社群關係。這些有號社群網路裡同時包含了負向關係較多以及正向關係較多的網路。實驗的結果最後顯示出以四個社群網路的平均準確率來看，我們的方法能取得更好的結果且效能比先其他的基礎方法增加了7.75%準確率。值得注意的是，我們的法不僅能解決聚集模糊的現象，而且在四個有號社群網路裡都取得最佳的結果。

Social network analysis has become one of the most popular research issues in recent years. The social network in which the relationships between two users can be positive and negative is called the signed network. In this paper, we try to use the positive and negative relations to predict the sign of links in a signed network. However, we observed the phenomenon of the “aggregation ambiguity” in the link sign prediction problem in previous work. This phenomenon means when the positive and negative evidences are nearly equal, we are hard to predict the sign of links in a signed network. Therefore, we propose a Proximity Confidence Aggregator (PCA) algorithm, which based on social confidence that combines the local and global network properties measured from features of nodes and edges. In our experiments, we study four datasets of signed networks from Wikiedit, Wikivote, Slashdot, and Epinions. The experimental results show that our approach leads to a better performance and gets 7.75% improvement over other baseline approaches in the average of accuracy. It is noteworthy that our approach can not only solve the aggregation ambiguity problem but also get a better performance in all of the datasets with a diverse distribution of positive and negative links.

[1] Adamic, L.A. and Adar, E., Friends and neighbors on the Web. Social Networks, 2003. 25(3), 211-230.
[2] Backstrom, L. and Leskovec, J., Supervised Random Walks: Predicting and Recommending Links in Social Networks, in WSDM’11. 2011, ACM: Hong Kong, China.
[3] Brandes, U., Lerner, J., Kenis, P., and Raaij, D.v., Network Analysis of Collaboration Structure in Wikipedia, in International World Wide Web Conference. 2009, ACM: Madrid, Spain.
[4] Brin, S. and Page, L., The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 1998. 30(1–7), 107–117.
[5] Brzozowski, M.J., Hogg, T., and Szabo, G., Friends and foes: ideological social networking, in Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems. 2008, ACM: Florence, Italy.
[6] Burke, M. and Kraut, R., Mopping up: modeling wikipedia promotion decisions, in Proceedings of the 2008 ACM conference on Computer supported cooperative work. 2008, ACM: San Diego, CA, USA.
[7] Cartwright, D. and Harary, F., Structure balance: A generalization of Heider’s theory. Psych. Rev, 1956. 63.
[8] Guha, R., Kumar, R., Raghavan, P., and Tomkins, A., Propagation of trust and distrust, in Proceedings of the 13th international conference on World Wide Web. 2004, ACM: New York, NY, USA.
[9] Haveliwala, T., Kamvar, S., and Jeh, G., An analytical comparison of approaches to personalizing PageRank (Technical Report). 2003: Stanford, CA: Stanford University.
[10] Haveliwala, T.H., Topic-sensitive PageRank: A context-sensitive ranking algorithm for Web search. IEEE Transactions on Knowledge and Data Engineering, 2003. 15(4): p. 784-796.
[11] Heider, F., Attitudes and cognitive organization. Journal of Psychology, 1946. 21: p. 107-112.
[12] Hogg, T., Wilkinson, D., Szabo, G., and Brzozowski, M., Multiple relationship types in online communities and social networks. In Proc. AAAI Spring Symposium on Social Information Processing, 2008.
[13] Jeh, G. and Widom, J., Scaling personalized Web search, in In Proceedings of the 12th International World Wide Web Conference (WWW12). 2003: New York: ACM Press. p. 271-279.
[14] Jeh, G. and Widom, J., SimRank: A measure of structural-context similarity, in In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2002: New York: ACM Press. p. 271–279.
[15] Kamvar, S.D., Haveliwala, T.H., Manning, C.D., and Golub, G.H., Exploiting the block structure of the Web for computing PageRank (Technical Report). 2003: Stanford, CA: Stanford University.
[16] Kleinberg, J.M., Authoritative Sources in a Hyperlinked Environment. J. ACM, 1999. 46(5): p. 604-632.
[17] Kunegis, J., Lommatzsch, A., and Bauckhage, C., The slashdot zoo: mining a social network with negative edges, in Proceedings of the 18th international conference on World wide web. 2009, ACM: Madrid, Spain.
[18] Kunegis, J., Schmidt, S., Lommatzsch, A., Lerner, J., Luca, E.W.D., and Albayrak, S., Spectral Analysis of Signed Graphs for Clustering, Prediction and Visualization. Proceedings of the SIAM International Conference on Data Mining, SDM 2010, 2010.
[19] Lampe, C.A.C., Johnston, E., and Resnick, P., Follow the reader: filtering comments on slashdot, in Proceedings of the SIGCHI conference on Human factors in computing systems. 2007, ACM: San Jose, California, USA.
[20] Leskovec, J., Backstrom, L., Kumar, R., and Tomkins, A., Microscopic Evolution of Social Networks, in KDD’08. 2008, ACM: Las Vegas, Nevada, USA.
[21] Leskovec, J., Huttenlocher, D., and Kleinberg, J., Predicting positive and negative links in online social networks, in Proceedings of the 19th international conference on World wide web. 2010, ACM: Raleigh, North Carolina, USA.
[22] Leskovec, J., Huttenlocher, D., and Kleinberg, J., Signed networks in social media, in Proceedings of the 28th international conference on Human factors in computing systems. 2010, ACM: Atlanta, Georgia, USA.
[23] Liben-Nowell, D. and Kleinberg, J., The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol., 2007. 58(7): p. 1019-1031.
[24] Ma, H., King, I., and Lyu, M.R., Learning to recommend with social trust ensemble, in Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval. 2009, ACM: Boston, MA, USA.
[25] Ma, H., Lyu, M.R., and King, I., Learning to recommend with trust and distrust relationships, in Proceedings of the third ACM conference on Recommender systems. 2009, ACM: New York, New York, USA.
[26] Ma, H., Yang, H., Lyu, M.R., and King, I., SoRec: social recommendation using probabilistic matrix factorization, in Proceeding of the 17th ACM conference on Information and knowledge management. 2008, ACM: Napa Valley, California, USA.
[27] Newman, M.E.J., Clustering and preferential attachment in growing networks, in Physical Review Letters E. 2001.
[28] Salton, G. and McGill, M.J., Introduction to modern information retrieval, in McGraw-Hill. 1983: New York.
[29] Scott, J., Social Network Analysis: a Handbook. Sage Publications, 2000.
[30] Symeonidis, P., Tiakas, E., and Manolopoulos, Y., Transitive node similarity for link prediction in social networks with positive and negative links, in Proceedings of the fourth ACM conference on Recommender systems. 2010, ACM: Barcelona, Spain.
[31] Wasserman, S. and Faust, K., Social Network Analysis: Methods and Applications. 1994: Camb. U. Press.
[32] Yang, B., Cheung, W., and Liu., J., Community mining from signed social networks. IEEE Trans. on Knowl. and Data Eng., 2007. 19(10): p. 1333–1348.