In this paper, we investigate recommender systems from a network perspective and investigate recommendation networks, where nodes are items (e.g., movies) and edges are constructed from top-N recommendations (e.g., related movies). In particular, we focus on evaluating the reachability and navigability of recommendation networks and investigate the following questions: (i) How well do recommendation networks support navigation and exploratory search? (ii) What is the influence of parameters, in particular different recommendation algorithms and the number of recommendations shown, on reachability and navigability? and (iii) How can reachability and navigability be improved in these networks? We tackle these questions by first evaluating the reachability of recommendation networks by investigating their structural properties. Second, we evaluate navigability by simulating three different models of information seeking scenarios. We find that with standard algorithms, recommender systems are not well suited to navigation and exploration and propose methods to modify recommendations to improve this. Our work extends from one-click-based evaluations of recommender systems towards multi-click analysis (i.e., sequences of dependent clicks) and presents a general, comprehensive approach to evaluating navigability of arbitrary recommendation networks.
Network Analysis Ever since Milgram's small world experiments @cite_3 , researchers have been making efforts to understand and in particular in networks. Kleinberg @cite_11 @cite_28 and Watts @cite_15 formalized the property that a navigable network requires short paths between all (or almost all) nodes @cite_22 . Formally, such a network has a low diameter bounded by a polynomial in @math , where @math is the number of nodes in the network, and a giant component containing almost all the nodes exists @cite_22 . In other words, because the majority of network nodes are connected, it is possible to reach all or almost all of the nodes, given global knowledge of the network. This property is referred to as . The low diameter and the existence of a giant component constitute necessary topological conditions for network navigability. In this paper we apply a set of standard network-theoretic measures including distribution of component sizes and component structure (via the bow tie model) to assess if a network satisfies them.
@cite_22 @cite_28 @cite_3 @cite_15 @cite_11
2164195254 1572272766 1573579329 2070497706 2128678576
The problem of searching for information in networks like the World Wide Web can be approached in a variety of ways, ranging from centralized indexing schemes to decentralized mechanisms that navigate the underlying network without knowledge of its global structure. The decentralized approach appears in a variety of settings: in the behavior of users browsing the Web by following hyperlinks; in the design of focused crawlers [4, 5, 8] and other agents that explore the Web’s links to gather information; and in the search protocols underlying decentralized peer-to-peer systems such as Gnutella [10], Freenet [7], and recent research prototypes [21, 22, 23], through which users can share resources without a central server. In recent work, we have been investigating the problem of decentralized search in large information networks [14, 15]. Our initial motivation was an experiment that dealt directly with the search problem in a decidedly pre-Internet context: Stanley Milgram’s famous study of the small-world phenomenon [16, 17]. Milgram was seeking to determine whether most pairs of people in society were linked by short chains of acquaintances, and for this purpose he recruited individuals to try forwarding a letter to a designated “target” through people they knew on a first-name basis. The starting individuals were given basic information about the target — his name, address, occupation, and a few other personal details — and had to choose a single acquaintance to send the letter to, with goal of reaching the target as quickly as possible; subsequent recipients followed the same procedure, and the chain closed in on its destination. Of the chains that completed, the median number of steps required was six — a result that has since entered popular culture as the “six degrees of separation” principle [11]. Milgram’s experiment contains two striking discoveries — that short chains are pervasive, and that people are able to find them. This latter point is concerned precisely with a type of decentralized navigation in a social network, consisting of people as nodes and links joining It is easier to find short chains between points in some networks than others. The small-world phenomenon — the principle that most of us are linked by short chains of acquaintances — was first investigated as a question in sociology1,2 and is a feature of a range of networks arising in nature and technology3,4,5. Experimental study of the phenomenon1 revealed that it has two fundamental components: first, such short chains are ubiquitous, and second, individuals operating with purely local information are very adept at finding these chains. The first issue has been analysed2,3,4, and here I investigate the second by modelling how individuals can find short chains in a large social network. Social networks have the surprising property of being “searchable”: Ordinary people are capable of directing messages through their network of acquaintances to reach a specific but distant target person in only a few steps. We present a model that offers an explanation of social network searchability in terms of recognizable personal identities: sets of characteristics measured along a number of social dimensions. Our model defines a class of searchable networks and a method for searching them that may be applicable to many network search problems, including the location of data files in peer-to-peer networks, pages on the World Wide Web, and information in distributed databases. Long a matter of folklore, the small-world phenomenon'''' --the principle that we are all linked by short chains of acquaintances --was inaugurated as an area of experimental study in the social sciences through the pioneering work of Stanley Milgram in the 1960''s. This work was among the first to make the phenomenon quantitative, allowing people to speak of the six degrees of separation'''' between any two people in the United States. Since then, a number of network models have been proposed as frameworks in which to study the problem analytically. One of the most refined of these models was formulated in recent work of Watts and Strogatz; their framework provided compelling evidence that the small-world phenomenon is pervasive in a range of networks arising in nature and technology, and a fundamental ingredient in the evolution of the World Wide Web. But existing models are insufficient to explain the striking algorithmic component of Milgram''s original findings: that individuals using local information are collectively very effective at actually constructing short paths between two points in a social network. Although recently proposed network models are rich in short paths, we prove that no decentralized algorithm, operating with local information only, can construct short paths in these networks with non-negligible probability. We then define an infinite family of network models that naturally generalizes the Watts-Strogatz model, and show that for one of these models, there is a decentralized algorithm capable of finding short paths with high probability. More generally, we provide a strong characterization of this family of network models, showing that there is in fact a unique model within the family for which decentralized algorithms are effective.