KDD2013

The process of opinion formation through synthesis and contrast of different viewpoints has been the subject of many studies in economics and social sciences. Today, this process manifests itself also in online social networks and social media. The key characteristic of successful promotion campaigns is that they take into consideration such opinion-formation dynamics in order to create a overall favorable opinion about a specific information item, such as a person, a product, or an idea. In this talk, we will review models of opinion dynamics and give a game-theoretic viewpoint to the opinion-formation process. Moreover, we will formalize the campaign-design problem as the problem of identifying a set of target individuals whose positive opinion about an information item will maximize the overall positive opinion for the item in the social network. From the technical point of view, we will discuss different variants of such campaign-design problems and analyze their computational difficulties as well as their applicability in practical settings.

The availability and affordability of large-scale data processing is transforming graph mining into a core production use case, especially in the consumer web space. At LinkedIn, the largest professional online social network with 225 million members, a crucial characteristic is the use of static and temporal network features for many applications, particularly recommendations. These include "People You May Know", a link prediction system to find other members on the network; "Endorsements", a lightweight skill reputation product; "Related Searches", query recommendations in our search engine; and more. How do we perform this graph mining at scale? What are some of the challenges we face? Besides the social graph, what about other interesting, but potentially more complex and larger graphs? In this talk, I will illustrate several of LinkedIn's solutions in large scale graph mining.

Given a set of people and a set of events attended by them, we address the problem of measuring connectedness or tie strength between each pair of persons. The underlying assumption is that attendance at mutual events gives an implicit social network between people. We take an axiomatic approach to this problem. Starting from a list of axioms, which a measure of tie strength must satisfy, we characterize functions that satisfy all the axioms. We then show that there is a range of tie-strength measures that satisfy this characterization. A measure of tie strength induces a ranking on the edges of the social network (and on the set of neighbors for every person). We show that for applications where the ranking, and not the absolute value of the tie strength, is the important aspect about the measure, the axioms are equivalent to a natural partial order. To settle on a particular measure, we must make a non-obvious decision about extending this partial order to a total order. This decision is best left to particular applications. We also classify existing tie-strength measures according to the axioms that they satisfy; and observe that none of the "self-referential" tie-strength measures satisfy the axioms. In our experiments, we demonstrate the efficacy of our approach; show the completeness and soundness of our axioms, and present Kendall Tau Rank Correlation between various tie-strength measures.

Google's Knowledge Graph contains over half a billion entities and over 18 billion facts and connections. The Knowledge Graph can grow via human contributions, linking to existing knowledge repositories, and automatic acquisition of knowledge from the Internet. In this talk, we will discuss the frontiers of research in knowledge discovery on the Web. We will also discuss new functionalities that become possible due to deeper, knowledge-based text understanding, including proactively fetching relevant information and entity-based services.

Personalized PageRank is a reasonably well known technique to find a community in a network starting from a single node. It works by approximating the stationary distribution of a resetting random-walk and using that stationary distribution to estimate the presence of nearby cuts in the graph. Ill discuss recent work on how to find use a personalized PageRank community to quickly estimate the sets of best conductance anywhere in the graph as well as how to find a good set of seeds to cover the entire graph with personalized PageRank communities.