The Impact of Social Networks on Multi-Agent Recommender Systems
  Awerbuch et al.'s approach to distributed recommender systems (DRSs) is to
have agents sample products at random while randomly querying one another for
the best item they have found; we improve upon this by adding a communication
network. Agents can only communicate with their immediate neighbors in the
network, but neighboring agents may or may not represent users with common
interests. We define two network structures: in the ``mailing-list model,''
agents representing similar users form cliques, while in the ``word-of-mouth
model'' the agents are distributed randomly in a scale-free network (SFN). In
both models, agents tell their neighbors about satisfactory products as they
are found. In the word-of-mouth model, knowledge of items propagates only
through interested agents, and the SFN parameters affect the system's
performance. We include a summary of our new results on the character and
parameters of random subgraphs of SFNs, in particular SFNs with power-law
degree distributions down to minimum degree 1. These networks are not as
resilient as Cohen et al. originally suggested. In the case of the widely-cited
``Internet resilience'' result, high failure rates actually lead to the
orphaning of half of the surviving nodes after 60% of the network has failed
and the complete disintegration of the network at 90%. We show that given an
appropriate network, the communication network reduces the number of sampled
items, the number of messages sent, and the amount of ``spam.'' We conclude
that in many cases DRSs will be useful for sharing information in a multi-agent
learning system.
