Matches in ScholarlyData for { ?s ?p ?o. }
- item-2 previous item-1.
- counting-triangles-and-the-curse-of-the-last-reduc creator sergei-vassilvitskii.
- counting-triangles-and-the-curse-of-the-last-reduc creator siddharth-suri.
- counting-triangles-and-the-curse-of-the-last-reduc type InProceedings.
- counting-triangles-and-the-curse-of-the-last-reduc label "Counting Triangles and the Curse of the Last Reducer".
- counting-triangles-and-the-curse-of-the-last-reduc sameAs counting-triangles-and-the-curse-of-the-last-reduc.
- counting-triangles-and-the-curse-of-the-last-reduc abstract "The clustering coefficient of a node in a social network is a fundamental measure that quantifies how tightly-knit the community is around the node. Its computation can be reduced to counting the number of triangles incident on the particular node in the network. In case the graph is too big to fit into memory, this is a non-trivial task, and previous researchers showed how to estimate the clustering coefficient in this scenario. A different avenue of research is to to perform the computation in parallel, spreading it across many machines. In recent years MapReduce has emerged as a de facto programming paradigm for parallel computation on massive data sets. The main focus of this work is to give MapReduce algorithms for counting triangles which we use to compute clustering coefficients. Our contributions are twofold. First, we describe a sequential triangle counting algorithm and show how to adapt it to the MapReduce setting. This algorithm achieves a factor of 10-100 speed up over the naive approach. Second, we present a new algorithm designed specifically for the MapReduce framework. A key feature of this approach is that it allows for a smooth tradeoff between the memory available on each individual machine and the total memory available to the algorithm, while keeping the total work done constant. Moreover, this algorithm can use any triangle counting algorithm as a black box and distribute the computation across many machines. We validate our algorithms on real world datasets comprising of millions of nodes and over a billion edges. Our results show both algorithms effectively deal with skew in the degree distribution and lead to dramatic speed ups over the naive implementation.".
- counting-triangles-and-the-curse-of-the-last-reduc hasAuthorList authorList.
- counting-triangles-and-the-curse-of-the-last-reduc hasTopic social-network-algorithms.
- counting-triangles-and-the-curse-of-the-last-reduc hasTopic World_Wide_Web.
- counting-triangles-and-the-curse-of-the-last-reduc isPartOf proceedings.
- counting-triangles-and-the-curse-of-the-last-reduc title "Counting Triangles and the Curse of the Last Reducer".
- authorList type List.
- authorList hasFirstItem item-1.
- authorList hasItem item-1.
- authorList hasItem item-2.
- authorList hasLastItem item-2.
- item-1 type ListItem.
- item-1 hasContent siddharth-suri.
- item-1 next item-2.
- item-2 type ListItem.
- item-2 hasContent sergei-vassilvitskii.
- item-2 previous item-1.
- differences-in-the-mechanics-of-information-diffus creator brendan-meeder.
- differences-in-the-mechanics-of-information-diffus creator daniel-m-romero.
- differences-in-the-mechanics-of-information-diffus creator jon-kleinberg.
- differences-in-the-mechanics-of-information-diffus type InProceedings.
- differences-in-the-mechanics-of-information-diffus label "Differences in the Mechanics of Information Diffusion Across Topics: Idioms, Political Hashtags, and Complex Contagion on Twitter".
- differences-in-the-mechanics-of-information-diffus sameAs differences-in-the-mechanics-of-information-diffus.
- differences-in-the-mechanics-of-information-diffus abstract "There is a widespread intuitive sense that different kinds of information spread differently on-line, but it has been difficult to evaluate this question quantitatively since it requires a setting where many different kinds of information spread in a shared environment. Here we study this issue on Twitter, analyzing the ways in which tokens known as hashtags spread on a network defined by the interactions among Twitter users. We find significant variation in the ways that widely-used hashtags on different topics spread. Our results show that this variation is not attributable simply to differences in stickiness, the probability of adoption based on one or more exposures, but also to a quantity that could be viewed as a kind of persistence the relative extent to which repeated exposures to a hashtag continue to have significant marginal effects. We find that hashtags on politically controversial topics are particularly persistent, with repeated exposures continuing to have unusually large marginal effects on adoption; this provides, to our knowledge, the first large-scale validation of the complex contagion principle from sociology, which posits that repeated exposures to an idea are particularly crucial when the idea is in some way controversial or contentious. Among other findings, we discover that hashtags representing the natural analogues of Twitter idioms and neologisms are particularly non-persistent, with the effect of multiple exposures decaying rapidly relative to the first exposure. We also study the subgraph structure of the initial adopters for different widely-adopted hashtags, again finding structural differences across topics. We develop simulation-based and generative models to analyze how the adoption dynamics interact with the network structure of the early adopters on which a hashtag spreads.".
- differences-in-the-mechanics-of-information-diffus hasAuthorList authorList.
- differences-in-the-mechanics-of-information-diffus hasTopic diffusion.
- differences-in-the-mechanics-of-information-diffus hasTopic World_Wide_Web.
- differences-in-the-mechanics-of-information-diffus isPartOf proceedings.
- differences-in-the-mechanics-of-information-diffus title "Differences in the Mechanics of Information Diffusion Across Topics: Idioms, Political Hashtags, and Complex Contagion on Twitter".
- authorList type List.
- authorList hasFirstItem item-1.
- authorList hasItem item-1.
- authorList hasItem item-2.
- authorList hasItem item-3.
- authorList hasLastItem item-3.
- item-1 type ListItem.
- item-1 hasContent daniel-m-romero.
- item-1 next item-2.
- item-2 type ListItem.
- item-2 hasContent brendan-meeder.
- item-2 next item-3.
- item-2 previous item-1.
- item-3 type ListItem.
- item-3 hasContent jon-kleinberg.
- item-3 previous item-2.
- dynamics-of-bidding-in-a-p2p-lending-service-effec creator jure-leskovec.
- dynamics-of-bidding-in-a-p2p-lending-service-effec creator simla-ceyhan.
- dynamics-of-bidding-in-a-p2p-lending-service-effec creator xiaolin-shi.
- dynamics-of-bidding-in-a-p2p-lending-service-effec type InProceedings.
- dynamics-of-bidding-in-a-p2p-lending-service-effec label "Dynamics of Bidding in A P2P Lending Service: Effects of Herding and Predicting Loan Success".
- dynamics-of-bidding-in-a-p2p-lending-service-effec sameAs dynamics-of-bidding-in-a-p2p-lending-service-effec.
- dynamics-of-bidding-in-a-p2p-lending-service-effec abstract "Online peer-to-peer (P2P) lending services are a new type of social platform that enables individuals borrow and lend money directly from one to another. In this paper, we study the dynamics of bid- ding behavior in a P2P loan auction website, Prosper.com. We investigate the change of various attributes of loan requesting listings over time, such as the interest rate and the number of bids. We ob- serve that there is herding behavior during bidding, and for most of the listings, the numbers of bids they receive reach spikes at very similar time points. We explain these phenomena by showing that there are economic and social factors that lenders take into account when deciding to bid on a listing.We also observe that the profits the lenders make are tied with their bidding preferences. Finally, we build a model based on the temporal progression of the bidding, that reliably predicts the success of a loan request listing, as well as whether a loan will be paid back or not.".
- dynamics-of-bidding-in-a-p2p-lending-service-effec hasAuthorList authorList.
- dynamics-of-bidding-in-a-p2p-lending-service-effec hasTopic social-network-analysis.
- dynamics-of-bidding-in-a-p2p-lending-service-effec hasTopic World_Wide_Web.
- dynamics-of-bidding-in-a-p2p-lending-service-effec isPartOf proceedings.
- dynamics-of-bidding-in-a-p2p-lending-service-effec title "Dynamics of Bidding in A P2P Lending Service: Effects of Herding and Predicting Loan Success".
- authorList type List.
- authorList hasFirstItem item-1.
- authorList hasItem item-1.
- authorList hasItem item-2.
- authorList hasItem item-3.
- authorList hasLastItem item-3.
- item-1 type ListItem.
- item-1 hasContent simla-ceyhan.
- item-1 next item-2.
- item-2 type ListItem.
- item-2 hasContent xiaolin-shi.
- item-2 next item-3.
- item-2 previous item-1.
- item-3 type ListItem.
- item-3 hasContent jure-leskovec.
- item-3 previous item-2.
- efficient-k-nearest-neighbor-graph-construction-fo creator kai-li.
- efficient-k-nearest-neighbor-graph-construction-fo creator moses-charikar.
- efficient-k-nearest-neighbor-graph-construction-fo creator wei-dong.
- efficient-k-nearest-neighbor-graph-construction-fo type InProceedings.
- efficient-k-nearest-neighbor-graph-construction-fo label "Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures".
- efficient-k-nearest-neighbor-graph-construction-fo sameAs efficient-k-nearest-neighbor-graph-construction-fo.
- efficient-k-nearest-neighbor-graph-construction-fo abstract "K-Nearest Neighbor Graph (K-NNG) construction is an important operation with many web related applications, including collaborative filtering, similarity search, and many others in data mining and machine learning. Existing methods for K-NNG construction either do not scale, or are specific to certain similarity measures. We present NN-Descent, a simple yet efficient algorithm for approximate K-NNG construction with arbitrary similarity measures. Our method is based on local search, has minimal space overhead and does not rely on any shared global index. Hence, it is especially suitable for large-scale applications where data structures need to be distributed over the network. We have shown with a variety of datasets and similarity measures that the proposed method typically converges to above 90% recall with each point comparing only to several percent of the whole dataset on average.".
- efficient-k-nearest-neighbor-graph-construction-fo hasAuthorList authorList.
- efficient-k-nearest-neighbor-graph-construction-fo hasTopic clustering.
- efficient-k-nearest-neighbor-graph-construction-fo hasTopic World_Wide_Web.
- efficient-k-nearest-neighbor-graph-construction-fo isPartOf proceedings.
- efficient-k-nearest-neighbor-graph-construction-fo title "Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures".
- authorList type List.
- authorList hasFirstItem item-1.
- authorList hasItem item-1.
- authorList hasItem item-2.
- authorList hasItem item-3.
- authorList hasLastItem item-3.
- item-1 type ListItem.
- item-1 hasContent wei-dong.
- item-1 next item-2.