基于复杂网络的若干动态机制研究
|
摘要
复杂网络广泛存在于自然界和人类社会中,例如交通运输网络,电力系统,电话通信网络,神经网络,细胞网络,蛋白质一蛋白质相互作用网络,互联网等。因此,研究这些网络不仅对人类的工作和生活有着重大意义,而且对我们了解自然界的演化规律有着重要的指导价值。
我们使用k近似方法检测社区动态变化,并与其他常见的算法比较来推断社区结构的相似性。通过分析社区节点之间的模块化分析,得到边的分配聚集的实际效果。我们提出了两个完全不同类型的图形的节点的近似算法,并证明了在海豚数据集上的可行性。高度的模块化是社区内的边缘比(或高于那些权重)和一个类似的随机生成的图(即不存在一个社区结构)的一个重要指标。社区发现使用模块化的优化具有和派系结构相似的结构。
社会网络的谣言传播的四个状态(“无知者”,“传播者”,“免疫者”和“潜伏状态”)在第三章进行了论证。我们扩展了谣言传播的标准模型,并给出一个在不同拓扑条件下完整的BA网络模拟结果。
在第四章,我们提出了推荐系统用户评分的相似性度量,从而在社会网络起到积极的信息过滤。在过去的十年里,社会推荐系统已经得到了物理,社会学和计算机科学等领域越来越多的关注。在这项研究中,我们使用社会网络来捕获用户兴趣的相似性,使用推荐系统来探讨潜在的相似之处。利用豆瓣网的书籍和评论者的数据集,我们建立了相似性预测模型。我们使用奇异值分解评估了模型的相似性测度的优缺点,并讨论了有效的推荐系统。
我们提出并研究了一种小世界网络上的舆论动力学的模型。特别的,我们将Hegselmann-Krause模型作为一个互动的随机过程,并通过计算机模拟进行分析。我们通过对自系数的确定来分析舆论过程中将会出现的持久的影响。根据远程连接和自系数,从无序到有序的过渡过程,我们观察到丰富多彩的动力学行为。总的来说,我们发现自系数的出现促进共识,由于所谓的“组效应”,有利于存在于网络中的观点之间的聚集。而且,由于不同观点要维持他们的自系数的行为的约束,这可能导致产生统一的共识。在这种情况下,足够频繁的远程链接是网络收敛到一个固定阶段的关键。
Complex network exists in both nature and human society, such as transporta-tion networks, power systems, telephone communication networks, neural networks,cell networks, protein-protein interaction networks, Internet. Therefore, the study ofcomplex networks is of great significance for human life and work, and for the under-standing of evolution of nature.
We present K-means approach and similarity measures to detect community dy-namic and infer community structure with other common algorithm. The modularitymeasures the quality of the clustering by inspecting the arrangement of the edges withinthe communities of vertices. We have provided algorithms for approximate computa-tion for nodes in different types of graphs, and have demonstrated the embedding onavailable dolphin dateset. A high modularity is an important indicator that the edgeswithin the communities outnumber (or have higher weights than) those in a similarrandomly generated graph (that does not present a community structure). Communitiesdiscovered using modularity optimization have a structure that is similar to the structureof cliques.
Gossip spreading with four states ("Ignorant","Spreader","Stifler" and "Death")in social networks is showed in chapter3. We extend the standard model of gossip dis-semination, and give a complete simulation in BA networks under different conditions.
Similarity measure of user rating play a positive information filter in social net-works is studied in chapter4. In the past decade, social recommending systems haveattracted increasing attention from the physical, social and computer science communi-ties. In this study, we use social networks to capture similarities of users’ interest and,accordingly, recommending systems to explore latent similarities. We build similarity-ratings-prediction models for a dataset of books and reviewers from Douban.com. Us-ing singular value decomposition, we evaluate the strengths and the weaknesses of thesimilarity measure, and discuss their effectiveness in recommending systems.
We propose and study a minimal model of opinion dynamics on small world net-works. In particular, we reformulate the Hegselmann-Krause model as an interactivestochastic process and analyze it by means of computer simulations. We introduce self-coefficients in order to determine the impact of persistent players on the emergence ofconsensus. Depending on the fraction of directed long-range connections and the valueof self-coefficients, we observe fascinatingly rich dynamical behavior and transitions from disordered to ordered states. In general, we find that self-coefficients promote theemergence of consensus due to the so-called “group effect” that facilitates coalescencebetween otherwise separated network components. Since players want to maintain theirself-coefficients they are also behaviorally constrained, which may in turn impede fullconsensus. Sufficiently frequent long-range links are in such situations crucial for thenetwork to converge into an absorbing phase.
我们使用k近似方法检测社区动态变化,并与其他常见的算法比较来推断社区结构的相似性。通过分析社区节点之间的模块化分析,得到边的分配聚集的实际效果。我们提出了两个完全不同类型的图形的节点的近似算法,并证明了在海豚数据集上的可行性。高度的模块化是社区内的边缘比(或高于那些权重)和一个类似的随机生成的图(即不存在一个社区结构)的一个重要指标。社区发现使用模块化的优化具有和派系结构相似的结构。
社会网络的谣言传播的四个状态(“无知者”,“传播者”,“免疫者”和“潜伏状态”)在第三章进行了论证。我们扩展了谣言传播的标准模型,并给出一个在不同拓扑条件下完整的BA网络模拟结果。
在第四章,我们提出了推荐系统用户评分的相似性度量,从而在社会网络起到积极的信息过滤。在过去的十年里,社会推荐系统已经得到了物理,社会学和计算机科学等领域越来越多的关注。在这项研究中,我们使用社会网络来捕获用户兴趣的相似性,使用推荐系统来探讨潜在的相似之处。利用豆瓣网的书籍和评论者的数据集,我们建立了相似性预测模型。我们使用奇异值分解评估了模型的相似性测度的优缺点,并讨论了有效的推荐系统。
我们提出并研究了一种小世界网络上的舆论动力学的模型。特别的,我们将Hegselmann-Krause模型作为一个互动的随机过程,并通过计算机模拟进行分析。我们通过对自系数的确定来分析舆论过程中将会出现的持久的影响。根据远程连接和自系数,从无序到有序的过渡过程,我们观察到丰富多彩的动力学行为。总的来说,我们发现自系数的出现促进共识,由于所谓的“组效应”,有利于存在于网络中的观点之间的聚集。而且,由于不同观点要维持他们的自系数的行为的约束,这可能导致产生统一的共识。在这种情况下,足够频繁的远程链接是网络收敛到一个固定阶段的关键。
Complex network exists in both nature and human society, such as transporta-tion networks, power systems, telephone communication networks, neural networks,cell networks, protein-protein interaction networks, Internet. Therefore, the study ofcomplex networks is of great significance for human life and work, and for the under-standing of evolution of nature.
We present K-means approach and similarity measures to detect community dy-namic and infer community structure with other common algorithm. The modularitymeasures the quality of the clustering by inspecting the arrangement of the edges withinthe communities of vertices. We have provided algorithms for approximate computa-tion for nodes in different types of graphs, and have demonstrated the embedding onavailable dolphin dateset. A high modularity is an important indicator that the edgeswithin the communities outnumber (or have higher weights than) those in a similarrandomly generated graph (that does not present a community structure). Communitiesdiscovered using modularity optimization have a structure that is similar to the structureof cliques.
Gossip spreading with four states ("Ignorant","Spreader","Stifler" and "Death")in social networks is showed in chapter3. We extend the standard model of gossip dis-semination, and give a complete simulation in BA networks under different conditions.
Similarity measure of user rating play a positive information filter in social net-works is studied in chapter4. In the past decade, social recommending systems haveattracted increasing attention from the physical, social and computer science communi-ties. In this study, we use social networks to capture similarities of users’ interest and,accordingly, recommending systems to explore latent similarities. We build similarity-ratings-prediction models for a dataset of books and reviewers from Douban.com. Us-ing singular value decomposition, we evaluate the strengths and the weaknesses of thesimilarity measure, and discuss their effectiveness in recommending systems.
We propose and study a minimal model of opinion dynamics on small world net-works. In particular, we reformulate the Hegselmann-Krause model as an interactivestochastic process and analyze it by means of computer simulations. We introduce self-coefficients in order to determine the impact of persistent players on the emergence ofconsensus. Depending on the fraction of directed long-range connections and the valueof self-coefficients, we observe fascinatingly rich dynamical behavior and transitions from disordered to ordered states. In general, we find that self-coefficients promote theemergence of consensus due to the so-called “group effect” that facilitates coalescencebetween otherwise separated network components. Since players want to maintain theirself-coefficients they are also behaviorally constrained, which may in turn impede fullconsensus. Sufficiently frequent long-range links are in such situations crucial for thenetwork to converge into an absorbing phase.
引文
[1] A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Sci-ence,286:509–512,1999.
[2] D. J. Watts and S. H. Strogatz. Collective dynamics of’small world’ networks.Nature,393:440–442,1998.
[3] R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Rev.Mod. Phys.,74:47–97,2002.
[4] Steven H. Strogatz. Exploring complex networks. Nature,410:268–276,2001.
[5] Duncan J. Watts. Networks, dynamics, and the small-world phenomenon. Am.J. Soc.,105:493–527,1999.
[6] A.-L. Barabási and Z. N. Oltvai. Network biology: understanding the cell’sfunctional organization. Nature Reviews Genetics,5:101–113,2004.
[7] Jon M. Kleinberg. Navigation in a small world. Nature,406(6798):845,2000.
[8] Qian Chen, Hyunseok Chang, Ramesh Govindan, Sugih Jamin, Scott Shenker,and Walter Willinger. The origin of power-laws in internet topologies revisited.pages608–617,2002.
[9] Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-lawrelationships of the internet topology. Comp. Comm. Rev.,29:251–262,1999.
[10] Alexei Vázquez, Romualdo Pastor-Satorras, and Alessandro Vespignani. Large-scale topological and dynamical properties of the internet. Phys. Rev. E,65:066130,2002.
[11] H. Jeong, S. Mason, A.-L. Barabási, and Z. N. Oltvai. Lethality and centrality inprotein networks. Nature,411:41–42,2001.
[12] H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási. The large-scaleorganization of metabolic networks. Nature,407:651–654,2000.
[13] Rodrigo De Castro and Jerrold W. Grossman. Famous trails to Paul Erdo s. Math.Intel.,21:51–53,1999.
[14] M. E. J. Newman. Scientific collaboration networks: I. Network constructionand fundamental results. Phys. Rev. E,64:016131,2001.
[15] M. E. J. Newman. The structure of scientific collaboration networks. PNAS,98:404–409,2001.
[16] M. Huxham, S. Beaney, and D. Raffaelli. Do parasites reduce the chances oftriangulation in a real food web? Oikos,76:284–300,1996.
[17] Guido Boella, Leendert van der Torre, and Serena Villata. Four measures for thedynamics of coalitions in social networks. pages361–362. ACM,2009.
[18] Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, andBobby Bhattacharjee. Measurement and analysis of online social networks. InProceedings of the7th ACM SIGCOMM conference on Internet measurement,IMC’07, pages29–42. ACM,2007.
[19] Sheng Yu and Subhash Kak. A survey of prediction using social media. CoRR,abs/1203.1647,2012.
[20] P. Erdo s and A. Rényi. On random graphs. Pub. Math.,6:290–297,1959.
[21] P. Erdo s and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad.Mat. Kutató Int. K zl.,5:17–61,1960.
[22] Santo Fortunato. Community detection in graphs. Physics Reports,486(3-5):75–174,2010.
[23] Jierui Xie, Stephen Kelley, and B. K. Szymanski. Overlapping community de-tection in networks: the state of the art and comparative study. ACM ComputingSurveys,45(4),2013.
[24] M. Girvan and M. E. J. Newman. Community structure in social and biologicalnetworks. Proceedings of the National Academy of Sciences,99(12):7821–7826,2002.
[25] M. E. J. Newman. Analysis of weighted networks. Phys. Rev. E,70:056131,2004.
[26] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi. Defining andidentifying communities in networks. Proceedings of the National Academy ofSciences,101(9):2658,2004.
[27] M E Newman. Modularity and community structure in networks. Proceed-ings of the National Academy of Sciences of the United States of America,103(23):8577–8582,2006.
[28] S.E. Schaeffer. Graph clustering. Computer Science Review,1(1):27–64,2007.
[29] Aaron Clauset, Cristopher Moore, and M. E. J. Newman. Hierarchical structureand the prediction of missing links in networks. Nature,453:98–101,2008.
[30] Martin Rosvall and Carl T. Bergstrom. Maps of random walks on complex net-works reveal community structure. Proceedings of the National Academy ofSciences,105(4):1118–1123,2008.
[31] Junhua Zhang, Shihua Zhang, and Xiang-Sun Zhang. Detecting communitystructure in complex networks based on a measure of information discrepancy.Physica A: Statistical Mechanics and its Applications,387(7):1675–1682,2008.
[32] J rg Reichardt and Stefan Bornholdt. Detecting fuzzy community structures incomplex networks with a potts model. Phys. Rev. Lett.,93:218701, Nov2004.
[33] I Ispolatov, I Mazo, and A Yuryev. Finding mesoscopic communities in s-parse networks. Journal of Statistical Mechanics: Theory and Experiment,2006(09):P09014,2006.
[34] Pascal Pons and Matthieu Latapy. Computing communities in large networksusing random walks. volume3733of Lecture Notes in Computer Science, pages284–293. Springer,2005.
[35] Zhenping Li, Shihua Zhang, Rui-Sheng Wang, Xiang-Sun Zhang, and LuonanChen. Quantitative function for community detection. Phys. Rev. E,77:036109,Mar2008.
[36] Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek. Uncovering theoverlapping community structure of complex networks in nature and society.Nature,435(7043):814–818, June2005.
[37] Imre Derényi, Gergely Palla, and Tamás Vicsek. Clique percolation in randomnetworks. Phys. Rev. Lett.,94:160202, Apr2005.
[38] Balázs Adamcsek, Gergely Palla, Illés J. Farkas, Imre Derényi, and Tamás Vic-sek. Cfinder: locating cliques and overlapping modules in biological networks.Bioinformatics,22(8):1021–1023,2006.
[39] Ginestra Bianconi. The entropy of randomized network ensembles. EurophysicsLetters,81(2):28005,2008.
[40] U. Brandes, D. Delling, M. Gaertler, R. G rke, M. Hoefer, Z. Nikoloski, and D.Wagner. On finding graph clusterings with maximum modularity. In Graph-Theoretic Concepts in Computer Science, pages121–132. Springer,2007.
[41] V. Arnau, S. Mars, and I. Marín. Iterative cluster analysis of protein interactiondata. Bioinformatics,21(3):364–378,2005.
[42] R. Aldecoa and I. Marín. Deciphering network community structure by surprise.PloS one,6(9):e24195,2011.
[43] A. Lancichinetti, S. Fortunato, and F. Radicchi. Benchmark graphs for testingcommunity detection algorithms. Physical Review E,78(4):046110,2008.
[44] A. Lancichinetti and S. Fortunato. Community detection algorithms: a compar-ative analysis. Physical Review E,80(5):056117,2009.
[45] R. Aldecoa and I. Marín. Jerarca: Efficient analysis of complex networks usinghierarchical clustering. PloS one,5(7):e11585,2010.
[46] U. Von Luxburg. A tutorial on spectral clustering. Statistics and computing,17(4):395–416,2007.
[47] A.Y. Ng, M.I. Jordan, Y. Weiss, et al. On spectral clustering: Analysis andan algorithm. Advances in neural information processing systems,2:849–856,2002.
[48] M. Rosvall and C.T. Bergstrom. Maps of random walks on complex networksreveal community structure. Proceedings of the National Academy of Sciences,105(4):1118–1123,2008.
[49] V.D. Blondel, J.L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding ofcommunities in large networks. Journal of Statistical Mechanics: Theory andExperiment,2008(10):P10008,2008.
[50] P. Ronhovde and Z. Nussinov. Multiresolution community detection for megas-cale networks by information-based replica correlations. Physical Review E,80(1):016109,2009.
[51] C.P. Massen and J.P.K. Doye. Thermodynamics of community structure.Preprint arXiv:cond-mat/0610077,2006.
[52] J. A. Hartigan. Bloc voting in the united states senate. Journal of Classification,17(1):29–49,2000.
[53] W O Kermack; A G McKendrick. A contribution to the mathematical theoryof epidemics. Proceedings of the Royal Society A: Mathematical, Physical andEngineering Science,115:700–721,1927.
[54] Michael B. A. Oldstone. Viruses, Plagues, and History: Past, Present and Fu-ture. Oxford University Press,2009.
[55] Charles F. Manski. Vaccination with partial knowledge of external effectiveness.107.
[56] Jan Medlock and Alison P. Galvani1. Vaccination with partial knowledge ofexternal effectiveness. Science,325:1705–1708,2009.
[57] Alison L. Hill, David G. Rand, Martin A. Nowak, and Nicholas A. Christakis.Infectious disease modeling of social contagion in networks. PLoS Comput Biol,6(11):e1000968,2010.
[58] D. J. DALEY and D. G. KENDALL. Stochastic rumours. Ima Journal of AppliedMathematics,1(1):42–55,1965.
[59] D. J. DALEY and D. G. KENDALL. Epidemics and rumours. Nature,204(4963):1118–1118,1964.
[60] A. McCallum, X. Wang, and A. Corrada-Emmanuel. Topic and role discoveryin social networks with experiments on enron and academic email. Journal ofArtificial Intelligence Research,30:249–272,2007.
[61] Allan J. Kimmel. Rumors and Rumor Control: A Manager’s Guide to Under-standing and Combatting Rumors. Lawrence Erlbaum Associates,2003.
[62] Y. Moreno, R. Pastor-Satorras, and A. Vespignani. Epidemic outbreaks in com-plex heterogeneous networks. The European Physical Journal B-CondensedMatter and Complex Systems,26:521–529,2002.10.1140/epjb/e20020122.
[63] M. Nekovee, Y. Moreno, G. Bianconi, and M. Marsili. Theory of rumour spread-ing in complex social networks. Physica A: Statistical Mechanics and its Appli-cations,374(1):457–470,2007.
[64] Sebastián Risau-Gusman and Damián H Zanette. Contact switching as a controlstrategy for epidemic outbreaks. Journal of Theoretical Biology,257(1):52–60,March2009.
[65] Claudio Castellano, Santo Fortunato, and Vittorio Loreto. Statistical physics ofsocial dynamics. Rev. Mod. Phys.,81:591–646,2009.
[66] Adam Kleczkowski and Bryan T. Grenfell. Mean-field-type equations for spreadof epidemics: the [‘]small world’ model. Physica A: Statistical Mechanics andits Applications,274(1-2):355–360,1999.
[67] Jaewook Joo and Joel L. Lebowitz. Behavior of susceptible-infected-susceptibleepidemics on heterogeneous networks with saturation. Phys. Rev. E,69:066105,2004.
[68] J. Gani D. Daley and J. Gani. Epidemic Modelling: An Introduction. CambridgeUniversity Press,2001.
[69] M. Nekovee, Y. Moreno, G. Bianconi, and M. Marsili. Theory of rumour spread-ing in complex social networks. Physica A: Statistical Mechanics and its Appli-cations,374(1):457–470,2007.
[70] G. Linden, B. Smith, and J. York. Amazon.com recommendations: item-to-itemcollaborative filtering. Internet Computing, IEEE,7(1):76–80, jan/feb2003.
[71] Abhinandan S. Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram. Googlenews personalization: scalable online collaborative filtering. In Proceedings ofthe16th international conference on World Wide Web, WWW’07, pages271–280, New York, NY, USA,2007. ACM.
[72] G. Adomavicius and A. Tuzhilin. Toward the next generation of recommendersystems: a survey of the state-of-the-art and possible extensions. Knowledge andData Engineering, IEEE Transactions on,17(6):734–749, june2005.
[73] Marko Balabanovic′and Yoav Shoham. Fab: content-based, collaborative rec-ommendation. Commun. ACM,40:66–72, March1997.
[74] Thomas Hofmann. Collaborative filtering via gaussian probabilistic latent se-mantic analysis. In Proceedings of the26th annual international ACM SIGIRconference on Research and development in informaion retrieval, SIGIR’03,pages259–266, New York, NY, USA,2003. ACM.
[75] Yehuda Koren. Factorization meets the neighborhood: a multifaceted collabo-rative filtering model. In Proceedings of the14th ACM SIGKDD internationalconference on Knowledge discovery and data mining, KDD’08, pages426–434,New York, NY, USA,2008. ACM.
[76] John S. Breese, David Heckerman, and Carl Myers Kadie. Empirical analysisof predictive algorithms for collaborative filtering. In Gregory F. Cooper andSeraf[n Moral, editors, UAI, pages43–52. Morgan Kaufmann,1998.
[77] David M. Pennock, Eric Horvitz, Steve Lawrence, and C. Lee Giles. Collab-orative filtering by personality diagnosis: A hybrid memory and model-basedapproach. In Craig Boutilier and MoisWs Goldszmidt, editors, UAI, pages473–480. Morgan Kaufmann,2000.
[78] Paul Resnick, Neophytos Iacovou, Mitesh Suchak, Peter Bergstrom, and JohnRiedl. Grouplens: an open architecture for collaborative filtering of netnews. InProceedings of the1994ACM conference on Computer supported cooperativework, CSCW’94, pages175–186, New York, NY, USA,1994. ACM.
[79] Lyle Ungar, Dean Foster, Ellen Andre, Star Wars, Fred Star Wars, Dean StarWars, and Jason Hiver Whispers. Clustering methods for collaborative filtering.AAAI Press,1998.
[80] Marko Balabanovic′and Yoav Shoham. Fab: content-based, collaborative rec-ommendation. Communications of the ACM,40(3):66–72,1997.
[81] Gediminas Adomavicius and Er Tuzhilin. Toward the next generation of recom-mender systems: A survey of the state-of-the-art and possible extensions. IEEETransactions on Knowledge and Data Engineering,17:734–749,2005.
[82] Leo Iaquinta, Marco de Gemmis, Pasquale Lops, Giovanni Semeraro, MicheleFilannino, and Piero Molino. Introducing serendipity in a content-based recom-mender system. In HIS’08: Proceedings of the20088th International Con-ference on Hybrid Intelligent Systems, pages168–173, Washington, DC, USA,2008. IEEE Computer Society.
[83] Mei Kobayashi and Koichi Takeda. Information retrieval on the web. ACMComputing Surveys (CSUR),32(2):144–173,2000.
[84] Upendra Shardanand and Pattie Maes. Social information filtering: algorithmsfor automating “word of mouth”. In CHI’95: Proceedings of the SIGCHI con-ference on Human factors in computing systems, pages210–217, New York, NY,USA,1995. ACM Press/Addison-Wesley Publishing Co.
[85] Thomas Hofmann. Latent semantic models for collaborative filtering. ACMTrans. Inf. Syst.,22:89–115, January2004.
[86] Thomas Hofmann and Jan Puzicha. Latent class models for collaborative filter-ing. In Proceedings of the Sixteenth International Joint Conference on ArtificialIntelligence, IJCAI’99, pages688–693, San Francisco, CA, USA,1999. MorganKaufmann Publishers Inc.
[87] Thomas Hofmann. Probabilistic latent semantic indexing. In Proceedings of the22nd annual international ACM SIGIR conference on Research and developmentin information retrieval, SIGIR’99, pages50–57, New York, NY, USA,1999.ACM.
[88] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing onlarge clusters. Commun. ACM,51:107–113, January2008.
[89] Daniel Billsus and Michael J. Pazzani. Learning collaborative information filters.In Proceedings of the Fifteenth International Conference on Machine Learning,ICML’98, pages46–54, San Francisco, CA, USA,1998. Morgan KaufmannPublishers Inc.
[90] Badrul M. Sarwar, George Karypis, Joseph A. Konstan, and John T. Riedl. Ap-plication of dimensionality reduction in recommender system–a case study. InIN ACM WEBKDD WORKSHOP,2000.
[91] Yifan Hu, Y. Koren, and C. Volinsky. Collaborative filtering for implicit feed-back datasets. In Data Mining,2008. ICDM’08. Eighth IEEE InternationalConference on, pages263–272, dec.2008.
[92] Douglas W Oard and Jinmook Kim. Implicit Feedback for Recommender Sys-tems, pages81–83.1998.
[93] Daniel Lemire and Anna Maclachlan. Slope one predictors for online rating-based collaborative filtering. In SDM’05: Proceedings of the Fifth SIAM Inter-national Conference on Data Mining, pages471–475. SIAM,2005.
[94] Robert M. Bell and Yehuda Koren. Lessons from the netflix prize challenge.SIGKDD Explor. Newsl.,9:75–79, December2007.
[95] Robert Bell, Yehuda Koren, and Chris Volinsky. Modeling relationships at mul-tiple scales to improve accuracy of large recommender systems. In Proceedingsof the13th ACM SIGKDD international conference on Knowledge discovery anddata mining, KDD’07, pages95–104, New York, NY, USA,2007. ACM.
[96] R.M. Bell and Y. Koren. Scalable collaborative filtering with jointly derivedneighborhood interpolation weights. In Data Mining,2007. ICDM2007. SeventhIEEE International Conference on, pages43–52, oct.2007.
[97] Arkadiusz Paterek. Improving regularized singular value decomposition for col-laborative filtering. Statistics,2007:2–5.
[98] Jonathan L. Herlocker, Joseph A. Konstan, and John Riedl. Explaining collab-orative filtering recommendations. In Proceedings of the2000ACM conferenceon Computer supported cooperative work, CSCW’00, pages241–250, New Y-ork, NY, USA,2000. ACM.
[99] Yi Ding and Xue Li. Time weight collaborative filtering. In Proceedings of the14th ACM international conference on Information and knowledge management,CIKM’05, pages485–492, New York, NY, USA,2005. ACM.
[100] Yehuda Koren. Collaborative filtering with temporal dynamics. Commun. ACM,53:89–97, April2010.
[101] Murat G ksedef and Sule Gündüz güdücü. Integration of the pagerank algo-rithm into web recommendation system. In Ajith P. Abraham, editor, IADISEuropean Conference on Data Mining2008, Amsterdam, The Netherlands, July24-26,2008. Proceedings, pages19–28. IADIS,2008.
[102] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageR-ank citation ranking: Bringing order to the web. Technical Report1999-66,Stanford InfoLab, November1999. Previous number=SIDL-WP-1999-0120.
[103] Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recom-mender systems. IEEE Computer,42(8):30–37,2009.
[104] Sean M. McNee, John Riedl, and Joseph A. Konstan. Being accurate is notenough: how accuracy metrics have hurt recommender systems. In CHI’06extended abstracts on Human factors in computing systems, CHI EA’06, pages1097–1101, New York, NY, USA,2006. ACM.
[105] G. Takács, I. Pilászy, B. Németh, and D. Tikk. Investigation of various matrixfactorization methods for large recommender systems. In Proceedings of the2nd KDD Workshop on Large-Scale Recommender Systems and the Netflix PrizeCompetition, pages1–8. ACM,2008.
[106] P. Massa and P. Avesani. Trust-aware collaborative filtering for recommendersystems. On the Move to Meaningful Internet Systems2004: CoopIS, DOA, andODBASE, pages492–508,2004.
[107] P. Massa and P. Avesani. Trust-aware recommender systems. In Proceedings ofthe2007ACM conference on Recommender systems, page24. ACM,2007.
[108] S. Yoo, Y. Yang, F. Lin, and I.C. Moon. Mining social networks for personalizedemail prioritization. In Proceedings of the15th ACM SIGKDD internationalconference on Knowledge discovery and data mining, pages967–976. ACM,2009.
[109] Netflix. Netflix: Tv&movies instantly streamed online. http://www.netflix.com,August2010.
[110] R.M. Bell, J. Bennett, Y. Koren, and C. Volinsky. The million dollar program-ming prize. IEEE Spectrum,46(5):28–33,2009.
[111] M. E. J. Newman. The structure and function of complex networks. SIAMReview,45:167–256,2003.
[112] Linyuan Lü, Matus Medo, Chi Ho Yeung, Yi-Cheng Zhang, Zi-Ke Zhang, andTao Zhou. Recommender systems. Physics Reports,519(1):1–49,2012.
[113] Gediminas Adomavicius and Alexander Tuzhilin. Toward the next generation ofrecommender systems: A survey of the state-of-the-art and possible extensions.IEEE Transactions on Knowledge and Data Engineering,17(6):734–749,2005.
[114] Linyuan Lü and Weiping Liu. Information filtering via preferential diffusion.Phys. Rev. E,83:066119,2011.
[115] Tao Zhou, Ri-Qi Su, Run-Ran Liu, Luo-Luo Jiang, Bing-Hong Wang, and Yi-Cheng Zhang. Accurate and diverse recommendations via eliminating redundantcorrelations. New Journal of Physics,11(12):123008,2009.
[116] Tao Zhou, Jie Ren, Matú Medo, and Yi-Cheng Zhang. Bipartite network pro-jection and personal recommendation. Phys. Rev. E,76:046115,2007.
[117] T. Zhou, L.-L. Jiang, R.-Q. Su, and Y.-C. Zhang. Effect of initial configurationon network-based recommendation. EPL (Europhysics Letters),81(5):58004,2008.
[118] Sergei Maslov and Yi-Cheng Zhang. Extracting hidden information from knowl-edge networks. Phys. Rev. Lett.,87(24):248701,2001.
[119] J Barre. Retrieving information from a noisy’knowledge network’. Journal ofStatistical Mechanics: Theory and Experiment,2007(08):P08015,2007.
[120] Jie Ren, Tao Zhou, and Yi-Cheng Zhang. Information filtering via self-consistentrefinement. EPL (Europhysics Letters),82(5):58007,2008.
[121] T. Zhou, Z. Kuscsik, J.G. Liu, M. Medo, J.R. Wakeling, and Y.C. Zhang. Solvingthe apparent diversity-accuracy dilemma of recommender systems. Proceedingsof the National Academy of Sciences of the USA,107(10):4511–4515,2010.
[122] Yi-Cheng Zhang, Marcel Blattner, and Yi-Kuo Yu. Heat conduction process oncommunity networks as a recommendation model. Phys. Rev. Lett.,99:154301,2007.
[123] Paul Jaccard. étude comparative de la distribution florale dans une portion desalpes et des jura. Bulletin del la Société Vaudoise des Sciences Naturelles,37:547–579,1901.
[124] F. Meyer L. Candillier and F. Fessant. Designing specific weighted similaritymeasures to improve collaborative filtering systems. In Advances in Data Min-ing: Medical Applications, E-Commerce, Marketing, and Theoretical Aspects,pages242–255,2008.
[125] Claudio Castellano, Santo Fortunato, and Vittorio Loreto. Statistical physics ofsocial dynamics. Rev. Mod. Phys.,81:591–646,2009.
[126] Dietrich Stauffer. Introduction to statistical physics outside physics. Physica A:Statistical and Theoretical Physics,336:1–5,2004.
[127] Gy rgy Szabó and Gábor Fáth. Evolutionary games on graphs. Phys. Rep.,446:97–216,2007.
[128] Peter Clifford and Aidan Sudbury. A model for spatial conflict. Biometrika,60:581–588,1973.
[129] Thomas M. Liggett. Stochastic interacting systems: contact, voter, and exclusionprocesses, volume324. Springer, Berlin Heidelberg New York,1999.
[130] V. Sood and S. Redner. Voter model on heterogeneous graphs. Phys. Rev. Lett.,94:178701, May2005.
[131] Víctor M. Eguíluz Krzysztof Suchecki and Maxi San Miguel. Voter model dy-namics in complex networks: Role of dimensionality, disorder, and degree dis-tribution. Phys. Rev. E,72:036132, Sep2005.
[132] F Vazquez and S Redner. Ultimate fate of constrained voters. Journal of PhysicsA: Mathematical and General,37(35):8479,2004.
[133] A. Baronchelli, C. Castellano, and R. Pastor-Satorras. Voter models on weightednetworks. Phys. Rev. E,83:066117,2011.
[134] Paolo Moretti, Andrea Baronchelli, Michele Starnini, and Romualdo Pastor-Satorras. Generalized voter-like models on heterogeneous networks. CoRR,abs/1206.3037,2012.
[135] Serge Galam. Minority opinion spreading in random geometry. The EuropeanPhysical Journal B,25:403–406,2002.
[136] P. L. Krapivsky and S. Redner. Dynamics of majority rule in two-state interactingspin systems. Phys. Rev. Lett.,90:238701, Jun2003.
[137] B. Lantané. The psychology of social impact. American Psychologist,36:343–356,1981.
[138] A. Nowak, B. Latane, and J. Szamrej. From private attitude to public opinion: Adynamic theory of social impact. Psychological Review,97:362–376,1990.
[139] Andrzej Nowak, Marek Kus, Jakub Urbaniak, and Tomasz Zarycki. Simulat-ing the coordination of individual economic decisions. Physica A: StatisticalMechanics and its Applications,287:613–630,2000.
[140] Serge Galam. Contrarian deterministic effects on opinion dynamics:"the hungelections scenario". Physica A: Statistical and Theoretical Physics,333:453–460,2004.
[141] Serge Galam. The dynamics of minority opinions in democratic debate. PhysicaA: Statistical and Theoretical Physics,336:56–62,2004.
[142] Guillaume Deffuant, FrWdWric Amblard, GWrard Weisbuch, and Thierry Faure.How can extremism prevail? a study based on the relative agreement interactionmodel. Journal of Artificial Societies and Social Simulation,5(4):1,2002.
[143] Guillaume Deffuant, David Neau, Frederic Amblard, and GWrard Weisbuch.Mixing beliefs among interacting agents. Adv. Complex Syst.,3:87–98,2000.
[144] Rainer Hegselmann and Ulrich Krause. Opinion dynamics and bounded confi-dence, models, analysis and simulation. Journal of Artificial Societies and SocialSimulation,5(3):2,2002.
[145] André C. R. Martins. Continuous opinions and discrete actions in opinion dy-namics problems. Int. Journal of Modern Physics C,19(4):617–624,2008.
[146] C. Pereira A. C. R. Martins and R. Vicente. An opinion dynamics model for thediffusion of innovations. Physica A,388:3225–3232,2000.
[147] Sznajd-Weron Katarzyna and Jósef Sznajd. Opinion evolution in closed com-munity. Int. Journal of Modern Physics C,11:1157–1165,2000.
[148] A. T. Bernardes, D. Stauffer, and J. Kertész. Election results and the sznajd mod-el on barabasi network. The European Physical Journal B-Condensed Matter,25:123–127,2002.
[149] D. Stauffer. Sociophysics simulations II: opinion dynamics. AIP ConferenceProceedings,779:56,2005.
[150] J. K. Shin. Information accumulation system by inheritance and diffusion. Phys-ica A: Statistical Mechanics and its Applications,388(17):3593–3599,2009.
[151] Joshua M Epstein. Generative social science: Studies in agent–based computa-tional modeling. Princeton University Press, Princeton, NJ,2006.
[152] Mohammad Afshar and Masoud Asadpour. Opinion formation by informed a-gents. J. Artificial Societies and Social Simulation,13(4):5,2010.
[153] M. Perc and A. Szolnoki. Coevolutionary games–a mini review. BioSystems,99:109–125,2010.
[154] Christian Borghesi and Serge Galam. Chaotic, staggered, and polarized dynam-ics in opinion forming: The contrarian effect. Phys. Rev. E,73:066118, Jun2006.
[155] Alejandro D. SSnchez, Juan M. L_pez, and Miguel A. Rodr[guez. Nonequi-librium phase transitions in directed small-world networks. Phys. Rev. Lett.,88:048701,2002.
[156] J. M. López M. S. de la Lama and H. S. Wio. Spontaneous emergence ofcontrarian-like behaviour in an opinion spreading model. EPL (Europhysics Let-ters),72(5):851,2005.
[157] Luo-luo Jiang, Da-yin Hua, and Ting Chen. Nonequilibrium phase transitionsin a model with social influence of inflexible units. J. Phys. A: Math. Theor.,40:11271,2007.
[158] Petter Holme and M. E. Newman. Nonequilibrium phase transition in the coevo-lution of networks and opinions. Phys. Rev. E,74:056108,2006.
[159] B. Schmittmann and Abhishek Mukhopadhyay. Opinion formation on adaptivenetworks with intensive average degree. Physical Review E,82(6):1–7,2010.
[160] I. J. Benczik, S. Z. Benczik, B. Schmittmann, and R. K. P. Zia. Opinion dynamicson an adaptive random network. Phys. Rev. E,79:046104,2009.
[161] Luo-Luo. Jiang, D. Hua, J. Zhu, B. Wang, and T. Zhou. Opinion dynamics ondirected small-world networks. Eur. Phys. J. B,65:251–255,2008.
[162] Xenofontas Dimitropoulos, Dmitri Krioukov, Amin Vahdat, and George Riley.Graph annotations in modeling complex network topologies. ACM Trans. Model.Comput. Simul.,19:(17)1–29,2009.
[163] M. E. J. Newman G. T. Barkema. Monte Carlo Methods in Statistical Physics.Oxford Uinversity Press, London,1999.
[164] D. P. Landau and K. Binder. A Guide to Monte Carlo Simulations in StatisticalPhysics. Cambridge University Press, Cambridge,2005.
[165] R. Pastor-Satorras and A. Vespignani. Evolution and Structure of the Internet:A Statistical Physics Approach. Cambridge University Press, New York, NY,USA,2004.
[166] Alejandro D. Sánchez, Juan M. López, and Miguel A. Rodríguez. Nonequi-librium phase transitions in directed small-world networks. Phys. Rev. Lett.,88:048701,2002.
[167] A. Szolnoki, G. Szabó, and M. Perc. Phase diagrams for the spatial public goodsgame with pool punishment. Phys. Rev. E,83:036101,2011.
[168] F. Fu and L. Wang. Coevolutionary dynamics of opinions and networks: Fromdiversity to uniformity. Phys. Rev. E,78:016104,2008.
[169] G. I iguez, J. Kertész, K. K. Kaski, and R. A. Barrio. Opinion and communityformation in coevolving networks. Phys. Rev. E,80:066119,2009.
[170] G. I iguez, J. Kertész, K. K. Kaski, and R. A. Barrio. Phase change in an opinion-dynamics model with separation of time scales. Phys. Rev. E,83:016111,2011.
[171] Petter Holme and Jari Saram ki. Temporal networks. Physics Reports,519(3):97–125,2012.
[172] Leon Danon, Ashley P Ford, Thomas House, Chris P Jewell, Matt J Keeling,Gareth O Roberts, Joshua V Ross, and Matthew C Vernon. Networks and theepidemiology of infectious disease. Interdisciplinary perspectives on infectiousdiseases,2011:284909,2011.
[173] H. H. K. Lentz, T. Selhorst, and I. M Sokolov. Unfolding accessibility providesa macroscopic approach to temporal networks. Arxiv preprint arXiv:1210.2283,October2012.
[174] S. Liu, A. Baronchelli, and N. Perra. Contagion dynamics in time-varyingmetapopulation networks. Arxiv preprint arXiv:1210.2776, October2012.
[175] R. O. dos Santos Soares and A. S. Martinez. The geometrical patterns of cooper-ation evolution in the spatial prisoner’s dilemma: An intra-group model. PhysicaA,369:823–829,2006.
[176] M. dos Santos, D. J. Rankin, and C. Wedekind. The evolution of punishmentthrough reputation. Proc. R. Soc. B,278:371–377,2011.
[177] Yu Zheng and Xiaofang Zhou, editors. Location-Based Social Networks: Users.Springer,2011.
[178] Yu Zheng, Lizhu Zhang, Zhengxin Ma, Xing Xie, and Wei-Ying Ma. Recom-mending friends and locations based on individual location history. ACM Trans-actions on the Web,5(1):5:1–44,2011.
[179] Yu Zheng and Xing Xie. Learning travel recommendations from user-generatedgps traces. ACM Transactions on Intelligent Systems and Technology,2(1):2,2011.
[180] Eunjoon Cho, Seth A. Myers, and Jure Leskovec. Friendship and mobility: usermovement in location-based social networks. In Chid AptW, Joydeep Ghosh, andPadhraic Smyth, editors, Proceedings of the17th ACM SIGKDD internationalconference on Knowledge discovery and data mining, pages1082–1090. ACM,2011.
[181] Yu Zheng and Xing Xie. Reviews of lbsn. http://research.microsoft.com/en-us/projects/lbsn, January2013.
[2] D. J. Watts and S. H. Strogatz. Collective dynamics of’small world’ networks.Nature,393:440–442,1998.
[3] R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Rev.Mod. Phys.,74:47–97,2002.
[4] Steven H. Strogatz. Exploring complex networks. Nature,410:268–276,2001.
[5] Duncan J. Watts. Networks, dynamics, and the small-world phenomenon. Am.J. Soc.,105:493–527,1999.
[6] A.-L. Barabási and Z. N. Oltvai. Network biology: understanding the cell’sfunctional organization. Nature Reviews Genetics,5:101–113,2004.
[7] Jon M. Kleinberg. Navigation in a small world. Nature,406(6798):845,2000.
[8] Qian Chen, Hyunseok Chang, Ramesh Govindan, Sugih Jamin, Scott Shenker,and Walter Willinger. The origin of power-laws in internet topologies revisited.pages608–617,2002.
[9] Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-lawrelationships of the internet topology. Comp. Comm. Rev.,29:251–262,1999.
[10] Alexei Vázquez, Romualdo Pastor-Satorras, and Alessandro Vespignani. Large-scale topological and dynamical properties of the internet. Phys. Rev. E,65:066130,2002.
[11] H. Jeong, S. Mason, A.-L. Barabási, and Z. N. Oltvai. Lethality and centrality inprotein networks. Nature,411:41–42,2001.
[12] H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási. The large-scaleorganization of metabolic networks. Nature,407:651–654,2000.
[13] Rodrigo De Castro and Jerrold W. Grossman. Famous trails to Paul Erdo s. Math.Intel.,21:51–53,1999.
[14] M. E. J. Newman. Scientific collaboration networks: I. Network constructionand fundamental results. Phys. Rev. E,64:016131,2001.
[15] M. E. J. Newman. The structure of scientific collaboration networks. PNAS,98:404–409,2001.
[16] M. Huxham, S. Beaney, and D. Raffaelli. Do parasites reduce the chances oftriangulation in a real food web? Oikos,76:284–300,1996.
[17] Guido Boella, Leendert van der Torre, and Serena Villata. Four measures for thedynamics of coalitions in social networks. pages361–362. ACM,2009.
[18] Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, andBobby Bhattacharjee. Measurement and analysis of online social networks. InProceedings of the7th ACM SIGCOMM conference on Internet measurement,IMC’07, pages29–42. ACM,2007.
[19] Sheng Yu and Subhash Kak. A survey of prediction using social media. CoRR,abs/1203.1647,2012.
[20] P. Erdo s and A. Rényi. On random graphs. Pub. Math.,6:290–297,1959.
[21] P. Erdo s and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad.Mat. Kutató Int. K zl.,5:17–61,1960.
[22] Santo Fortunato. Community detection in graphs. Physics Reports,486(3-5):75–174,2010.
[23] Jierui Xie, Stephen Kelley, and B. K. Szymanski. Overlapping community de-tection in networks: the state of the art and comparative study. ACM ComputingSurveys,45(4),2013.
[24] M. Girvan and M. E. J. Newman. Community structure in social and biologicalnetworks. Proceedings of the National Academy of Sciences,99(12):7821–7826,2002.
[25] M. E. J. Newman. Analysis of weighted networks. Phys. Rev. E,70:056131,2004.
[26] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi. Defining andidentifying communities in networks. Proceedings of the National Academy ofSciences,101(9):2658,2004.
[27] M E Newman. Modularity and community structure in networks. Proceed-ings of the National Academy of Sciences of the United States of America,103(23):8577–8582,2006.
[28] S.E. Schaeffer. Graph clustering. Computer Science Review,1(1):27–64,2007.
[29] Aaron Clauset, Cristopher Moore, and M. E. J. Newman. Hierarchical structureand the prediction of missing links in networks. Nature,453:98–101,2008.
[30] Martin Rosvall and Carl T. Bergstrom. Maps of random walks on complex net-works reveal community structure. Proceedings of the National Academy ofSciences,105(4):1118–1123,2008.
[31] Junhua Zhang, Shihua Zhang, and Xiang-Sun Zhang. Detecting communitystructure in complex networks based on a measure of information discrepancy.Physica A: Statistical Mechanics and its Applications,387(7):1675–1682,2008.
[32] J rg Reichardt and Stefan Bornholdt. Detecting fuzzy community structures incomplex networks with a potts model. Phys. Rev. Lett.,93:218701, Nov2004.
[33] I Ispolatov, I Mazo, and A Yuryev. Finding mesoscopic communities in s-parse networks. Journal of Statistical Mechanics: Theory and Experiment,2006(09):P09014,2006.
[34] Pascal Pons and Matthieu Latapy. Computing communities in large networksusing random walks. volume3733of Lecture Notes in Computer Science, pages284–293. Springer,2005.
[35] Zhenping Li, Shihua Zhang, Rui-Sheng Wang, Xiang-Sun Zhang, and LuonanChen. Quantitative function for community detection. Phys. Rev. E,77:036109,Mar2008.
[36] Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek. Uncovering theoverlapping community structure of complex networks in nature and society.Nature,435(7043):814–818, June2005.
[37] Imre Derényi, Gergely Palla, and Tamás Vicsek. Clique percolation in randomnetworks. Phys. Rev. Lett.,94:160202, Apr2005.
[38] Balázs Adamcsek, Gergely Palla, Illés J. Farkas, Imre Derényi, and Tamás Vic-sek. Cfinder: locating cliques and overlapping modules in biological networks.Bioinformatics,22(8):1021–1023,2006.
[39] Ginestra Bianconi. The entropy of randomized network ensembles. EurophysicsLetters,81(2):28005,2008.
[40] U. Brandes, D. Delling, M. Gaertler, R. G rke, M. Hoefer, Z. Nikoloski, and D.Wagner. On finding graph clusterings with maximum modularity. In Graph-Theoretic Concepts in Computer Science, pages121–132. Springer,2007.
[41] V. Arnau, S. Mars, and I. Marín. Iterative cluster analysis of protein interactiondata. Bioinformatics,21(3):364–378,2005.
[42] R. Aldecoa and I. Marín. Deciphering network community structure by surprise.PloS one,6(9):e24195,2011.
[43] A. Lancichinetti, S. Fortunato, and F. Radicchi. Benchmark graphs for testingcommunity detection algorithms. Physical Review E,78(4):046110,2008.
[44] A. Lancichinetti and S. Fortunato. Community detection algorithms: a compar-ative analysis. Physical Review E,80(5):056117,2009.
[45] R. Aldecoa and I. Marín. Jerarca: Efficient analysis of complex networks usinghierarchical clustering. PloS one,5(7):e11585,2010.
[46] U. Von Luxburg. A tutorial on spectral clustering. Statistics and computing,17(4):395–416,2007.
[47] A.Y. Ng, M.I. Jordan, Y. Weiss, et al. On spectral clustering: Analysis andan algorithm. Advances in neural information processing systems,2:849–856,2002.
[48] M. Rosvall and C.T. Bergstrom. Maps of random walks on complex networksreveal community structure. Proceedings of the National Academy of Sciences,105(4):1118–1123,2008.
[49] V.D. Blondel, J.L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding ofcommunities in large networks. Journal of Statistical Mechanics: Theory andExperiment,2008(10):P10008,2008.
[50] P. Ronhovde and Z. Nussinov. Multiresolution community detection for megas-cale networks by information-based replica correlations. Physical Review E,80(1):016109,2009.
[51] C.P. Massen and J.P.K. Doye. Thermodynamics of community structure.Preprint arXiv:cond-mat/0610077,2006.
[52] J. A. Hartigan. Bloc voting in the united states senate. Journal of Classification,17(1):29–49,2000.
[53] W O Kermack; A G McKendrick. A contribution to the mathematical theoryof epidemics. Proceedings of the Royal Society A: Mathematical, Physical andEngineering Science,115:700–721,1927.
[54] Michael B. A. Oldstone. Viruses, Plagues, and History: Past, Present and Fu-ture. Oxford University Press,2009.
[55] Charles F. Manski. Vaccination with partial knowledge of external effectiveness.107.
[56] Jan Medlock and Alison P. Galvani1. Vaccination with partial knowledge ofexternal effectiveness. Science,325:1705–1708,2009.
[57] Alison L. Hill, David G. Rand, Martin A. Nowak, and Nicholas A. Christakis.Infectious disease modeling of social contagion in networks. PLoS Comput Biol,6(11):e1000968,2010.
[58] D. J. DALEY and D. G. KENDALL. Stochastic rumours. Ima Journal of AppliedMathematics,1(1):42–55,1965.
[59] D. J. DALEY and D. G. KENDALL. Epidemics and rumours. Nature,204(4963):1118–1118,1964.
[60] A. McCallum, X. Wang, and A. Corrada-Emmanuel. Topic and role discoveryin social networks with experiments on enron and academic email. Journal ofArtificial Intelligence Research,30:249–272,2007.
[61] Allan J. Kimmel. Rumors and Rumor Control: A Manager’s Guide to Under-standing and Combatting Rumors. Lawrence Erlbaum Associates,2003.
[62] Y. Moreno, R. Pastor-Satorras, and A. Vespignani. Epidemic outbreaks in com-plex heterogeneous networks. The European Physical Journal B-CondensedMatter and Complex Systems,26:521–529,2002.10.1140/epjb/e20020122.
[63] M. Nekovee, Y. Moreno, G. Bianconi, and M. Marsili. Theory of rumour spread-ing in complex social networks. Physica A: Statistical Mechanics and its Appli-cations,374(1):457–470,2007.
[64] Sebastián Risau-Gusman and Damián H Zanette. Contact switching as a controlstrategy for epidemic outbreaks. Journal of Theoretical Biology,257(1):52–60,March2009.
[65] Claudio Castellano, Santo Fortunato, and Vittorio Loreto. Statistical physics ofsocial dynamics. Rev. Mod. Phys.,81:591–646,2009.
[66] Adam Kleczkowski and Bryan T. Grenfell. Mean-field-type equations for spreadof epidemics: the [‘]small world’ model. Physica A: Statistical Mechanics andits Applications,274(1-2):355–360,1999.
[67] Jaewook Joo and Joel L. Lebowitz. Behavior of susceptible-infected-susceptibleepidemics on heterogeneous networks with saturation. Phys. Rev. E,69:066105,2004.
[68] J. Gani D. Daley and J. Gani. Epidemic Modelling: An Introduction. CambridgeUniversity Press,2001.
[69] M. Nekovee, Y. Moreno, G. Bianconi, and M. Marsili. Theory of rumour spread-ing in complex social networks. Physica A: Statistical Mechanics and its Appli-cations,374(1):457–470,2007.
[70] G. Linden, B. Smith, and J. York. Amazon.com recommendations: item-to-itemcollaborative filtering. Internet Computing, IEEE,7(1):76–80, jan/feb2003.
[71] Abhinandan S. Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram. Googlenews personalization: scalable online collaborative filtering. In Proceedings ofthe16th international conference on World Wide Web, WWW’07, pages271–280, New York, NY, USA,2007. ACM.
[72] G. Adomavicius and A. Tuzhilin. Toward the next generation of recommendersystems: a survey of the state-of-the-art and possible extensions. Knowledge andData Engineering, IEEE Transactions on,17(6):734–749, june2005.
[73] Marko Balabanovic′and Yoav Shoham. Fab: content-based, collaborative rec-ommendation. Commun. ACM,40:66–72, March1997.
[74] Thomas Hofmann. Collaborative filtering via gaussian probabilistic latent se-mantic analysis. In Proceedings of the26th annual international ACM SIGIRconference on Research and development in informaion retrieval, SIGIR’03,pages259–266, New York, NY, USA,2003. ACM.
[75] Yehuda Koren. Factorization meets the neighborhood: a multifaceted collabo-rative filtering model. In Proceedings of the14th ACM SIGKDD internationalconference on Knowledge discovery and data mining, KDD’08, pages426–434,New York, NY, USA,2008. ACM.
[76] John S. Breese, David Heckerman, and Carl Myers Kadie. Empirical analysisof predictive algorithms for collaborative filtering. In Gregory F. Cooper andSeraf[n Moral, editors, UAI, pages43–52. Morgan Kaufmann,1998.
[77] David M. Pennock, Eric Horvitz, Steve Lawrence, and C. Lee Giles. Collab-orative filtering by personality diagnosis: A hybrid memory and model-basedapproach. In Craig Boutilier and MoisWs Goldszmidt, editors, UAI, pages473–480. Morgan Kaufmann,2000.
[78] Paul Resnick, Neophytos Iacovou, Mitesh Suchak, Peter Bergstrom, and JohnRiedl. Grouplens: an open architecture for collaborative filtering of netnews. InProceedings of the1994ACM conference on Computer supported cooperativework, CSCW’94, pages175–186, New York, NY, USA,1994. ACM.
[79] Lyle Ungar, Dean Foster, Ellen Andre, Star Wars, Fred Star Wars, Dean StarWars, and Jason Hiver Whispers. Clustering methods for collaborative filtering.AAAI Press,1998.
[80] Marko Balabanovic′and Yoav Shoham. Fab: content-based, collaborative rec-ommendation. Communications of the ACM,40(3):66–72,1997.
[81] Gediminas Adomavicius and Er Tuzhilin. Toward the next generation of recom-mender systems: A survey of the state-of-the-art and possible extensions. IEEETransactions on Knowledge and Data Engineering,17:734–749,2005.
[82] Leo Iaquinta, Marco de Gemmis, Pasquale Lops, Giovanni Semeraro, MicheleFilannino, and Piero Molino. Introducing serendipity in a content-based recom-mender system. In HIS’08: Proceedings of the20088th International Con-ference on Hybrid Intelligent Systems, pages168–173, Washington, DC, USA,2008. IEEE Computer Society.
[83] Mei Kobayashi and Koichi Takeda. Information retrieval on the web. ACMComputing Surveys (CSUR),32(2):144–173,2000.
[84] Upendra Shardanand and Pattie Maes. Social information filtering: algorithmsfor automating “word of mouth”. In CHI’95: Proceedings of the SIGCHI con-ference on Human factors in computing systems, pages210–217, New York, NY,USA,1995. ACM Press/Addison-Wesley Publishing Co.
[85] Thomas Hofmann. Latent semantic models for collaborative filtering. ACMTrans. Inf. Syst.,22:89–115, January2004.
[86] Thomas Hofmann and Jan Puzicha. Latent class models for collaborative filter-ing. In Proceedings of the Sixteenth International Joint Conference on ArtificialIntelligence, IJCAI’99, pages688–693, San Francisco, CA, USA,1999. MorganKaufmann Publishers Inc.
[87] Thomas Hofmann. Probabilistic latent semantic indexing. In Proceedings of the22nd annual international ACM SIGIR conference on Research and developmentin information retrieval, SIGIR’99, pages50–57, New York, NY, USA,1999.ACM.
[88] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing onlarge clusters. Commun. ACM,51:107–113, January2008.
[89] Daniel Billsus and Michael J. Pazzani. Learning collaborative information filters.In Proceedings of the Fifteenth International Conference on Machine Learning,ICML’98, pages46–54, San Francisco, CA, USA,1998. Morgan KaufmannPublishers Inc.
[90] Badrul M. Sarwar, George Karypis, Joseph A. Konstan, and John T. Riedl. Ap-plication of dimensionality reduction in recommender system–a case study. InIN ACM WEBKDD WORKSHOP,2000.
[91] Yifan Hu, Y. Koren, and C. Volinsky. Collaborative filtering for implicit feed-back datasets. In Data Mining,2008. ICDM’08. Eighth IEEE InternationalConference on, pages263–272, dec.2008.
[92] Douglas W Oard and Jinmook Kim. Implicit Feedback for Recommender Sys-tems, pages81–83.1998.
[93] Daniel Lemire and Anna Maclachlan. Slope one predictors for online rating-based collaborative filtering. In SDM’05: Proceedings of the Fifth SIAM Inter-national Conference on Data Mining, pages471–475. SIAM,2005.
[94] Robert M. Bell and Yehuda Koren. Lessons from the netflix prize challenge.SIGKDD Explor. Newsl.,9:75–79, December2007.
[95] Robert Bell, Yehuda Koren, and Chris Volinsky. Modeling relationships at mul-tiple scales to improve accuracy of large recommender systems. In Proceedingsof the13th ACM SIGKDD international conference on Knowledge discovery anddata mining, KDD’07, pages95–104, New York, NY, USA,2007. ACM.
[96] R.M. Bell and Y. Koren. Scalable collaborative filtering with jointly derivedneighborhood interpolation weights. In Data Mining,2007. ICDM2007. SeventhIEEE International Conference on, pages43–52, oct.2007.
[97] Arkadiusz Paterek. Improving regularized singular value decomposition for col-laborative filtering. Statistics,2007:2–5.
[98] Jonathan L. Herlocker, Joseph A. Konstan, and John Riedl. Explaining collab-orative filtering recommendations. In Proceedings of the2000ACM conferenceon Computer supported cooperative work, CSCW’00, pages241–250, New Y-ork, NY, USA,2000. ACM.
[99] Yi Ding and Xue Li. Time weight collaborative filtering. In Proceedings of the14th ACM international conference on Information and knowledge management,CIKM’05, pages485–492, New York, NY, USA,2005. ACM.
[100] Yehuda Koren. Collaborative filtering with temporal dynamics. Commun. ACM,53:89–97, April2010.
[101] Murat G ksedef and Sule Gündüz güdücü. Integration of the pagerank algo-rithm into web recommendation system. In Ajith P. Abraham, editor, IADISEuropean Conference on Data Mining2008, Amsterdam, The Netherlands, July24-26,2008. Proceedings, pages19–28. IADIS,2008.
[102] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageR-ank citation ranking: Bringing order to the web. Technical Report1999-66,Stanford InfoLab, November1999. Previous number=SIDL-WP-1999-0120.
[103] Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recom-mender systems. IEEE Computer,42(8):30–37,2009.
[104] Sean M. McNee, John Riedl, and Joseph A. Konstan. Being accurate is notenough: how accuracy metrics have hurt recommender systems. In CHI’06extended abstracts on Human factors in computing systems, CHI EA’06, pages1097–1101, New York, NY, USA,2006. ACM.
[105] G. Takács, I. Pilászy, B. Németh, and D. Tikk. Investigation of various matrixfactorization methods for large recommender systems. In Proceedings of the2nd KDD Workshop on Large-Scale Recommender Systems and the Netflix PrizeCompetition, pages1–8. ACM,2008.
[106] P. Massa and P. Avesani. Trust-aware collaborative filtering for recommendersystems. On the Move to Meaningful Internet Systems2004: CoopIS, DOA, andODBASE, pages492–508,2004.
[107] P. Massa and P. Avesani. Trust-aware recommender systems. In Proceedings ofthe2007ACM conference on Recommender systems, page24. ACM,2007.
[108] S. Yoo, Y. Yang, F. Lin, and I.C. Moon. Mining social networks for personalizedemail prioritization. In Proceedings of the15th ACM SIGKDD internationalconference on Knowledge discovery and data mining, pages967–976. ACM,2009.
[109] Netflix. Netflix: Tv&movies instantly streamed online. http://www.netflix.com,August2010.
[110] R.M. Bell, J. Bennett, Y. Koren, and C. Volinsky. The million dollar program-ming prize. IEEE Spectrum,46(5):28–33,2009.
[111] M. E. J. Newman. The structure and function of complex networks. SIAMReview,45:167–256,2003.
[112] Linyuan Lü, Matus Medo, Chi Ho Yeung, Yi-Cheng Zhang, Zi-Ke Zhang, andTao Zhou. Recommender systems. Physics Reports,519(1):1–49,2012.
[113] Gediminas Adomavicius and Alexander Tuzhilin. Toward the next generation ofrecommender systems: A survey of the state-of-the-art and possible extensions.IEEE Transactions on Knowledge and Data Engineering,17(6):734–749,2005.
[114] Linyuan Lü and Weiping Liu. Information filtering via preferential diffusion.Phys. Rev. E,83:066119,2011.
[115] Tao Zhou, Ri-Qi Su, Run-Ran Liu, Luo-Luo Jiang, Bing-Hong Wang, and Yi-Cheng Zhang. Accurate and diverse recommendations via eliminating redundantcorrelations. New Journal of Physics,11(12):123008,2009.
[116] Tao Zhou, Jie Ren, Matú Medo, and Yi-Cheng Zhang. Bipartite network pro-jection and personal recommendation. Phys. Rev. E,76:046115,2007.
[117] T. Zhou, L.-L. Jiang, R.-Q. Su, and Y.-C. Zhang. Effect of initial configurationon network-based recommendation. EPL (Europhysics Letters),81(5):58004,2008.
[118] Sergei Maslov and Yi-Cheng Zhang. Extracting hidden information from knowl-edge networks. Phys. Rev. Lett.,87(24):248701,2001.
[119] J Barre. Retrieving information from a noisy’knowledge network’. Journal ofStatistical Mechanics: Theory and Experiment,2007(08):P08015,2007.
[120] Jie Ren, Tao Zhou, and Yi-Cheng Zhang. Information filtering via self-consistentrefinement. EPL (Europhysics Letters),82(5):58007,2008.
[121] T. Zhou, Z. Kuscsik, J.G. Liu, M. Medo, J.R. Wakeling, and Y.C. Zhang. Solvingthe apparent diversity-accuracy dilemma of recommender systems. Proceedingsof the National Academy of Sciences of the USA,107(10):4511–4515,2010.
[122] Yi-Cheng Zhang, Marcel Blattner, and Yi-Kuo Yu. Heat conduction process oncommunity networks as a recommendation model. Phys. Rev. Lett.,99:154301,2007.
[123] Paul Jaccard. étude comparative de la distribution florale dans une portion desalpes et des jura. Bulletin del la Société Vaudoise des Sciences Naturelles,37:547–579,1901.
[124] F. Meyer L. Candillier and F. Fessant. Designing specific weighted similaritymeasures to improve collaborative filtering systems. In Advances in Data Min-ing: Medical Applications, E-Commerce, Marketing, and Theoretical Aspects,pages242–255,2008.
[125] Claudio Castellano, Santo Fortunato, and Vittorio Loreto. Statistical physics ofsocial dynamics. Rev. Mod. Phys.,81:591–646,2009.
[126] Dietrich Stauffer. Introduction to statistical physics outside physics. Physica A:Statistical and Theoretical Physics,336:1–5,2004.
[127] Gy rgy Szabó and Gábor Fáth. Evolutionary games on graphs. Phys. Rep.,446:97–216,2007.
[128] Peter Clifford and Aidan Sudbury. A model for spatial conflict. Biometrika,60:581–588,1973.
[129] Thomas M. Liggett. Stochastic interacting systems: contact, voter, and exclusionprocesses, volume324. Springer, Berlin Heidelberg New York,1999.
[130] V. Sood and S. Redner. Voter model on heterogeneous graphs. Phys. Rev. Lett.,94:178701, May2005.
[131] Víctor M. Eguíluz Krzysztof Suchecki and Maxi San Miguel. Voter model dy-namics in complex networks: Role of dimensionality, disorder, and degree dis-tribution. Phys. Rev. E,72:036132, Sep2005.
[132] F Vazquez and S Redner. Ultimate fate of constrained voters. Journal of PhysicsA: Mathematical and General,37(35):8479,2004.
[133] A. Baronchelli, C. Castellano, and R. Pastor-Satorras. Voter models on weightednetworks. Phys. Rev. E,83:066117,2011.
[134] Paolo Moretti, Andrea Baronchelli, Michele Starnini, and Romualdo Pastor-Satorras. Generalized voter-like models on heterogeneous networks. CoRR,abs/1206.3037,2012.
[135] Serge Galam. Minority opinion spreading in random geometry. The EuropeanPhysical Journal B,25:403–406,2002.
[136] P. L. Krapivsky and S. Redner. Dynamics of majority rule in two-state interactingspin systems. Phys. Rev. Lett.,90:238701, Jun2003.
[137] B. Lantané. The psychology of social impact. American Psychologist,36:343–356,1981.
[138] A. Nowak, B. Latane, and J. Szamrej. From private attitude to public opinion: Adynamic theory of social impact. Psychological Review,97:362–376,1990.
[139] Andrzej Nowak, Marek Kus, Jakub Urbaniak, and Tomasz Zarycki. Simulat-ing the coordination of individual economic decisions. Physica A: StatisticalMechanics and its Applications,287:613–630,2000.
[140] Serge Galam. Contrarian deterministic effects on opinion dynamics:"the hungelections scenario". Physica A: Statistical and Theoretical Physics,333:453–460,2004.
[141] Serge Galam. The dynamics of minority opinions in democratic debate. PhysicaA: Statistical and Theoretical Physics,336:56–62,2004.
[142] Guillaume Deffuant, FrWdWric Amblard, GWrard Weisbuch, and Thierry Faure.How can extremism prevail? a study based on the relative agreement interactionmodel. Journal of Artificial Societies and Social Simulation,5(4):1,2002.
[143] Guillaume Deffuant, David Neau, Frederic Amblard, and GWrard Weisbuch.Mixing beliefs among interacting agents. Adv. Complex Syst.,3:87–98,2000.
[144] Rainer Hegselmann and Ulrich Krause. Opinion dynamics and bounded confi-dence, models, analysis and simulation. Journal of Artificial Societies and SocialSimulation,5(3):2,2002.
[145] André C. R. Martins. Continuous opinions and discrete actions in opinion dy-namics problems. Int. Journal of Modern Physics C,19(4):617–624,2008.
[146] C. Pereira A. C. R. Martins and R. Vicente. An opinion dynamics model for thediffusion of innovations. Physica A,388:3225–3232,2000.
[147] Sznajd-Weron Katarzyna and Jósef Sznajd. Opinion evolution in closed com-munity. Int. Journal of Modern Physics C,11:1157–1165,2000.
[148] A. T. Bernardes, D. Stauffer, and J. Kertész. Election results and the sznajd mod-el on barabasi network. The European Physical Journal B-Condensed Matter,25:123–127,2002.
[149] D. Stauffer. Sociophysics simulations II: opinion dynamics. AIP ConferenceProceedings,779:56,2005.
[150] J. K. Shin. Information accumulation system by inheritance and diffusion. Phys-ica A: Statistical Mechanics and its Applications,388(17):3593–3599,2009.
[151] Joshua M Epstein. Generative social science: Studies in agent–based computa-tional modeling. Princeton University Press, Princeton, NJ,2006.
[152] Mohammad Afshar and Masoud Asadpour. Opinion formation by informed a-gents. J. Artificial Societies and Social Simulation,13(4):5,2010.
[153] M. Perc and A. Szolnoki. Coevolutionary games–a mini review. BioSystems,99:109–125,2010.
[154] Christian Borghesi and Serge Galam. Chaotic, staggered, and polarized dynam-ics in opinion forming: The contrarian effect. Phys. Rev. E,73:066118, Jun2006.
[155] Alejandro D. SSnchez, Juan M. L_pez, and Miguel A. Rodr[guez. Nonequi-librium phase transitions in directed small-world networks. Phys. Rev. Lett.,88:048701,2002.
[156] J. M. López M. S. de la Lama and H. S. Wio. Spontaneous emergence ofcontrarian-like behaviour in an opinion spreading model. EPL (Europhysics Let-ters),72(5):851,2005.
[157] Luo-luo Jiang, Da-yin Hua, and Ting Chen. Nonequilibrium phase transitionsin a model with social influence of inflexible units. J. Phys. A: Math. Theor.,40:11271,2007.
[158] Petter Holme and M. E. Newman. Nonequilibrium phase transition in the coevo-lution of networks and opinions. Phys. Rev. E,74:056108,2006.
[159] B. Schmittmann and Abhishek Mukhopadhyay. Opinion formation on adaptivenetworks with intensive average degree. Physical Review E,82(6):1–7,2010.
[160] I. J. Benczik, S. Z. Benczik, B. Schmittmann, and R. K. P. Zia. Opinion dynamicson an adaptive random network. Phys. Rev. E,79:046104,2009.
[161] Luo-Luo. Jiang, D. Hua, J. Zhu, B. Wang, and T. Zhou. Opinion dynamics ondirected small-world networks. Eur. Phys. J. B,65:251–255,2008.
[162] Xenofontas Dimitropoulos, Dmitri Krioukov, Amin Vahdat, and George Riley.Graph annotations in modeling complex network topologies. ACM Trans. Model.Comput. Simul.,19:(17)1–29,2009.
[163] M. E. J. Newman G. T. Barkema. Monte Carlo Methods in Statistical Physics.Oxford Uinversity Press, London,1999.
[164] D. P. Landau and K. Binder. A Guide to Monte Carlo Simulations in StatisticalPhysics. Cambridge University Press, Cambridge,2005.
[165] R. Pastor-Satorras and A. Vespignani. Evolution and Structure of the Internet:A Statistical Physics Approach. Cambridge University Press, New York, NY,USA,2004.
[166] Alejandro D. Sánchez, Juan M. López, and Miguel A. Rodríguez. Nonequi-librium phase transitions in directed small-world networks. Phys. Rev. Lett.,88:048701,2002.
[167] A. Szolnoki, G. Szabó, and M. Perc. Phase diagrams for the spatial public goodsgame with pool punishment. Phys. Rev. E,83:036101,2011.
[168] F. Fu and L. Wang. Coevolutionary dynamics of opinions and networks: Fromdiversity to uniformity. Phys. Rev. E,78:016104,2008.
[169] G. I iguez, J. Kertész, K. K. Kaski, and R. A. Barrio. Opinion and communityformation in coevolving networks. Phys. Rev. E,80:066119,2009.
[170] G. I iguez, J. Kertész, K. K. Kaski, and R. A. Barrio. Phase change in an opinion-dynamics model with separation of time scales. Phys. Rev. E,83:016111,2011.
[171] Petter Holme and Jari Saram ki. Temporal networks. Physics Reports,519(3):97–125,2012.
[172] Leon Danon, Ashley P Ford, Thomas House, Chris P Jewell, Matt J Keeling,Gareth O Roberts, Joshua V Ross, and Matthew C Vernon. Networks and theepidemiology of infectious disease. Interdisciplinary perspectives on infectiousdiseases,2011:284909,2011.
[173] H. H. K. Lentz, T. Selhorst, and I. M Sokolov. Unfolding accessibility providesa macroscopic approach to temporal networks. Arxiv preprint arXiv:1210.2283,October2012.
[174] S. Liu, A. Baronchelli, and N. Perra. Contagion dynamics in time-varyingmetapopulation networks. Arxiv preprint arXiv:1210.2776, October2012.
[175] R. O. dos Santos Soares and A. S. Martinez. The geometrical patterns of cooper-ation evolution in the spatial prisoner’s dilemma: An intra-group model. PhysicaA,369:823–829,2006.
[176] M. dos Santos, D. J. Rankin, and C. Wedekind. The evolution of punishmentthrough reputation. Proc. R. Soc. B,278:371–377,2011.
[177] Yu Zheng and Xiaofang Zhou, editors. Location-Based Social Networks: Users.Springer,2011.
[178] Yu Zheng, Lizhu Zhang, Zhengxin Ma, Xing Xie, and Wei-Ying Ma. Recom-mending friends and locations based on individual location history. ACM Trans-actions on the Web,5(1):5:1–44,2011.
[179] Yu Zheng and Xing Xie. Learning travel recommendations from user-generatedgps traces. ACM Transactions on Intelligent Systems and Technology,2(1):2,2011.
[180] Eunjoon Cho, Seth A. Myers, and Jure Leskovec. Friendship and mobility: usermovement in location-based social networks. In Chid AptW, Joydeep Ghosh, andPadhraic Smyth, editors, Proceedings of the17th ACM SIGKDD internationalconference on Knowledge discovery and data mining, pages1082–1090. ACM,2011.
[181] Yu Zheng and Xing Xie. Reviews of lbsn. http://research.microsoft.com/en-us/projects/lbsn, January2013.