微信服务号

微信订阅号

2025年5月1日 23:29 星期四
首页 > 过刊浏览>2014年第25卷第1期 >1-15. DOI:10.13328/j.cnki.jos.004503
PDF HTML阅读 XML下载 导出引用 引用提醒
符号网络研究综述
作者:
基金项目:

国家重点基础研究发展计划（973）（2012CB316303）；国家科技支撑计划（2012BAH39B04）；国家自然科学基金（61232010，61202215，61174152）；北京市自然科学基金（4122077）


Survey of Signed Network Research
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [76]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    符号网络是指边具有正或负符号属性的网络，其中，正边和负边分别表示积极的关系和消极的关系.真实世界的许多复杂网络中都存在对立的关系，尤其是在信息、生物和社会领域.利用边的符号属性去分析、理解和预测这些复杂网络的拓扑结构、功能、动力学行为具有十分重要的理论意义，并且对个性化推荐、态度预测、用户特征分析与聚类等都具有重要的应用价值.然而，当前人们对网络的符号属性关注较少.综述了符号网络的研究背景及意义、国内外研究现状和最新进展，并讨论了目前存在的主要问题，试图让人们对符号网络这一研究方向能有清晰而全面的认识，为网络数据挖掘、复杂网络分析、社会学、生物信息学等相关领域的研究者提供有益的参考.

    Abstract:

    Signed network is a kind of network including edges with the property of positive or negative sign. The positive and negative sign represent positive relationship and negative relationship, respectively. Many real complex networks have opposite relationships, especially in social, biological and information fields. Using the sign properties of edges to analysis, understand and predict the topological structures, functions and dynamic behaviors of these real networks has important theoretical significance and practical applications, such as personalized recommendation, prediction of attitudes, user analysis and clustering and so on. However, academic research has devoted little attention to signed network. This paper reviews the background, significance, research situation and recent progress of signed networks, and discusses the main problems of existing works. This study is to provide a clear and comprehensive understanding to this meaningful research area, and to benefit to the researchers from the fields of network data mining, complex network analysis, sociology and biological information.

    参考文献
    [1] Heider F. Attitudes and cognitive organization. Journal of Psychology, 1946,21(1):107-112. [doi: 10.1080/00223980.1946. 9917275]
    [2] Ghosn F, Palmer G. The MID3 data set, 1993-2001: Procedures, coding rules, and description. Conflict Management and Peace Science, 2004,21(2):133-154. [doi: 10.1080/07388940490463861]
    [3] Parisien C, Anderson CH, Eliasmith C. Solving the problem of negative synaptic weights in cortical models. Neural Computation, 2008,20(6):1473-1494. [doi: 10.1162/neco.2008.07-06-295]
    [4] Guha R, Kumar R, Raghavan P, Tomkins A. Propagation of trust and distrust. In: Proc. of the 13th Int''l Conf. on World Wide Web. New York: ACM Press, 2004. 403-412. [doi: 10.1145/988672.988727]
    [5] Kunegis J, Lommatzsch A, Bauckhage C. The slashdot zoo: Mining a social network with negative edges. In: Proc. of the 18th Int''l Conf. on World Wide Web. New York: ACM Press, 2009. 741-750. [doi: 10.1145/1526709.1526809]
    [6] Leskovec J, Huttenlocher D, Kleinberg J. Signed networks in social media. In: Proc. of the SIGCHI Conf. on Human Factors in Computing Systems. New York: ACM Press, 2010. 1361-1370. [doi: 10.1145/1753326.1753532]
    [7] Leskovec J, Huttenlocher D, Kleinberg J. Predicting positive and negative links in online social networks. In: Proc. of the 19th Int''l Conf. on World Wide Web. New York: ACM Press, 2010. 641-650. [doi: 10.1145/1772690.1772756]
    [8] Larusso N, Bogdanov P, Singh A. Identifying communities with coherent and opposing views. In: Proc. of the 15th Annual Graduate Student Workshop in Computing. Santa Barbara: UCSB, 2010. 31-32. http://gswc.cs.ucsb.edu/2010/proceedings.pdf
    [9] Pang B, Lee L. Opinion mining and sentiment analysis. Foundations and Trends in Information Retrieval, 2008,2(1-2):1-135. [doi: 10.1561/1500000011]
    [10] Cartwright D, Harary F. Structural balance: A generalization of Heider''s theory. Psychological Review, 1956,63(5):277-293. [doi: 10.1037/h0046049]
    [11] Huang ZX, Qiu YH. A multiple-perspective approach to constructing and aggregating citation semantic link network. Future Generation Computer Systems, 2010,26(3):400-407. [doi: 10.1016/j.future.2009.07.006]
    [12] Srinivasan A. Local balancing influences global structure in social networks. Proc. of the National Academy of Sciences, 2011, 108(5):1751-1752. [doi: 10.1073/pnas.1018901108]
    [13] Davis JA. Clustering and structural balance in graphs. Human Relations, 1967,20(2):181-187. [doi: 10.1177/001872676702000 206]
    [14] Szell M, Lambiotte R, Thurner S. Multirelational organization of large-scale social networks in an online world. Proc. of the National Academy of Sciences, 2010,107(3):13636-13641. [doi: 10.1073/pnas.1004008107]
    [15] Chiang KY, Natarajan N, Tewari A, Dhillon IS. Exploiting longer cycles for link prediction in signed networks. In: Proc. of the 20th ACM Int''l Conf. on Information and Knowledge Management. New York: ACM Press, 2011. 1157-1162. [doi: 10.1145/2063576.2063742]
    [16] Bonacich P, Lloyd P. Calculating status with negative relations. Social Networks, 2004,26(4):331-338. [doi: 10.1016/j.socnet.2004. 08.007]
    [17] Bonacich P. Power and centrality: A family of measures. American Journal of Sociology, 1987,92(5):1170-1182. [doi: 10.1086/228631]
    [18] Bonacich P. Some unique properties of eigenvector centrality. Social Networks, 2007,29(4):555-564. [doi: 10.1016/j.socnet.2007. 04.002]
    [19] Kamvar SD, Schlosser MT, Garcia-Molina H. The EigenTrust algorithm for reputation management in P2P networks. In: Proc. of the 12th Int''l Conf. on World Wide Web. New York: ACM Press, 2003. 640-651. [doi: 10.1145/775152.775242]
    [20] de Kerchove C, van Dooren P. The PageTrust algorithm: How to rank Web pages when negative links are allowed. In: Proc. of the SIAM Int''l Conf. on Data Mining. Philadelphia: SIAM, 2008. 346-352. https://www.siam.org/proceedings/datamining/2008/dm08. php
    [21] Harary F, Kabell JA. A simple algorithm to detect balance in signed graphs. Mathematical Social Sciences, 1980,1(1):131-136. [doi: 10.1016/0165-4896(80)90010-4]
    [22] Maybee JS, Maybee SJ. An algorithm for identifying Morishima and anti-Morishima matrices and balanced digraphs. Mathematical Social Sciences, 1983,6(1):99-103. [doi: 10.1016/0165-4896(83)90050-1]
    [23] Kunegis J, Schmidt S, Lommatzsch A, Lerner J, de Luca EW, Albayrak S. Spectral analysis of signed graphs for clustering, prediction and visualization. In: Proc. of the SIAM Int''l Conf. on Data Mining. Philadelphia: SIAM, 2010. 559-570. https://www. siam.org/proceedings/datamining/2010/dm10.php
    [24] Zachary WW. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977,33(4): 452-473.
    [25] Katz L. A new status index derived from sociometric analysis. Psychometrika, 1953,18(1):39-43. [doi: 10.1007/BF02289026]
    [26] Harary F. On the measurement of structural balance. Behavioral Science, 1959,4(4):316-323.
    [27] Harary F. A matrix criterion for structural balance. Naval Research Logistics Quarterly, 1960,7(2):195-199. [doi: 10.1002/nav. 3800070208]
    [28] Facchetti G, Iacono G, Altafini C. Computing global structural balance in large-scale signed social networks. Proc. of the National Academy of Sciences, 2011,108(52):20953-20958. [doi: 10.1073/pnas.1109521108]
    [29] Galam S. Fragmentation versus stability in bimodal coalitions. Physica A: Statistical Mechanics and its Applications, 1996,230 (1-2):174-188. [doi: 10.1016/0378-4371(96)00034-9]
    [30] Antal T, Krapivsky PL, Redner S. Dynamics of social balance on networks. Physical Review E, 2005,72(3):036121. [doi: 10.1103/PhysRevE.72.036121]
    [31] Marvel SA, Strogatz SH, Kleinberg JM. Energy landscape of social balance. Physical Review Letters, 2009,103(19):198701. [doi: 10.1103/PhysRevLett.103.198701]
    [32] Shen HW. Community Structure of Complex Networks. Berlin: Springer-Verlag, 2013. 1-17.
    [33] Doreian P, Mrvar A. A partitioning approach to structural balance. Social Networks, 1996,18(2):149-168. [doi: 10.1016/0378- 8733(95)00259-6]
    [34] Doreian P, Batagelj V, Ferligoj A. Generalized Blockmodeling. Cambridge: Cambridge University Press, 2005. 295-325.
    [35] Doreian P. A multiple indicator approach to blockmodeling signed networks. Social Networks, 2008,30(3):247-258. [doi: 10.1016/j.socnet.2008.03.005]
    [36] Brusco M, Doreian P, Mrvar A, Steinley D. Two algorithms for relaxed structural balance partitioning: Linking theory, models and data to understand social network phenomena. Sociological Methods and Research, 2011,40(1):57-87. [doi: 10.1177/004912 4110384947]
    [37] Mrvar A, Doreian P. Partitioning signed two-mode networks. The Journal of Mathematical Sociology, 2009,33(3):196-221. [doi: 10.1080/00222500902946210]
    [38] Banerjee S, Sarkar K, Gokalp S, Sen A, Davulcu H. Partitioning signed bipartite graphs for classification of individuals and organizations. In: Proc. of the Social Computing, Behavioral—Cultural Modeling and Prediction. LNCS, Berlin: Springer-Verlag, 2012. 196-204. [doi: 10.1007/978-3-642-29047-3_24]
    [39] Inohara T. Quasi-Clusterability of signed graphs with negative self evaluation. Applied Mathematics and Computation, 2004,158(1): 201-215. [doi: 10.1016/j.amc.2003.09.005]
    [40] Inohara T. Signed graphs with negative self evaluation and clusterability of graphs. Applied Mathematics and Computation, 2004, 158(2):477-487. [doi: 10.1016/j.amc.2003.09.015]
    [41] Gómez S, Jensen P, Arenas A. Analysis of community structure in networks of correlated data. Physical Review E, 2009,80(1): 016114. [doi: 10.1103/PhysRevE.80.016114]
    [42] Traag VA, Bruggeman J. Community detection in networks with positive and negative links. Physics Review E, 2009,80(3): 036115. [doi: 10.1103/PhysRevE.80.036115]
    [43] Li X, Chen HC, Li S. Exploiting emotions in social interactions to detect online social communities. In: Proc. of the Pacific Asia Conf. on Information Systems. Atlanta: AIS, 2010. 1426-1437.
    [44] Bansal N, Blum A, Chawla S. Correlation clustering. Machine Learning, 2002,56(1-3):89-113.
    [45] Demaine ED, Immorlica N. Correlation clustering with partial information. In: Proc. of the Approximation, Randomization, and Combinatorial Optimization. LNCS, Berlin: Springer-Verlag, 2003. 1-13. [doi: 10.1007/978-3-540-45198-3_1]
    [46] Yang B, Cheung WK, Liu JM. Community mining from signed social networks. IEEE Trans. on Knowledge and Data Engineering, 2007,19(10):1333-1348. [doi: 10.1109/TKDE.2007.1061]
    [47] Kong LQ, Yang ML. Improvement of clustering algorithm FEC for signed networks. Journal of Computer Applications, 2011,31(5): 1395-1399 (in Chinese with English abstract). [doi: 10.3724/SP.J.1087.2011.01395]
    [48] Sharma T, Charls A, Singh PK. Community mining in signed social networks—An automated approach. In: Proc. of the Int''l Conf. on Computer Engineering and Applications. Singapore: IACSIT Press, 2009. 152-157. http://cpfd.cnki.com.cn/Article/CPFDTOTAL-CDYA200906001028.htm
    [49] Wang ZG, Thorngate W. Sentiment and social mitosis: Implications of Heider''s balance theory. Journal of Artificial Societies and Social Simulation, 2003,6(3):26-45.
    [50] Antal T, Krapivsky PL, Redner S. Social balance on networks: The dynamics of friendship and enmity. Physica D: Nonlinear Phenomena, 2006,224(2):130-136. [doi: 10.1016/j.physd.2006.09.028]
    [51] Kulakowski K, Gawroński P, Gronek P. The Heider balance—A continuous approach. Int''l Journal of Modern Physics C, 2005, 16(5):707-716. [doi: 10.1142/S012918310500742X]
    [52] Gawroński P, Gronek P, Kulakowski K. The Heider balance and social distance. Acta Physica Polonica B, 2005,36(8):2549-2558.
    [53] Gawroński P, Kulakowski K. Heider balance in human networks. AIP Conf. Proc., 2005,779(1):93-95.
    [54] Marvel SA, Kleinberg J, Kleinberg RD, Strogatz SH. Continuous-Time model of structural balance. Proc. of the National Academy of Sciences, 2011,108(5):1771-1776. [doi: 10.1073/pnas.1013213108]
    [55] Gawroński P, Kulakowski K. A numerical trip to social psychology: Long-Living states of cognitive dissonance. Computational Science, 2007,4490:43-50. http://link.springer.com/chapter/10.1007/978-3-540-72590-9_6
    [56] Radicchi F, Vilone D, Yoon S, Meyer-Ortmanns H. Social balance as a satisfiability problem of computer science. Physical Review E, 2007,75(2):026106. [doi: 10.1103/PhysRevE.75.026106]
    [57] Radicchi F, Vilone D, Meyer-Ortmanns H. Universality class of triad dynamics on a triangular lattice. Physical Review E, 2007, 75(2):021118. [doi: 10.1103/PhysRevE.75.021118]
    [58] Malekzadeh M, Fazli MA, Khalidabadi PJ, Safariy M, Rabieey HR. Social balance and signed network formation games. In: Proc. of the 5th Int''l Workshop on Social Network Mining and Analysis. NewYork: ACM Press, 2011. http://users.cis.fiu.edu/~lzhen001/activities/KDD2011Program/workshops/SNAKDD2011/SNAKDD2011-Proceedings.pdf#page=127
    [59] Victor P, Cornelis C, De Cock M, da Silva PP. Gradual trust and distrust in recommender systems. Fuzzy Sets and Systems, 2009, 160(10):1367-1382. [doi: 10.1016/j.fss.2008.11.014]
    [60] Victor P, Cornelis C, De Cock M, Teredesai AM. Trust- and distrust- based recommendations for controversial reviews. Intelligent Systems, 2011,26(1):48-55. [doi: 10.1109/MIS.2011.22]
    [61] Ma H, Lyu MR, King I. Learning to recommend with trust and distrust relationships. In: Proc. of the 3rd ACM Conf. on Recommender Systems. New York: ACM Press, 2009. 189-196. [doi: 10.1145/1639714.1639746]
    [62] Chen CC, Wan YH, Chung MC, Sun YC. An effective recommendation method for cold start new users using trust and distrust networks. Information Sciences, 2009,224:19-36. [doi: 10.1016/j.ins.2012.10.037]
    [63] Symeonidis P, Tiakas E, Manolopoulos Y. Transitive node similarity for link prediction in social networks with positive and negative links. In: Proc. of the 4th ACM Conf. on Recommender Systems. New York: ACM Press, 2010. 183-190. [doi: 10.1145/1864708.1864744]
    [64] Liu HF, Lim EP, Lauw HW, Le MT, Sun AX, Srivastava J, Kim YA. Predicting trusts among users of online communities: An epinions case study. In: Proc. of the 9th ACM Conf. on Electronic Commerce. New York: ACM Press, 2008. 310-319. [doi: 10. 1145/1386790.1386838]
    [65] DuBois T, Golbeck J, Srinivasan A. Predicting trust and distrust in social networks. In: Proc. of the 2011 IEEE Int''l Conf. on Social Computing. Washington: IEEE Computer Society, 2011. 418-424. [doi: 10.1109/PASSAT/SocialCom.2011.56]
    [66] Zolfaghar K, Aghaie A. Mining trust and distrust relationships in social Web applications. In: Proc. of the 2010 IEEE Int''l Conf. on Intelligent Computer Communication and Processing. Washington: IEEE Computer Society, 2010. 73-80. [doi: 10.1109/ICCP. 2010.5606460]
    [67] Borzymek P, Sydow M. Trust and distrust prediction in social network with combined graphical and review-based attributes. In: Proc. of the Agent and Multi-Agent Systems: Technologies and Applications. LNCS, Berlin: Springer-Verlag, 2010. 122-131. [doi: 10.1007/978-3-642-13480-7_14]
    [68] Maniu S, Cautis B, Abdessalem T. Building a signed network from interactions in Wikipedia. In: Proc. of the Databases and Social Networks. New York: ACM Press, 2011. 19-24. [doi: 10.1145/1996413.1996417]
    [69] Mishra A, Bhattacharya A. Finding the bias and prestige of nodes in networks based on trust scores. In: Proc. of the 20th Int''l Conf. on World Wide Web. New York: ACM Press, 2011. 567-576. [doi: 10.1145/1963405.1963485]
    [70] Li RH, Yu JX, Huang X, Cheng H. A framework of algorithms: Computing the bias and prestige of nodes in trust networks. PLoS ONE, 2013,7(12):e50843.
    [71] Chiluka N, Andrade N, Pouwelse J, Sips H. Leveraging trust and distrust for sybil-tolerant voting in online social media. In: Proc. of the 1st Workshop on Privacy and Security in Online Social Media. New York: ACM Press, 2012. 1-8. [doi: 10.1145/2185354. 2185355]
    [72] Khopkar T, Li X, Resnick P. Self-Selection, slipping, salvaging, slacking, and stoning the impacts of negative feedback at eBay. In: Proc. of the 6th ACM Conf. on Electronic Commerce. New York: ACM Press, 2005. 223-231. [doi: 10.1145/1064009.1064033]
    [73] Inohara T. Clusterability of groups and information exchange in group decision making with approval voting system. Applied Mathematics and Computation, 2003,136(1):1-15. [doi: 10.1016/S0096-3003(02)00008-5]
    [74] Nishikawaa T, Mottera AE. Network synchronization landscape reveals compensatory structures, quantization, and the positive effect of negative interactions. Proc. of the National Academy of Sciences, 2010,107(23):10342-1034. [doi: 10.1073/pnas. 0912444107]
    [75] Brandes U, Kenis P, Lerner J, van Raaij D. Network analysis of collaboration structure in Wikipedia. In: Proc. of the 18th Int''l Conf. on World Wide Web. New York: ACM Press, 2009. 731-740. [doi: 10.1145/1526709.1526808]
    [76] Kermarrec AM, Thraves C. Can everybody sit closer to their friends than their enemies. In: Proc. of the Mathematical Foundations of Computer Science. LNCS, Berlin: Springer-Verlag, 2011. 388-399. [doi: 10.1007/978-3-642-22993-0_36]
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

程苏琦,沈华伟,张国清,程学旗.符号网络研究综述.软件学报,2014,25(1):1-15

复制
分享
文章指标
  • 点击次数:8464
  • 下载次数: 12703
  • HTML阅读次数: 4205
  • 引用次数: 0
历史
  • 收稿日期:2012-07-26
  • 最后修改日期:2013-06-09
  • 在线发布日期: 2013-11-04
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19894625位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号