Mais uma palestra do Ciclo de Seminários do PESC. Teremos no púlpito o Prof. Don Towsley (UMass Amherst, EUA) que há muitos anos nos visita, sempre em agosto, por conta de colaborações científicas com professores dentro e fora do PESC e pelo seu apreço pela cidade. O Don é um dos pesquisadores mais citados da Computação e alguns de seus artigos influentes possuem mais de mil citações (15 possuem mais de 500!). Nesta ocasião sua palestra será sobre amostragem de pares de vértices em grafos grandes com aplicações a Redes Sociais Online. Por exemplo, como estimar o número de amizades entre tricolores e flamenguistas no Facebook?

Dia/horário/local:
Quarta, 19 de agosto de 2015, 11 horas, sala H-324B

Participe e ajude na divulgação!  Clique para mais detalhes.  

----
Palestrante:
Don Towsley - Distinguished University Professor, University of Massachusetts (UMass), Amherst, EUA.

Título:
Sampling Node Pairs in Large Graphs

Resumo:
Characterizing user pair relationships is important for applications such as friend recommendation and interest targeting in online social networks (OSNs). Due to the large scale nature of such networks, it is infeasible to enumerate all user pairs and so sampling is necessarily used. In this talk I focus on this problem from two perspectives, from an OSN service provider with access to the complete network and from a suspicious BBN summer intern with limited access to the network.
Characterizing pair relationships poses a great challenge to an OSN provider even when it possesses the complete topology. The reason is that when sampling techniques, e.g., uniform vertex sampling (UVS) are naively applied, they can introduce large biases, in particular, for estimating similarity distribution statistics of user pairs such as network homophily. Estimating statistics of user pairs is more challenging in the absence of the complete topology information, since an unbiased sampling technique such as UVS is usually not allowed, and exploring the OSN topology is expensive. To address these challenges, we present unbiased sampling methods to characterize user pair properties based on UVS and random walks (RWs) respectively. We evaluate our methods to show their accuracy and efficiency. Finally, we apply our methods to several OSNs and characterize the homophily present in each.