Graph of user interaction on eBay
http://www.cs.ucr.edu/~michalis/PAPERS/CAMERA-ebayGI08.pdf
This paper discusses how the online auction users of eBay interact and create online social networks. The paper splits up the graph created by the users into three types: “the Trust graph, the Transaction graph, and the Undirected graph for understanding the key properties of the eBay transaction feedback.”
“The Trust graph is a directed graph which represents the eBay reputation system. We draw an edge from a to b if a votes for b. The weight of the edge is the value of the vote (+1, 0, or 1).”
“The Transaction graph is a directed graph which represents the role of users. We draw a line from node a to node b if a buys from b.” “Note that we mention the Transaction graph for completeness, but we do not study this graph here.”
“The Undirected graph consists of undirected edges between nodes that at least one node has left feedback for the other.”
The paper goes on to discuss how each of these graphs are useful for “understanding the key properties of the eBay transaction feedback.”
For the Trust graph, the paper observed that 99% of sellers with negative feedback have less than 10 negative feedbacks; furthermore, feedback is not necessarily reciprocal and negative feedback in and of itself is rare; the negative feedbacks that a user has decrease significantly the “preferential” status of the user.
From the Undirected graph, the paper observes that the graph becomes denser over time; the paper observes graph densification and growth of giant component over time. Linear preferential attachment exists partially as we explain later. Furthermore, the negative feedbacks that a user has decrease significantly the “preferential” status of the user.
Most importantly, the paper observes The eBay graph differs from other scale-free networks as “the rich-club phenomenon does not appear on the eBay graph, though like many networks, it has skewed degree distribution and is disassortative. Another interesting property is that the degree distribution of negative feed- backs is skewed.”
This relates to the course as it combines many of the topics: strong/weak graph theory, network exchange, auctions, and the internet/web/PageRank. The users of eBay are essentially giving the sellers a PageRank via their reviews. eBay is, of course, an auction site. And overall, the graphs created by the users of eBay incorporate a version of Strong/Weak Graph theory because of how the feedback system works: i.e. if a user gives positive feedback to two different sellers, and many other users also gave feedback to one of those sellers, it is likely that the other seller is also a trusted seller.