Adaptive Social Recommendation

In the current age of information overload, information-sharing social networks like Twitter play a crucial role in the propagation of information and the formation of opinions. In these systems, a user can follow other users and in turn receive information from them. The working principle is that of social recommendation, for which users actively select their preferred information sources. The influence, or "leadership", is then measured by the number of follower she has. In this paper we performed an empirical analysis of four information-sharing systems (Delicious, Flickr, Twitter, YouTube), revealing that the topology of the resulting networks is characterised by a scale-free leadership structure

Leadership distribution (measured by number of followers) in various social networks, with best power-law fit.

We developed a model for such systems in which the diffusion of information on the leader-follower network occurs simultaneously with the evolution of the network itself, with the two dynamics influencing each other (models of this type are called "adaptive"). In a nutshell, the model works as follows:

This model can be implemented via an agent-based framework. In this paper we showed that a broad distribution of the leadership emerges also in the model, due to a "good get richer" phenomenon that is more profound than the "rich get richer'' as it relates the attractiveness of a node to its intrinsic qualities. We further showed that incorporating user reputation in the similarity score can substantially improve the outcome, by enhancing the diffusion of high-quality content.

Optimization of the Network Topology

In the model described above, the network evolution is driven by an interplay between topology and dynamics, with the leader updating procedure playing a crucial role. The question is: how to find good information sources for each user? 

In this paper we first conducted an empirical analysis on different information-sharing social networks, showing that these systems are characterised by very high values of link reciprocity and clustering coefficient, because users that are close in the network are likely to have common interests. We drew inspiration from these observations to define local selection strategies, for which new candidate leaders are picked in the neighborhood of the target user. However a common problem in optimization tasks is that local search strategies often gets stuck in local minima, representing a sub-optimal assignment of leaders. We thus added some small percentage of randomness in the selection, mimicking users establishing weak ties by random encounters. 

When assessing the features of the resuting network topology from the viewpoint of user' satisfaction and network adaptation, such local rewiring rules display the same performance of a global search strategy, the latter being very demanding for large-scale networks and also unfeasible without a centralized control. Hence the local search rules create networks which are effective in information diffusion and resemble structures resulting from real human activity.

In this paper we exploited these findings to implement the model as a peer-to-peer system.

Degree of users satisfaction for different leader selection strategies, as a function of the news evaluated in the model.
Degree of network optimization for different leader selection strategies, as a function of the news evaluated in the model.