QQ客服 官方微博 反馈留言

	A game theoretic model for the formation of navigable small-world networks
	Yang, Zhi ; Chen, Wei
	2015
英文摘要	Kleinberg proposed a family of small-world networks to explain the navigability of large-scale real-world social networks. However, the underlying mechanism that drives real networks to be navigable is not yet well understood. In this paper, we present a game theoretic model for the formation of navigable small world networks. We model the network formation as a game in which people seek for both high reciprocity and long-distance relationships. We show that the navigable small-world network is a Nash Equilibrium of the game. Moreover, we prove that the navigable small-world equilibrium tolerates collusions of any size and arbitrary deviations of a large random set of nodes, while non-navigable equilibria do not tolerate small group collusions or random perturbations. Our empirical evaluation further demonstrates that the system always converges to the navigable network even when limited or no information about other players' strategies is available. Our theoretical and empirical analyses provide important new insight on the connection between distance, reciprocity and navigability in social networks.; EI; 1329-1339
语种	英语
出处	24th International Conference on World Wide Web, WWW 2015
DOI标识	10.1145/2736277.2741110
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/436825]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Yang, Zhi,Chen, Wei. A game theoretic model for the formation of navigable small-world networks. 2015-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。