Finding the bias and prestige of nodes in networks based on trust scores
Finding the bias and prestige of nodes in networks based on trust scores
复制标题
根据信任评分查找网络中节点的偏见和声望
DOI：
10.1145/1963405.1963485
复制
发表时间：
2011
影响因子：
2.5
通讯作者：
Arnab Bhattacharya
中科院分区：
文献类型：
--
作者：
Abhinav Mishra;Arnab Bhattacharya
许多现实生活中的图（例如社交网络和点对点网络）通过使用信任分数来标记边缘来捕获节点之间的关系。此类网络的重要用途包括信任预测、在本地子图中查找最可靠或最受信任的节点等。对于许多此类应用程序，评估节点的信誉和偏差至关重要。节点的偏差表示其信任/不信任其邻居的倾向，并且与真实性密切相关。如果一个节点信任其所有邻居，那么它对另一个节点的可信推荐就不太可靠。它基于这样的想法：高偏差节点的推荐权重应该较小。在本文中，我们提出了一种算法来计算网络中节点的偏差和声望，其中边权重表示信任分数。与大多数其他基于图的算法不同，即使边权重不一定为正，我们的方法也能工作。该算法是迭代的，运行时间为 O(km)，其中 k 是迭代次数，m 是网络中边的总数。该算法还表现出其他几个理想的特性。它很快收敛到一个独特的值。此外，任何特定迭代中的偏差和声望值的误差都是有限的。此外，实验表明我们的模型非常符合平衡理论（朋友的敌人就是敌人等）等社会理论。
Many real-life graphs such as social networks and peer-to-peer networks capture the relationships among the nodes by using trust scores to label the edges. Important usage of such networks includes trust prediction, finding the most reliable or trusted node in a local subgraph, etc. For many of these applications, it is crucial to assess the prestige and bias of a node. The bias of a node denotes its propensity to trust/mistrust its neighbours and is closely related to truthfulness. If a node trusts all its neighbours, its recommendation of another node as trustworthy is less reliable. It is based on the idea that the recommendation of a highly biased node should weigh less. In this paper, we propose an algorithm to compute the bias and prestige of nodes in networks where the edge weight denotes the trust score. Unlike most other graph-based algorithms, our method works even when the edge weights are not necessarily positive. The algorithm is iterative and runs in O(km) time where k is the number of iterations and m is the total number of edges in the network. The algorithm exhibits several other desirable properties. It converges to a unique value very quickly. Also, the error in bias and prestige values at any particular iteration is bounded. Further, experiments show that our model conforms well to social theories such as the balance theory (enemy of a friend is an enemy, etc.).