CiteULike: gionis's library [36 articles]

BrowseRank: Letting Web Users Vote for Page Importance

Y Liu — 2008-05-26T09:42:59-00:00

(2008)

Computing shortest paths with uncertainty

T Feder — 2008-05-23T16:17:47-00:00

(2003)

We consider the problem of estimating the length of a shortest path in a DAG whose edge lengths are known only approximately but can be determined exactly at a cost. Initially, each edge e is known only to lie within an interval [l e ; he ]; the estimation algorithm can pay ce to find the exact length of e. In particular, we study the problem of finding the cheapest set of edges such that, if exactly these edges are queried, the length of the shortest path will be known, within an...

Better Approximation of Betweenness Centrality

Robert Geisberger — 2008-05-21T16:23:45-00:00

Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX) (2008)

Best position algorithms for top-k queries

Reza Akbarinia — 2008-05-20T19:55:06-00:00

(2007), pp. 495-506.

MapReduce: Simplified Data Processing on Large Clusters

Jeffrey Dean — 2005-12-08T17:08:27-00:00

OSDI '04, pp. 137-150.

MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a _map_ function that processes a key/value pair to generate a set of intermediate key/value pairs, and a _reduce_ function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model, as shown in the paper. <P> Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run-time system takes care of the details of partitioning the input data, scheduling the program's execution across a set of machines, handling machine failures, and managing the required inter- machine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system. <P> Our implementation of MapReduce runs on a large cluster of commodity machines and is highly scalable: a typical MapReduce computation processes many terabytes of data on thousands of machines. Programmers find the system easy to use: hundreds of MapReduce programs have been implemented and upwards of one thousand MapReduce jobs are executed on Google's clusters every day. <P>

Approximating Betweenness Centrality

David Bader — 2008-05-18T15:31:58-00:00

Algorithms and Models for the Web-Graph (2007), pp. 124-137.

Betweenness is a centrality measure based on shortest paths, widely used in complex network analysis. It is computationally-expensive to exactly determine betweenness; currently the fastest-known algorithm by Brandes requires O(nm) time for unweighted graphs and O(nm + n 2logn) time for weighted graphs, where n is the number of vertices and m is the number of edges in the network. These are also the worst-case time bounds for computing the betweenness score of a single vertex. In this paper, we present a novel approximation algorithm for computing betweenness centrality of a given vertex, for both weighted and unweighted graphs. Our approximation algorithm is based on an adaptive sampling technique that significantly reduces the number of single-source shortest path computations for vertices with high centrality. We conduct an extensive experimental study on real-world graph instances, and observe that our random sampling algorithm gives very good betweenness approximations for biological networks, road networks and web crawls.

Optimal aggregation algorithms for middleware

Ronald Fagin — 2008-05-19T11:30:21-00:00

J. Comput. Syst. Sci., Vol. 66, No. 4. (June 2003), pp. 614-656.

A faster algorithm for betweenness centrality

U Brandes — 2007-07-28T20:24:18-00:00

(2001)

The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require #(n ) time and #(n ) space, where n is the number of actors in the network.

Efficient search ranking in social networks

Monique Vieira — 2008-05-15T15:24:08-00:00

(2007), pp. 563-572.

Towards Identity Anonymization on Graphs

Kun Liu — 2008-05-14T09:29:00-00:00

(2008)

Randomizing Social Networks: a Spectrum Preserving Approach

Xiaowei Ying — 2008-05-14T09:26:51-00:00

(2008)

Link Privacy in Social Networks

Aleksandra Korolova — 2008-05-14T09:11:10-00:00

Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on (2008), pp. 1355-1357.

We consider a privacy threat to a social network in which the goal of an attacker is to obtain knowledge of a significant fraction of the links in the network. We formalize the typical social network interface and the information about links that it provides to its users in terms of lookahead. We consider a particular threat in which an attacker subverts user accounts to gain information about local neighborhoods in the network and pieces them together in order to build a global picture. We analyze, both experimentally and theoretically, the number of user accounts an attacker would need to subvert for a successful attack, as a function of his strategy for choosing users whose accounts to subvert and a function of the lookahead provided by the network. We conclude that such an attack is feasible in practice, and thus any social network that wishes to protect the link privacy of its users should take great care in choosing the lookahead of its interface, limiting it to 1 or 2, whenever possible.

The Structure of Collaborative Tagging Systems

Scott Golder — 2005-08-27T17:06:09-00:00

(18 Aug 2005)

Collaborative tagging describes the process by which many users add metadata in the form of keywords to shared content. Recently, collaborative tagging has grown in popularity on the web, on sites that allow users to tag bookmarks, photographs and other content. In this paper we analyze the structure of collaborative tagging systems as well as their dynamical aspects. Specifically, we discovered regularities in user activity, tag frequencies, kinds of tags used, bursts of popularity in bookmarking and a remarkable stability in the relative proportions of tags within a given url. We also present a dynamical model of collaborative tagging that predicts these stable patterns and relates them to imitation and shared knowledge.

Searching the Blogosphere

Nilesh Bansal — 2008-03-28T17:04:53-00:00

WebDB (2007)

BuzzRank &\#8230; and the trend is your friend

Klaus Berberich — 2008-03-28T16:27:36-00:00

(2006), pp. 937-938.

The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank

Mathew Richardson — 2005-10-03T10:41:59-00:00

(2002)

The PageRank algorithm, used in the Google search engine, greatly improves the results of Web search by taking into account the link structure of the Web. PageRank assigns to a page a score proportional to the number of times a random surfer would visit that page, if it surfed indefinitely from page to page, following all outlinks from a page with equal probability. We propose to improve PageRank by using a more intelligent surfer, one that is guided by a probabilistic model of the relevance of ...

Optimizing web search using social annotations

Shenghua Bao — 2007-05-10T22:36:45-00:00

(2007), pp. 501-510.

HT06, tagging paper, taxonomy, Flickr, academic article, to read

Cameron Marlow — 2006-08-24T20:16:54-00:00

(2006), pp. 31-40.

Entropy of search logs: how hard is search? with personalization? with backoff?

Qiaozhu Mei — 2008-02-20T11:07:28-00:00

(2008), pp. 45-54.

Usage patterns of collaborative tagging systems

Scott Golder — 2006-07-05T17:36:01-00:00

J. Inf. Sci., Vol. 32, No. 2. (April 2006), pp. 198-208.

Personalizing Image Search Results on Flickr

Kristina Lerman — 2007-04-16T16:57:49-00:00

(12 Apr 2007)

The social media site Flickr allows users to upload their photos, annotate them with tags, submit them to groups, and also to form social networks by adding other users as contacts. Flickr offers multiple ways of browsing or searching it. One option is tag search, which returns all images tagged with a specific keyword. If the keyword is ambiguous, e.g., “beetle” could mean an insect or a car, tag search results will include many images that are not relevant to the sense the user had in mind when executing the query. We claim that users express their photography interests through the metadata they add in the form of contacts and image annotations. We show how to exploit this metadata to personalize search results for the user, thereby improving search performance. First, we show that we can significantly improve search precision by filtering tag search results by user's contacts or a larger social network that includes those contact's contacts. Secondly, we describe a probabilistic model that takes advantage of tag information to discover latent topics contained in the search results. The users' interests can similarly be described by the tags they used for annotating their images. The latent topics found by the model are then used to personalize search results by finding images on topics that are of interest to the user.

Query incentive networks

J Kleinberg — 2008-03-18T17:51:27-00:00

Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on (2005), pp. 132-141.

The concurrent growth of on-line communities exhibiting large-scale social structure, and of large decentralized peer-to-peer file-sharing systems, has stimulated new interest in understanding networks of interacting agents as economic systems. Here we formulate a model for query incentive networks, motivated by such systems: users seeking information or services can pose queries, together with incentives for answering them, that are propagated along paths in a network. This type of information-seeking process can be formulated as a game among the nodes in the network, and this game has a natural Nash equilibrium. In such systems, it is a fundamental question to understand how much incentive is needed in order for a node to achieve a reasonable probability of obtaining an answer to a query from the network. We study the size of query incentives as a function both of the rarity of the answer and the structure of the underlying network. This leads to natural questions related to strategic behavior in branching processes. Whereas the classically studied criticality of branching processes is centered around the region where the branching parameter is 1, we show in contrast that strategic interaction in incentive propagation exhibits critical behavior when the branching parameter is 2.

How to search a social network

Lada Adamic — 2008-01-29T15:10:43-00:00

Social Neworks, Vol. 27, No. 3. (July 2005), pp. 187-203.

Complex Networks and Decentralized Search Algorithms

Jon Kleinberg — 2008-01-29T15:59:24-00:00

(2006)

Can Social Bookmarking Improve Web Search?

Paul Heymann — 2008-03-04T17:36:13-00:00

(February 2008)

Social bookmarking is a recent phenomenon which has the potential to give us a great deal of data about pages on the web. One major question is whether that data can be used to augment systems like web search. To answer this question, over the past year we have gathered what we believe to be the largest dataset from a social bookmarking site yet analyzed by academic researchers. Our dataset represents about forty million bookmarks from the social bookmarking site del.icio.us. We contribute a characterization of posts to del.icio.us: how many bookmarks exist (about 115 million), how fast is it growing, and how active are the URLs being posted about (quite active). We also contribute a characterization of tags used by bookmarkers. We found that certain tags tend to gravitate towards certain domains, and vice versa. We also found that tags occur in over 50 percent of the pages that they annotate, and in only 20 percent of cases do they not occur in the page text, backlink page text, or forward link page text of the pages they annotate. We conclude that social bookmarking can provide search data not currently provided by other sources, though it may currently lack the size and distribution of tags necessary to make a significant impact.

Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions

Gediminas Adomavicius — 2006-02-21T16:53:07-00:00

IEEE Transactions on Knowledge and Data Engineering, Vol. 17, No. 6. (June 2005), pp. 734-749.

Member-Gediminas Adomavicius and Member-Alexander Tuzhilin

Tribler: A social-based peer-to-peer system

J Pouwelse — 2007-01-31T09:19:12-00:00

Concurrency and Computation: Practice and Experience, Vol. 20 (2008), pp. 127-138.

Challenges in Searching Online Communities

Sihem Yahia — 2008-03-04T19:41:16-00:00

Bulletin of the IEEE Computer Society Technical Committee on Data Engineering (2007), pp. 1-9.

Using Social Tagging to Improve Social Navigation

David Millen — 2008-03-03T00:39:29-00:00

(2006)

In this paper, we explore the increasingly popular social bookmarking services. These services powerfully combine personal tagging of information sources with interactive browsing, which allows for improved social navigation. We examine the use of a social bookmarking service, deployed in a large organization, to understand how social navigation is supported. We conclude that social tags used in the context of a social bookmarking service are an important way to improve social navigation.

SOCIAL COMPUTING: AN OVERVIEW

Manoj Parameswaran — 2008-03-04T20:02:06-00:00

Communications of the Association for Information Systems, Vol. 19 (2007), pp. 762-780.

A collection of technologies termed social computing is driving a dramatic evolution of the Web, matching the dot-com era in growth, excitement, and investment. All of these share a high degree of community formation, user level content creation, and a variety of other characteristics. We provide an overview of social computing and identify salient characteristics. We argue that social computing holds tremendous disruptive potential in the business world and can significantly impact society, and outline possible changes in organized human action that could be brought about. Social computing can also have deleterious effects associated with it, including security issues. We suggest that social computing should be a priority for researchers and business leaders and illustrate the fundamental shifts in communication, computing, collaboration, and commerce brought about by this trend.

Pruning policies for two-tiered inverted index with correctness guarantee

Alexandros Ntoulas — 2007-12-19T21:47:48-00:00

(2007), pp. 191-198.

Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks

Pekka Orponen — 2004-11-22T00:17:30-00:00

(2 June 2004)

We propose efficient algorithms for two key tasks in the analysis of large nonuniform networks: uniform node sampling and cluster detection. Our sampling technique is based on augmenting a simple, but slowly mixing uniform MCMC sampler with a regular random walk in order to speed up its convergence; however the combined MCMC chain is then only sampled when it is in its "uniform sampling" mode.Our clustering algorithm determines the relevant neighbourhood of a given node u in the network by first estimating the Fiedler vector of a Dirichlet matrix with u fixed at zero potential, and then finding the neighbourhood of u that yields a minimal weighted Cheeger ratio, where the edge weights are determined by differences in the estimated node potentials. Both of our algorithms are based on local computations, i.e. operations on the full adjacency matrix of the network are not used. The algorithms are evaluated experimentally using three types of nonuniform networks: Dorogovtsev-Goltsev-Mendes "pseudofractal graphs", scientific collaboration networks, and randomised "caveman graphs".

Local Computation of PageRank Contributions

Reid Andersen — 2007-12-03T16:34:57-00:00

Algorithms and Models for the Web-Graph (2007), pp. 150-165.

Motivated by the problem of detecting link-spam, we consider the following graph-theoretic primitive: Given a webgraph G, a vertex v in G, and a parameter δ ∈ (0,1), compute the set of all vertices that contribute to v at least a δ fraction of v’s PageRank. We call this set the δ-contributing set of v. To this end, we define the contribution vector of v to be the vector whose entries measure the contributions of every vertex to the PageRank of v. A local algorithm is one that produces a solution by adaptively examining only a small portion of the input graph near a specified vertex. We give an efficient local algorithm that computes an ε-approximation of the contribution vector for a given vertex by adaptively examining O(1/ε) vertices. Using this algorithm, we give a local approximation algorithm for the primitive defined above. Specifically, we give an algorithm that returns a set containing the δ-contributing set of v and at most O(1/δ) vertices from the δ/2-contributing set of v, and which does so by examining at most O(1/δ) vertices. We also give a local algorithm for solving the following problem: If there exist k vertices that contribute a ρ-fraction to the PageRank of v, find a set of k vertices that contribute at least a (ρ − ε)-fraction to the PageRank of v. In this case, we prove that our algorithm examines at most O(k/ε) vertices.

Local methods for estimating pagerank values

Yen-Yu Chen — 2005-07-04T11:55:30-00:00

(2004), pp. 381-389.

A brief history of generative models for power law and lognormal distributions

M Mitzenmacher — 2006-09-15T22:00:19-00:00

Power law distributions are an increasingly common model for computer science applications; for example, they have been used to describe file size distributions and in- and out-degree distributions for the Web and Internet graphs. Recently, the similar lognormal distribution has also been suggested as an appropriate alternative model for file size distributions. In this paper, we briefly survey some of the history of these distributions, focusing on work in other fields. We find that several...

Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)

Lun Li — 2005-10-19T18:43:40-00:00

(18 Oct 2005)

Although the “scale-free” literature is large and growing, it gives neither a precise definition of scale-free graphs nor rigorous proofs of many of their claimed properties. In fact, it is easily shown that the existing theory has many inherent contradictions and verifiably false claims. In this paper, we propose a new, mathematically precise, and structural definition of the extent to which a graph is scale-free, and prove a series of results that recover many of the claimed properties while suggesting the potential for a rich and interesting theory. With this definition, scale-free (or its opposite, scale-rich) is closely related to other structural graph properties such as various notions of self-similarity (or respectively, self-dissimilarity). Scale-free graphs are also shown to be the likely outcome of random construction processes, consistent with the heuristic definitions implicit in existing random graph approaches. Our approach clarifies much of the confusion surrounding the sensational qualitative claims in the scale-free literature, and offers rigorous and quantitative alternatives.