1,721,072 research outputs found
A Linear Time Algorithm for Scheduling Outforests with Communication Delays on Two or Three Processors
Full text linkMapping small worlds
No full textSocial networks are usually navigable small worlds: individuals are able to find short chains of acquaintances connecting pairs of unrelated nodes. This property can be explained by the fact that nodes are characterized by a series of properties, such as geographical position, work or educational background; the navigation proceeds towards the node that is "most similar" to the destination. Since nodes are likely to be linked with similar individuals, this strategy permits to quickly reach the destination. We approach the problem of creating the information that makes a network navigable. Starting from a given network, and without any other information, we show how nodes can reconstruct, with a scalable and decentralized algorithm, a "network map ": a d-dimensional layout that places nodes in a way that reflects the network structure, so that navigability is achieved. Euclidean distance on the layout is used as a measure for node similarity, and efficient routing can be simply achieved by iteratively jumping towards the neighbor that is closest to the destination. The network map provides a means for implementing routing on social networks that can be used in "darknets", that is, anonymous networks where nodes establish connections only if they are mutually trusted. Moreover, the distance between nodes on the network map can be used as a measure of node affinity, and may help in various types of network analysis, for instance to help evaluate reputation in webs of trust, or in order to perform "personalized" ranking. © 2007 IEEE
Flow and open shop scheduling on two machines with transportation times and machine-independent processing times in NP-hard
No full text
Neighbourhood maps: decentralized ranking in small‐world P2P networks
No full textReputation in P2P networks is an important tool to encourage cooperation among peers. It is based on ranking of peers according to their past behaviour. In large-scale real-world networks, a global centralized knowledge about all nodes is neither affordable nor practical. For this reason, reputation ranking is often based on local history knowledge available on the evaluating node. This criterion is not optimal, since it ignores useful data about interactions with other peers. In our approach, evaluations of past history create recommendations between nodes, that will be used to form a network called web of trust. Under the assumption that the web of trust has the ubiquitous small-world property, we propose a simple, scalable and decentralized method, called 'neighbourhood maps', which approximates rankings calculated using link-analysis techniques, exploiting the short-distance characteristics of small-world networks. We test our algorithms using data from the OpenPGP web of trust, a real-world network of trust relationships, and by developing a simple simulation of a file-sharing network using an evolutive approach. Our results show that it is sufficient to have maps having size O (√n), where n is the size of the network, in order to have good results. Copyright © 2007 John Wiley & Sons, Ltd
Neighbourhood maps: decentralised ranking in small-world P2P networks
No full textReputation in P2P networks is an important tool to encourage cooperation among peers. It is based on ranking of peers according to their past behaviour. In large-scale real world networks, a global centralised knowledge about all nodes is neither affordable nor practical. For this reason, reputation ranking is often based on local history knowledge available on the evaluating node. This criterion is not optimal, since it ignores useful data about interactions with other peers. We propose a simple, scalable and decentralised method, called "neighbourhood maps", that approximates rankings calculated using link-analysis techniques, exploiting the short-distance characteristics of small-world networks. We test our algorithms using data from the OpenPGP web-of-trust, a real-world network of trust relationships. © 2006 IEEE
Webs of Trust: Choosing Who to Trust on the Internet
No full textHow to decide whether to engage in transactions with strangers? Whether we’re offering a ride, renting a room or apartment, buying or selling items, or even lending money, we need a degree of trust that the others will behave as they should. Systems like Airbnb, Uber, Blablacar, eBay and others handle this by creating systems where people initially start as untrusted, and they gain reputation over time by behaving well. Unfortunately, these systems are proprietary and siloed, meaning that all information about transactions becomes property of the company managing the systems, and that there are two types of barriers to entry: first, whenever new users enter a new system they will need to restart from scratch as untrusted, without the possibility of exploiting the reputation they gained elsewhere; second, new applications have a similar cold-start problem: young systems, where nobody has reputation yet, are difficult to kickstart. We propose a solution based on a web of trust: a decentralized repository of data about past interactions between users, without any trusted third party. We think this approach can solve the aforementioned issue, establishing a notion of trust that can be used across applications while protecting user privacy. Several problems require consideration, such as scalability and robustness, as well as the trade-off between privacy and accountability. In this paper, we provide an overview of issues and solutions available in the literature, and we discuss the directions to take to pursue this project
SOFIA: Social filtering for robust recommendations
No full textDigital content production and distribution has radically changed our business models. An unprecedented volume of supply is now on offer, whetted by the demand of millions of users from all over the world. Since users cannot be expected to browse through millions of different items to find what they might like, filtering has become a popular technique to connect supply and demand: trusted users are first identified, and their opinions are then used to create recommendations. In this domain, users' trustworthiness has been measured according to one of the following two criteria: taste similarity (i.e., "trust those who agree with me"), or social ties (i.e., "trust my friends, and the people that my friends trust"). The former criterion aims at identifying competent users, but is subject to abuse by malicious behaviours. The latter aims at detecting well-intentioned users, but fails to capture the natural subjectivity of tastes. We argue that, in order to be trusted, users must be both well-intentioned and competent. Based on this observation, we propose a novel approach that we call social filtering. We describe SOFIA, an algorithm realising this approach, and validate its performance, in terms of accuracy and robustness, on two real large-scale datasets. © 2008 International Federation for Information Processing
- …
