Restricted Area  |

InWeb-SCNARC Workshop on Complex Networks Research

January 18th, 2013

ICEx – Room 2077

Department of Computer Science

Universidade Federal de Minas Gerais


The goal of the InWeb-SCNARC Workshop on Complex Networks Research is to debate state of the art research in that area and foster cooperation between InWeb and SCNARC through presentations of the research being pursued at both institutions and discussion of joint projects and cooperation activities.


9:30 – 10:00 – Welcome coffee

10:00 – 11:00 – Research on Complex Networks at InWeb

Virgilio Almeida – InWeb/UFMG

11:00 – 12:00 – The Influence of Committed Minorities on Social Consensus

Boleslaw Szymanski – SCNARC/RPI

Human behavior is profoundly affected by the influenceability of individuals and the social networks that link them together. In the sociological context, spread of ideas, ideologies and innovations is often studied to understand how individuals adopt new states in behavior, opinion, ideology or consumption through the influence of their neighbors. In this paper, we study the evolution of opinions and the dynamics of its spread. We use the binary agreement model starting from an initial state where all individuals adopt a given opinion B, except for a fraction p<1 of the total number of individuals who are committed to opinion A. In a generalization of this model, we consider also the initial state in which some of the individuals holding opinion B are also committed to it. Committed individuals are defined as those who are immune to influence but they can influence others to alter their opinion through the usual prescribed rules for opinion change. The question that we specifically ask is: how does the consensus time vary with the size of the committed fraction? More generally, our work addresses the conditions under which an inflexible set of minority opinion holders can win over the rest of the population. We show that the prevailing majority opinion in a population can be rapidly reversed by a small fraction p of randomly distributed committed agents who are immune to influence. Specifically, we show that when the committed fraction grows beyond a critical value pc=9.79%, there is a dramatic decrease in the time, Tc, taken for the entire population to adopt the committed opinion. Below this value, the consensus time is proportional to the exponential function of the network size, while above this value this time is proportional to the logarithm of the network size. This has enormous impact on stability/instability of the society opinions. We also discuss conditions under which the committed minority can rapidly reverse the influenceable majority even if the latter is supported by a small fraction of individuals committed to their opinion. The results are relevant in understanding and influencing the social perceptions of policies and products at different scales.

12:00 – 14:00 – Lunch

14:00 – 14:40 –  Identifying Experts and Spammers in the Twitter Social Network

Fabricio Benevenuto – UFMG

Microblogging sites like Twitter have emerged as a popular platform for exchanging real-time information on the Web. Twitter is used by hundreds of millions of users ranging from popular news organizations and celebrities to domain experts in a variety of fields. As a result, the quality of information posted in this system is highly variable and finding the users that are authoritative sources of relevant and trust-worthy information is a key challenge. In this talk, I will present our recent research efforts to address this challenge. First, I focus on understanding and combating link farming activity in Twitter. Users, especially spammers, resort to link farming to acquire large numbers of follower links in the social network. Acquiring followers not only increases the size of a user’s direct audience, but also contributes to the perceived influence of the user, which in turn impacts the ranking of the user’s tweets by search engines. I will first discuss results from our recent studies investigating link farming activity in the Twitter network and then propose mechanisms to discourage the activity. Second, I focus on the problem of finding topic experts in Twitter. I will propose a new methodology that relies on the wisdom of the Twitter crowds. I will first describe how we mined information to build an expert search system for Twitter and then present results from a real-world deployment.

14:40 – 15:20 – Forecasting in the NBA and Other Team Sports: Network Effects in Action

Pedro Melo – UFMG

The multi-million sports-betting market is based on the fact that the task of predicting the outcome of a sports event is very hard. Even with the aid of an uncountable number of descriptive statistics and background information, only a few can correctly guess the outcome of a game or a league. In this talk, we first explore and describe a new trend on the sports analytics field,  which aims to move away from the traditional way of predicting sports events by using network effects instead of plain box-score statistics. Secondly, we describe our approach, which models sports leagues as networks of players and teams where the only information available is the work relationships among them. We propose two network-based models to predict the behavior of teams in sports leagues. These models are parameter-free, that is, they do not have a single parameter, and moreover are sport-agnostic: they can be applied directly to any team sports league. First, we view a sports league as a network in evolution, and we infer the implicit feedback behind network changes and properties over the years. Then, we use this knowledge to construct the network-based prediction models, which can, with a significantly high probability, indicate how well a team will perform over a season. We compare our proposed models with other prediction models in two of the most popular sports leagues: the National Basketball Association (NBA) and the Major League Baseball (MLB). Our model shows consistently good results in comparison with the other models and, relying upon the network properties of the teams, we achieved a 14% rank prediction accuracy improvement over our best competitor.

15:20 – 16:00 – On the Separability of Structural Classes of Communities

Bruno Abrahao – Cornell

Three major factors govern the intricacies of community extraction in networks: (1) the application domain includes a wide variety of networks of fundamentally di erent natures, (2) the literature o ers a multitude of disparate community detection algorithms, and (3) there is no consensus characterizing how to discriminate communities from non-communities. In this talk, we present a comprehensive analysis of community properties through a class separability framework. Our approach enables the assessment of the structural dissimilarity among the output of multiple community detection algorithms and between the output of algorithms and communities that arise in practice. To demonstrate this concept, we furnish our method with a large set of structural properties and multiple community detection algorithms. Applied to a diverse collection of large scale network datasets, the analysis reveals that (1) the di fferent detection algorithms extract fundamentally di erent structures; (2) the structure of communities that arise in practice is closest to that of communities that random-walk-based algorithms extract, although still signi cantly di erent from that of the output of all the algorithms; and (3) a small subset of the properties are nearly as discriminative as the full set, while making explicit the ways in which the algo rithms produce biases. Our framework enables an informed choice of the most suitable community detection method for a given purpose and network and allows for a comparison of existing community detection algorithms while guiding the design of new ones.

16:00 – 16:40 – Popularity  Evolution of User Generated Content: Characterization and Prediction

Jussara Almeida – InWeb/UFMG

Understanding and predicting how the popularity of user generated content evolves over time have attracted a lot of interest recently, as such knowledge can drive and support the effective design of a variety of different services such as content distribution, advertising, content recommendation, to name a few. The multitude of different factors  that might impact how popularity of a piece of content evolves, some of which are specific to the particular application and platform where the content is published and shared, makes  popularity prediction a particular challenging problem.  In this talk, I will discuss our on-going efforts in characterizing and predicting  the popularity evolution of user generated content, focusing on two specific contexts: YouTube videos and Foursquare tips.  Our prediction methods are based on classification and regression models, and exploit different sets of  user and/or content related features. For YouTube videos,   I will also discuss the problem of predicting the popularity trend of a piece of content.

16:40 – 17:00 – Closing Remarks Make a javascript code that implements depth-first search 2

Copyright © 2013 InWeb - Instituto Nacional de Ciência e Tecnologia para a Web - All rights reserved.
XHTML 1.1 OKXHTML 1.1 CSS 2.1 OKCSS 2.1 razz