Local Algorithms for Finding Interesting Individuals in Large Networks
We initiate the study of local, sublinear time algorithms for finding vertices with extreme topological properties - such as high degree or clustering coefficient - in large social or other networks. We introduce a new model, called the Jump and Crawl model, in which algorithms are permitted only two graph operations. The Jump operation returns a randomly chosen vertex, and is meant to model the ability to discover new vertices via keyword search in the Web, shared hobbies or interests in social networks such as Facebook, and other mechanisms that may return vertices that are distant from all those currently known. The Crawl operation permits an algorithm to explore the neighbors of any currently known vertex, and has clear analogous in many modern networks. We give both upper and lower bounds in the Jump and Crawl model for the problems of finding vertices of high degree and high clustering coefficient. We consider both arbitrary graphs, and specializations in which some common assumptions are made on the global topology (such as power law degree distributions or generation via preferential attachment). We also examine local algorithms for some related vertex or graph properties, and discuss areas for future investigation.
social networks graph theory algorithms
Mickey Brautbar Michael Kearns
Computer and Information Science, University of Pennsylvania, Philadelphia, 19104, USA
国际会议
The First Symposium on Innovations in Computer Science(2010 计算机科学创新研讨会 ICS 2010)
北京
英文
188-199
2010-01-05（万方平台首次上网日期，不代表论文的发表时间）