Improving the Effectiveness of Eigentrust in Computing the Reputation of Social Agents in Presence of Collusion.

The introduction of trust-based approaches in social scenarios modeled as multi-agent systems (MAS) has been recognized as a valid solution to improve the effectiveness of these communities. In fact, they make interactions taking place in social scenarios much fruitful as possible, limiting or even avoiding malicious or fraudulent behaviors, including collusion. This is also the case of multi-layered neural networks (NN), which can face limited, incomplete, misleading, controversial or noisy datasets, produced by untrustworthy agents. Many strategies to deal with malicious agents in social networks have been proposed in the literature. One of the most effective is represented by Eigentrust, often adopted as a benchmark. It can be seen as a variation of PageRank, an algorithm for determining result rankings used by search engines like Google. Moreover, Eigentrust can also be viewed as a linear neural network whose architecture is represented by the graph of Web pages. A major drawback of Eigentrust is that it uses some additional information about agents that can be a priori considered particularly trustworthy, rewarding them in terms of reputation, while the non pre-trusted agents are penalized. In this paper, we propose a different strategy to detect malicious agents which does not modify the real reputation values of the honest ones. We introduce a measure of effectiveness when computing reputation in presence of malicious agents. Moreover, we define a metric of error useful to quantitatively determine how much an algorithm for the identification of malicious agents modifies the reputation scores of the honest ones. We have performed an experimental campaign of mathematical simulations on a dynamic multi-agent environment. The obtained results show that our method is more effective than Eigentrust in determining reputation values, presenting an error which is about a thousand times lower than the error produced by Eigentrust on medium-sized social networks.

Estimating Graph Robustness Through the Randic Index.

Graph robustness-the ability of a graph to preserve its connectivity after the loss of nodes and edges-has been extensively studied to quantify how social, biological, physical, and technical systems withstand to external damages. In this paper, we prove that graph robustness can be quickly estimated through the Randic index, a parameter introduced in chemistry to study organic compounds. We prove that Erdos-Renyj (ER) graphs are a good specimen of robust graphs because they lack of a clear modular structure; we derive an analytical expression for the Randic index of ER graphs and use ER graphs as an effective term of comparison to decide about graph robustness. Experiments on real datasets from different domains (scientific collaboration networks, content-sharing systems, co-purchase networks from an e-commerce platform, and a road network) show that real-life large graphs are more robust than ER ones with the same number of nodes and edges. We also observe that if node degree distribution closely follows a power law, then few edges contribute for more than half of the Randic index, thus indicating that the selective removal of those edges has devastating impact on graph robustness. Finally, we describe sampling-based algorithms to efficiently but accurately approximate the Randic index.

Trust and compactness in social network groups.

Understanding the dynamics behind group formation and evolution in social networks is considered an instrumental milestone to better describe how individuals gather and form communities, how they enjoy and share the platform contents, how they are driven by their preferences/tastes, and how their behaviors are influenced by peers. In this context, the notion of compactness of a social group is particularly relevant. While the literature usually refers to compactness as a measure to merely determine how much members of a group are similar among each other, we argue that the mutual trustworthiness between the members should be considered as an important factor in defining such a term. In fact, trust has profound effects on the dynamics of group formation and their evolution: individuals are more likely to join with and stay in a group if they can trust other group members. In this paper, we propose a quantitative measure of group compactness that takes into account both the similarity and the trustworthiness among users, and we present an algorithm to optimize such a measure. We provide empirical results, obtained from the real social networks EPINIONS and CIAO, that compare our notion of compactness versus the traditional notion of user similarity, clearly proving the advantages of our approach.