Absorbing random walk centrality

Our paper on absorbing random-walk centrality will be presented at ICDM next week. It is a joint work with Harry Mavroforakis and Aristides Gionis.

What is absorbing random-walk centrality (ARW-centrality)?

It is a measure that tells us how central one set of nodes (let’s call it C) is with respect to another set of nodes (let’s call it Q) in a graph. As an example, consider the graph shown in the figure below. In that graph, we use color to indicate the two sets of nodes — Q is shown in red and C is shown in blue. Continue reading

Finding similar neighborhoods across cities

By Geraud Le Falher, Michael Mathioudakis, and Aris Gionis

Our friend Oliver lives in London, where he works as a consultant for a big financial company. Occasionally, he takes a business trip to another major city, to seal a major deal, and make major buck for his boss. Of course, Oliver being Oliver, he always finds the time to enjoy whatever city he happens to be. When in London, he likes to suit up and hang out in Soho, a “predominantly fashionable district of upmarket restaurants.” He would like to do that also in Rome, where he’s flying to next week, but he doesn’t know much about that city. Where is the Soho of Rome? What neighborhood of Rome is most similar to Soho? Continue reading

Overlapping community detection in labeled graphs

In a recent paper with Esther Galbrun and Nikolaj Tatti, presented in the journal of Data Mining and Knowledge Discovery, we worked on the problem of discovering overlapping communities in networks with labeled vertices. The model is motivated by social networks, where vertex labels are used to represent information about individuals, such as occupation, hobbies, preferences, etc. The hypothesis is that the vertex labels can be used to derive and explain the community structure in the network. Continue reading

From “I love you babe” to “leave me alone” — romantic relationship breakups on twitter

Our recent paper (together with Ingmar Weber and Sonia Dal Cin) studying Romantic Relationship Breakups on Twitter was accepted at the 6th International Conference on Social Informatics (SocInfo 2014). In the paper, we identified pairs of Twitter users who were in a romantic relationship and studied various psychological processes surrounding relationship dissolution. Continue reading

How graph algorithms can help to find interesting events

In our recent KDD paper, with Polina Rozenshtein, Aris Anagnostopoulos, and Nikolaj Tatti, we worked on the problem of finding events in graphs. We abstracted the event-finding problem with the following simple formulation: Given a graph with node weights and edge distances, find a subset of nodes (the event) that have large sum of weights and are well connected. In the paper we showed how to use this formulation to find interesting events in real-world datasets. Continue reading

Co-following on twitter

Our recent paper about second order “Co-Following” on Twitter was accepted in ACM Hypertext 2014 (short paper). This is work that I did mostly while I was at QCRI, with Ingmar Weber. The idea is that two Twitter users whose followers have similar friends are similar, even though they might not share any common followers. The intuition behind why this works is that the friends of a user typically represent the interests of that user, and so if two Twitter users have followers who have similar interests, they might be similar. Continue reading

The network response problem

Understanding the mechanisms of influence and contagion in human interactions is a central focal point in today’s research, in computational social science, machine learning, and data mining. Quantifying the effects of social influence was the question behind the controversial recently-published facebook experiment, which aimed to show that emotional contagion occurs on social networks (the NYT’s article).

Continue reading