@article{kleinberg2013analysis, abstract = {The growth of the Web has required us to think about the design of information systems in which large-scale computational and social feedback effects are simultaneously at work. At the same time, the data generated by Web-scale systems—recording the ways in which millions of participants create content, link information, form groups and communicate with one another—have made it possible to evaluate long-standing theories of social interaction, and to formulate new theories based on what we observe. These developments have created a new level of interaction between computing and the social sciences, enriching the perspectives of both of these disciplines. We discuss some of the observations, theories and conclusions that have grown from the study of Web-scale social interaction, focusing on issues including the mechanisms by which people join groups, the ways in which different groups are linked together in social networks and the interplay of positive and negative interactions in these networks.}, author = {Kleinberg, Jon}, doi = {10.1098/rsta.2012.0378}, eprint = {http://rsta.royalsocietypublishing.org/content/371/1987/20120378.full.pdf+html}, interhash = {b4686f01da53c975f342dbb40bdd1a90}, intrahash = {e3898cfb7206a7fee8eb3a5419aa030f}, journal = {Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences}, month = mar, number = 1987, title = {Analysis of large-scale social and information networks}, url = {http://rsta.royalsocietypublishing.org/content/371/1987/20120378.abstract}, volume = 371, year = 2013 } @article{kleinberg1999authoritative, abstract = {The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of context on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics, through the discovery of “authorative” information sources on such topics. We propose and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure. Our formulation has connections to the eigenvectors of certain matrices associated with the link graph; these connections in turn motivate additional heuristrics for link-based analysis.}, acmid = {324140}, address = {New York, NY, USA}, author = {Kleinberg, Jon M.}, doi = {10.1145/324133.324140}, interhash = {48a48add3cba613f07df1e9b56278b85}, intrahash = {16d697dadb4743613449792e72b434b7}, issn = {0004-5411}, issue = {5}, journal = {J. ACM}, month = {September}, numpages = {29}, pages = {604--632}, publisher = {ACM}, title = {Authoritative sources in a hyperlinked environment}, url = {http://doi.acm.org/10.1145/324133.324140}, volume = 46, year = 1999 } @inproceedings{Backstrom:2007:WAT:1242572.1242598, abstract = {In a social network, nodes correspond topeople or other social entities, and edges correspond to social links between them. In an effort to preserve privacy, the practice of anonymization replaces names with meaningless unique identifiers. We describe a family of attacks such that even from a single anonymized copy of a social network, it is possible for an adversary to learn whether edges exist or not between specific targeted pairs of nodes.}, acmid = {1242598}, address = {New York, NY, USA}, author = {Backstrom, Lars and Dwork, Cynthia and Kleinberg, Jon}, booktitle = {Proceedings of the 16th international conference on World Wide Web}, doi = {10.1145/1242572.1242598}, interhash = {aa7d0f96c372d2c03d228f27a7f4b66b}, intrahash = {913059fcbf0453c60ff8b79e2705742c}, isbn = {978-1-59593-654-7}, location = {Banff, Alberta, Canada}, numpages = {10}, pages = {181--190}, publisher = {ACM}, series = {WWW '07}, title = {Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography}, url = {http://doi.acm.org/10.1145/1242572.1242598}, year = 2007 } @misc{leskovec2010predicting, abstract = { We study online social networks in which relationships can be either positive(indicating relations such as friendship) or negative (indicating relationssuch as opposition or antagonism). Such a mix of positive and negative linksarise in a variety of online settings; we study datasets from Epinions,Slashdot and Wikipedia. We find that the signs of links in the underlyingsocial networks can be predicted with high accuracy, using models thatgeneralize across this diverse range of sites. These models provide insightinto some of the fundamental principles that drive the formation of signedlinks in networks, shedding light on theories of balance and status from socialpsychology; they also suggest social computing applications by which theattitude of one user toward another can be estimated from evidence provided bytheir relationships with other members of the surrounding social network.}, author = {Leskovec, Jure and Huttenlocher, Daniel and Kleinberg, Jon}, interhash = {24158224b6b45342017e1157f98f5c65}, intrahash = {cdf322be85a607c789a5ee0e930f72ef}, note = {cite arxiv:1003.2429}, title = {Predicting Positive and Negative Links in Online Social Networks}, url = {http://arxiv.org/abs/1003.2429}, year = 2010 } @inproceedings{crandall2008feedback, abstract = {A fundamental open question in the analysis of social networks is to understand the interplay between similarity and social ties. People are similar to their neighbors in a social network for two distinct reasons: first, they grow to resemble their current friends due to social influence; and second, they tend to form new links to others who are already like them, a process often termed selection by sociologists. While both factors are present in everyday social processes, they are in tension: social influence can push systems toward uniformity of behavior, while selection can lead to fragmentation. As such, it is important to understand the relative effects of these forces, and this has been a challenge due to the difficulty of isolating and quantifying them in real settings.}, address = {New York, NY, USA}, at = {2009-07-01 08:09:57}, author = {Crandall, David and Cosley, Dan and Huttenlocher, Daniel and Kleinberg, Jon and Suri, Siddharth}, booktitle = {KDD '08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining}, doi = {10.1145/1401890.1401914}, id = {3353096}, interhash = {07ad80d96b769ae60741f4269fccd544}, intrahash = {64d218d536296955df9780a23d9f2aec}, isbn = {978-1-60558-193-4}, location = {Las Vegas, Nevada, USA}, pages = {160--168}, priority = {3}, publisher = {ACM}, title = {Feedback effects between similarity and social influence in online communities}, url = {http://dx.doi.org/10.1145/1401890.1401914}, year = 2008 } @article{kleinberg99authoritative, abstract = {. The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of contexts on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics,...}, author = {Kleinberg, Jon M.}, citeulike-article-id = {1115}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.9983}, citeulike-linkout-1 = {http://citeseer.nj.nec.com/kleinberg99authoritative.html}, citeulike-linkout-2 = {http://dx.doi.org/10.1145/324133.324140}, doi = {10.1145/324133.324140}, interhash = {48a48add3cba613f07df1e9b56278b85}, intrahash = {c86549355475331f563d0a3ba7816dab}, journal = {Journal of the ACM}, month = {September}, number = 5, pages = {604--632}, posted-at = {2005-07-07 17:29:16}, priority = {0}, title = {Authoritative sources in a hyperlinked environment}, url = {http://dx.doi.org/10.1145/324133.324140}, volume = 46, year = 1999 } @inproceedings{Gibson98clusteringcategorical, abstract = {We describe a novel approach for clustering collections of sets, and its application to the analysis and mining of categorical data. By "categorical data," we mean tables with fields that cannot be naturally ordered by a metric --- e.g., the names of producers of automobiles, or the names of products offered by a manufacturer. Our approach is based on an iterative method for assigning and propagating weights on the categorical values in a table; this facilitates a type of similarity measure arising from the cooccurrence of values in the dataset. Our techniques can be studied analytically in terms of certain types of non-linear dynamical systems. We discuss experiments on a variety of tables of synthetic and real data; we find that our iterative methods converge quickly to prominently correlated values of various categorical fields. 1 Introduction Much of the data in databases is categorical: fields in tables whose attributes cannot naturally be ordered as numerical values can. The pro...}, author = {Gibson, David and Kleinberg, Jon and Raghavan, Prabhakar}, interhash = {1439dc731dbc3225e455c4cd4ec297b1}, intrahash = {31bcdc070e056e9ba33ba155ebc9285d}, pages = {311--322}, title = {Clustering Categorical Data: An Approach Based on Dynamical Systems}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8003}, year = 1998 } @inproceedings{1557077, abstract = {Tracking new topics, ideas, and "memes" across the Web has been an issue of considerable interest. Recent work has developed methods for tracking topic shifts over long time scales, as well as abrupt spikes in the appearance of particular named entities. However, these approaches are less well suited to the identification of content that spreads widely and then fades over time scales on the order of days - the time scale at which we perceive news and events. We develop a framework for tracking short, distinctive phrases that travel relatively intact through on-line text; developing scalable algorithms for clustering textual variants of such phrases, we identify a broad class of memes that exhibit wide spread and rich variation on a daily basis. As our principal domain of study, we show how such a meme-tracking approach can provide a coherent representation of the news cycle - the daily rhythms in the news media that have long been the subject of qualitative interpretation but have never been captured accurately enough to permit actual quantitative analysis. We tracked 1.6 million mainstream media sites and blogs over a period of three months with the total of 90 million articles and we find a set of novel and persistent temporal patterns in the news cycle. In particular, we observe a typical lag of 2.5 hours between the peaks of attention to a phrase in the news media and in blogs respectively, with divergent behavior around the overall peak and a "heartbeat"-like pattern in the handoff between news and blogs. We also develop and analyze a mathematical model for the kinds of temporal variation that the system exhibits.}, address = {New York, NY, USA}, author = {Leskovec, Jure and Backstrom, Lars and Kleinberg, Jon}, booktitle = {KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining}, doi = {http://doi.acm.org/10.1145/1557019.1557077}, interhash = {f60a96f8adb340b62bacbc90fdb3e069}, intrahash = {051df7b09db1d7806909cc22c1a362c8}, isbn = {978-1-60558-495-9}, location = {Paris, France}, pages = {497--506}, publisher = {ACM}, title = {Meme-tracking and the dynamics of the news cycle}, url = {http://portal.acm.org/citation.cfm?id=1557077}, year = 2009 } @article{kleinberg1999hits, abstract = {. The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of contexts on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics,...}, author = {Kleinberg, Jon M.}, citeulike-article-id = {1115}, comment = {HITS algorithm}, interhash = {48a48add3cba613f07df1e9b56278b85}, intrahash = {c86549355475331f563d0a3ba7816dab}, journal = {Journal of the ACM}, number = 5, pages = {604--632}, priority = {1}, title = {Authoritative sources in a hyperlinked environment}, url = {http://citeseer.ist.psu.edu/kleinberg99authoritative.html}, volume = 46, year = 1999 } @inproceedings{citeulike:347486, author = {Leskovec, Jure and Kleinberg, Jon and Faloutsos, Christos}, booktitle = {KDD}, citeulike-article-id = {347486}, interhash = {2afe2dfec088b4c54983cba0a103aafe}, intrahash = {c71e295b95551b8de4d9a75f6351f184}, priority = {4}, privnote = {Anwenden auf delicious datensatz}, title = {Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations}, url = {http://www.cs.cornell.edu/home/kleinber/kdd05-time.pdf}, year = 2005 } @inproceedings{conf/kdd/BackstromHKL06, author = {Backstrom, Lars and Huttenlocher, Daniel P. and Kleinberg, Jon M. and Lan, Xiangyang}, booktitle = {KDD}, crossref = {conf/kdd/2006}, date = {2006-10-05}, editor = {Eliassi-Rad, Tina and Ungar, Lyle H. and Craven, Mark and Gunopulos, Dimitrios}, ee = {http://doi.acm.org/10.1145/1150402.1150412}, interhash = {a3cda51b88fd4ff49632bd6b393b5b6b}, intrahash = {d7f58740d7b63881ba4993d0a576be94}, isbn = {1-59593-339-5}, pages = {44-54}, publisher = {ACM}, title = {Group formation in large social networks: membership, growth, and evolution.}, url = {http://dblp.uni-trier.de/db/conf/kdd/kdd2006.html#BackstromHKL06}, year = 2006 } @inproceedings{conf/ht/GibsonKR98, author = {Gibson, David and Kleinberg, Jon M. and Raghavan, Prabhakar}, booktitle = {Hypertext}, cdrom = {HT1998/P225.pdf}, ee = {db/conf/ht/GibsonKR98.html}, interhash = {47c85d35ba3293b0de52af32e824164b}, intrahash = {bdc4ed454bc2dd7194de0f5f0b451203}, pages = {225-234}, title = {Inferring Web Communities from Link Topology.}, url = {http://dblp.uni-trier.de/db/conf/ht/ht98.html#GibsonKR98}, year = 1998 } @article{gibson00clustering, author = {Gibson, David and Kleinberg, Jon M. and Raghavan, Prabhakar}, interhash = {8a2ea9a413538069328404c0bfe9c656}, intrahash = {5205d8f52b2a8f22b63dd40bdd99746a}, journal = {VLDB Journal: Very Large Data Bases}, number = {3--4}, pages = {222--236}, title = {Clustering Categorical Data: An Approach Based on Dynamical Systems}, url = {http://citeseer.ist.psu.edu/cache/papers/cs/157/http:zSzzSzcs.cornell.eduzSzInfozSzPeoplezSzkleinberzSzvldb98.pdf/gibson98clustering.pdf}, volume = 8, year = 2000 }