Patterns of File-Sharing in an Enterprise: Authors, Contributors, Collectors, and Lurkers

Great work by Michael Muller of IBM

We describe Cattail, an experimental enterprise file-sharing service in IBM. Over the past several years, 17985 Cattail users have uploaded 132041 files, which have been used by 115538 users. In addition 15240 people have shared 75951 of the files with other users, and, 5444 people have created 12461 collections comprising 60476 of the files. We use this rich set of data to characterize file-sharing in the enterprise. This talk will describe Cattail, and the factors that lead to a file being of use to other people, analyzed in two timeframes: over the lifetime of a file, and within the microstructure of a user's session. We will also explore emergent roles within the file-sharing system, and we will conclude with a look at the work of lurkers in the enterprise.

Importance Algorithms by Jung

>>> BaryCenter(someGraph)
A simple node importance ranker based on the total shortest path of the node. More central nodes in a connected component will have smaller overall shortest paths, and 'peripheral' nodes on the network will have larger overall shortest paths. Runing this ranker on a graph with more than one connected component will arbitarily mix nodes from both components. For this reason you should probably run this ranker on one
component only (but that goes for all rankers).
A simple example of usage is:
BaryCenter ranker = new BaryCenter(someGraph);
ranker.evaluate();
ranker.printRankings();


>>>BetweennessCentrality(someGraph)
Computes betweenness centrality for each vertex and edge in the graph. The result is that each vertex and edge has a UserData element of type MutableDouble whose key is 'centrality.BetweennessCentrality'.
Note: Many social network researchers like to normalize the betweenness values by dividing the values by (n-1)(n-2)/2. The values given here are unnormalized.
A simple example of usage is:
BetweennessCentrality ranker = new BetweennessCentrality(someGraph);
ranker.evaluate();
ranker.printRankings();

>>> DegreeDistributionRanker(someGraph)
A simple node importance ranker based on the degree of the node. The user can specify whether s/he wants to use the indegree or the outdegree as the metric. If the graph is undirected this option is effectively ignored. So for example, if the graph is directed and the user chooses to use in-degree, nodes with the highest in-degree will be ranked highest and similarly nodes with the lowest in-degree will be ranked lowest.
A simple example of usage is:
DegreeDistributionRanker ranker = new DegreeDistributionRanker(someGraph);
ranker.evaluate();
ranker.printRankings();


>>> HITS(someGraph)
Calculates the "hubs-and-authorities" importance measures for each node in a graph. These measures are defined recursively as follows:
The *hubness* of a node is the degree to which a node links to other important authorities
The *authoritativeness* of a node is the degree to which a node is pointed to by important hubs
Note: This algorithm uses the same key as HITSWithPriors for storing rank sccores.
A simple example of usage is:
HITS ranker = new HITS(someGraph);
ranker.evaluate();
ranker.printRankings();


>>> HITSWithPriors(someGraph,0.3,rootSet)
Algorithm that extends the HITS algorithm by incorporating root nodes (priors). Whereas in HITS the importance of a node is implicitly computed relative to all nodes in the graph, now importance is computed relative to the specified root nodes.
A simple example of usage is:
HITSWithPriors ranker = new HITSWithPriors(someGraph,0.3,rootSet);
ranker.evaluate();
ranker.printRankings();


>>> KStepMarkov(someGraph,rootSet,6,null)
Algorithm variant of PageRankWithPriors that computes the importance of a node based upon taking fixed-length random walks out from the root set and then computing the stationary probability of being at each node. Specifically, it computes the relative probability that the markov chain will spend at any particular node, given that it start in the root set and ends after k steps.
A simple example of usage is:
KStepMarkov ranker = new KStepMarkov(someGraph,rootSet,6,null);
ranker.evaluate();
ranker.printRankings();


>>> MarkovCentrality


>>> PageRank(someGraph,0.15)
This algorithm measures the importance of a node in terms of the fraction of time spent at that node relative to all other nodes. This fraction is measured by first transforming the graph into a first-order Markov chain where the transition probability of going from node u to node v is equal to (1-alpha)*[1/outdegree(u)] + alpha*(1/|V|) where |V| is the # of vertices in the graph and alpha is a parameter typically set to be between 0.1 and 0.2 (according to the authors). If u has no out-edges in the original graph then 0 is used instead of 1/outdegree(v). Once the markov chain is created, the stationary probability of being at each node (state) is computed using an iterative update method that is guaranteed to converge if the markov chain is ergodic.
A simple example of usage is:
PageRank ranker = new PageRank(someGraph,0.15);
ranker.evaluate();
ranker.printRankings();

>>> PageRankWithPriors(someGraph,0.3,1,rootSet,null)
Algorithm that extends the PageRank algorithm by incorporating root nodes (priors). Whereas in PageRank the importance of a node is implicitly computed relative to all nodes in the graph now importance is computed relative to the specified root nodes.
Note: This algorithm uses the same key as PageRank for storing rank sccores
A simple example of usage is:
PageRankWithPriors ranker = new PageRankWithPriors(someGraph,0.3,1,rootSet,null);
ranker.evaluate();
ranker.printRankings();

>>> RandomWalkBetweenness(someGraph) !!! undirected
Computes betweenness centrality for each vertex in the graph. The betweenness values in this case are based on random walks, measuring the expected number of times a node is traversed by a random walk averaged over all pairs of nodes. The result is that each vertex has a UserData element of type
MutableDouble whose key is 'centrality.RandomWalkBetweennessCentrality'
A simple example of usage is:
RandomWalkBetweenness ranker = new RandomWalkBetweenness(someGraph);
ranker.evaluate();
ranker.printRankings();


>>> RandomWalkBetweenness(someGraph,someSource,someTarget)
Computes s-t betweenness centrality for each vertex in the graph. The betweenness values in this case are based on random walks, measuring the expected number of times a node is traversed by a random walk from s to t. The result is that each vertex has a UserData element of type
MutableDouble whose key is 'centrality.RandomWalkBetweennessCentrality'
A simple example of usage is:
RandomWalkSTBetweenness ranker = new RandomWalkBetweenness(someGraph,someSource,someTarget);
ranker.evaluate();
ranker.printRankings();


>>> VoltageRanker
Ranks vertices in a graph according to their 'voltage' in an approximate solution to the Kirchoff equations. This is accomplished by tying "source" vertices to specified positive voltages, "sink" vertices to 0 V, and iteratively updating the voltage of each other vertex to the (weighted) average of the voltages of its neighbors. The resultant voltages will all be in the range [0, max] where max is the largest voltage of any source vertex (in the absence of negative source voltages; see below). A few notes about this algorithm's interpretation of the graph data: Higher edge weights are interpreted as indicative of greater influence/effect than lower edge weights. Negative edge weights (and negative "source" voltages) invalidate the interpretation of the resultant values as voltages. However, this algorithm will not reject graphs with negative edge weights or source voltages.Parallel edges are equivalent to a single edge whose weight is the sum of the weights on the parallel edges. Current flows along undirected edges in both directions, but only flows along directed edges in the direction of the edge.


>>> WeightedNIPaths(someGraph,2.0,6,rootSet)
This algorithm measures the importance of nodes based upon both the number and length of disjoint paths that lead to a given node from each of the nodes in the root set. Specifically the formula for measuring the importance of a node is given by: I(t|R) = sum_i=1_|P(r,t)|_{alpha^|p_i|} where alpha is the path decay coefficient, p_i is path i and P(r,t) is a set of maximum-sized node-disjoint paths from r to t.
This algorithm uses heuristic breadth-first search to try and find the maximum-sized set of node-disjoint paths between two nodes. As such, it is not guaranteed to give exact answers.
A simple example of usage is:
WeightedNIPaths ranker = new WeightedNIPaths(someGraph,2.0,6,rootSet);
ranker.evaluate();
ranker.printRankings();

Strong Social Networks

A well-written article (pdf) reports on the work by Oxford folks (previous post). Plus, it says that a "pair of Oxford physicists, Neil Johnson and Sean Gourley, have teamed up with social scientists at the Conflict Analysis Resource Center (CERAC), based in Bogotá"

"When the researchers graphed all the attacks within a given conflict, with the number of attacks plotted against the number killed in each, it produces a fat-tailed exponential curve. And the exponent of the function, which determines the curve’s shape, is nearly always the same. “Terrorism and guerrilla warfare everywhere in the world has a signature of about 2.5,” says Gourley. Plotting the distribution of these events over time produces another, distinctive signature.

The weakness of weak ties

This is a very interesting paper: Structure and tie strengths in mobile communication networks. It studies the communication patterns of millions of mobile phone users by arranging them in a big weighted social network. The weight between two individuals corresponds to the aggregated duration of calls between them.

Findings:
"Weak ties appear to be crucial for maintaining the network’s structural integrity, but strong ties play an important role in maintaining local communities. Both weak and strong ties are ineffective, however, when it comes to information transfer, given that most news in the real simulations reaches an individual for the first time through ties of intermediate strength." ..."The speed of spread then depended on the strength of each link. The results suggest that information spreads most quickly via links of intermediate strength, or medium length calls. This is because information spreads slowly through weaker links, or shorter calls, and stronger links tend to bind only a limited number of people."

Consequence:
To enhance the spreading of information, one needs to intentionally force it through the intermediate- to weak-strenght ties (while avoiding hubs!)

Robustness of community structure in networks

"The discovery of community structure is a common challenge in the analysis of network data. Many methods have been proposed for finding community structure, but few have been proposed for determining whether the structure found is statistically significant or whether, conversely, it could have arisen purely as a result of chance. In this paper we show that the significance of community structure can be effectively quantified by measuring its robustness to small perturbations in network structure. We propose a suitable method for perturbing networks and a measure of the resulting change in community structure and use them to assess the significance of community structure in a variety of networks, both real and computer generated." Source

Does your data follow a power-law distribution?

Power-law distributions in empirical data (htm)

Science paper (pdf)

Recommenders Everywhere - WikiLens

Here is the talk. "Suppose you have a passion for items of a certain type, and you wish to start a recommender system around those items. You want a system like Amazon or Epinions, but for cookie recipes, local theater, or microbrew beer. How can you set up your recommender system without assembling complicated algorithms, large software infrastructure, a large community of contributors, or even a full catalog of items?

WikiLens is open source software that enables anyone, anywhere to start a community-maintained recommender around any type of item. We introduce five principles for community-maintained recommenders that address the two
key issues: (1) community contribution of items and associated information; and (2) finding items of interest. Since all recommender communities start small, we look at feasibility and utility in the small world, one with few users, few items, few ratings. We describe the features of WikiLens, which are based on our principles, and give lessons learned from two years of experience running
wikilens.org."

The Natural Pattern Behind our Votes

From 30 years of elections around the world: "The most important factor determining a candidate’s success compared with his rivals in the same party turns out to be his or her personal ability to connect with the public."

How opinions form?
Person-to-person process is enough to explain the data! "In their model, they supposed that each candidate starts out trying to convince others to vote in their favour. Those he or she convinces, then try to convince others. These influences percolate through the scoial net until everyone has made a decision."
Consequence
Candidates should focus on WHO they contact - influential people may easily convince others.
More on this pdf.

The wireless epidemic

The wireless epidemic by Jon Kleinberg

At one end are network models that reflect strong spatial effects, with nodes at fixed positions in two dimensions, each connected to a small number of other nodes a short distance away [9]. At the other end are ‘scale-free’ networks, which are essentially unconstrained by physical proximity, and in which the number of contacts per node are widely spread [14]. Models based on human travel data occupy an intermediate position in this spectrum of spatial constraints. The different network structures lead in turn to qualitative differences in the way epidemics spread: whereas epidemics can persist at arbitrarily low levels of virulence in scale-free networks[14,15], epidemics in simple two-dimensional models need a minimum level of virulence to prevent
them from dying out quickly [9].

Bluetooth ...is disrupting this dichotomy by making possible computer-virus outbreaks whose progress closely tracks human mobility patterns. These types of wireless worm are designed to infect mobile devices such as cell phones, and then to continuously scan for other devices within a few tens of metres or less, looking for new targets. A computer virus thus becomes something you catch not necessarily from a compromised computer halfway around the world, but possibly from the person sitting next to you on a bus, or at a nearby table in a restaurant.

9. Durrett, R. SIAM Rev. 41, 677–718 (1999).
14. Pastor-Satorras, R. & Vespignani, A. Phys. Rev. Lett. 86, 3200–3203 (2000).
15. Berger, N., Borgs, C., Chayes, J. T. & Saberi, A. I. Proc. 16th ACM Symp. Discr. Algor. 301–310 (ACM, New York, 2005).

The impact of social structure on economic outcomes

Some extracts from The impact of social structure on economic outcomes.

4 core principles:

1) Norms and Network Density. ... the denser a network, the more unique paths along which information, ideas and influence can travel between any two nodes. Thus, greater density makes ideas about proper behavior more likely to be encountered repeatedly, discussed and fixed; it also renders deviance from resulting norms harder to hide and, thus, more likely to be punished. ... larger groups will have lower network density because people have cognitive, emotional, spatial and temporal limits on how many social ties they can sustain.

2) The Strength of Weak Ties. More novel information flows to individuals through weak than through strong ties. Because our close friends tend to move in the same circles that we do, the information they receive overlaps considerably with what we already know. ...This is so even though close friends may be more interested than acquaintances in helping us; social structure can dominate motivation. This is one aspect of what I have called “the strength of weak ties” (Granovetter, 1973, 1983). ... if cliques are connected to one another, it is mainly by weak ties. This implies that such ties determine the extent of information diffusion in large-scale social structures. One outcome is that in scientific fields, new information and ideas are more efficiently diffused through weak ties.

3) The Importance of “Structural Holes.” Burt (1992) extended and reformulated the “weak ties” argument by emphasizing that ... the strategic advantage that may be enjoyed by individuals with ties into multiple networks that are largely separated from one another. Insofar as they constitute the only route through which information or other resources may flow from one network sector to another, they can be said to exploit “structural holes” in the network. ... One reason resources may be unconnected is that they reside in separated networks of individuals or transactions. Thus, the actor who sits astride structural holes in networks (as described in Burt, 1992) is well placed to innovate.

Prospective employers and employees prefer to learn about one another from personal sources whose information they trust. This is an example of what has been called “social capital” (Lin, 2001). ... for goods where assessment is difficult, such as used cars, legal advice and home repairs, one-quarter to one-half of purchases in the United States are made through personal networks.

Studies of peasant markets often suggest that “clientelization,” defined as dealing exclusively with known buyers and sellers, raises prices above their competitive level

Social relations are also closely linked to productivity. Economic models attribute productivity to personal traits, modifiable by learning. But one’s position in a social group can also be a central influence on productivity, for several reasons. One is that many tasks cannot be accomplished without serious cooperation from
others; another is that many tasks are too complex and subtle to be done “by the book” (which is why the “rulebook slowdown” is a potent labor weapon) and require the exercise of “tacit knowledge” appropriable only through interaction with knowledgeable others.

“loyalty systems”—attempts to elicit cooperation from workers deriving not only from incentives but also from identification with the firm or with some set of individuals that encourages high standards and productivity.

Your personal data? If you can't take it out, don't put it in

Many companies are going open. Are they? Take OpenSocial (APIs by Google), Open Handset Alliance (alliance of 34 companies led by Google), and Open Media (an initiative announced by Bebo). What is common to all three initiatives, apart from the use of the word "open", is that none is directly aimed at benefiting the user (here).

Google is clearly "not responding to consumer needs. The applications it has
demonstrated using Android are readily available on existing phones and operating systems. Users are not crying out for yet another interface for their phones".

Tim O'Reilly: "We don't want to have the same application on multiple social networks, we want applications that can use data from multiple social networks".


In another FT's article: "the technology industry has little financial incentive to reduce switching costs. While users are free to switch from one service to another at any time, the critical question is: can they take their data with them? Can they take their photos, their videos, their e-mails? And how easy is that? Data are often stored in proprietary file formats, which are protected by patents, and those are controlled by software and service vendors."

"Which raises the question: Do you actually own your own data?" The answer is unfortunately a qualified no! A very interesting research direction, right?

Is Britney Spears Spam?

From my old blog (21st August 2007):
In the last post, I was raving on about ..., uhm, probably about trust bootstrapping, right? :-) I went from a definition of cold reading to a very personal interpretation of Posner's review of Blink. Now, in the same vein (i.e., keeping on being delirious), I move on this nice paper, which carries out (in a way) not offender profiling but MySpace user profiling.
Title: Is Britney Spears Spam? (pdf)

Problem: In social network websites (e.g., MySpace), to decide whether to accept invitations to connect, users manually examine the senders' profiles. However that may be time consuming!

Existing Solutions: One may automate the acceptance of invitations by having users running trust propagation algorithms.

Complication: The authors write that using current trust propagation algorithms may be less than desirable since trust both decays with the number of hops and is usually one-dimensional.

Proposal: Use machine learning techniques to classify user profiles. The classification describes a profile across two dimensions: sociability and promotin. Based on these dimensions' values for a profile, users then decide whether
to accept the invitation of that profile's user. To come up with a dataset on which to evaluate their algorithm, the authors randomly select and rate by hand MySpace users.
Future: I would:
> Apply a new trust propagation algorithm (pdf) to avoid trust decay and apply TRULLO (pdf) to handle multi-dimensional trust.
> Look at literature on criminal profiling. In UCL's main library, I noticed many books about criminal profiling. I wonder whether those books could inform a (future) paper titled "On profiling (not only criminals but) Web 2.0 users" ;-)
> Look at literature on statistical discrimination (previous post) and on customer profiling (mining customer data).
> Consider Tim Finin's comments:"It would be interesting to see how well various measures of the network structure around false and true profies serve as features. I think this is very similar to the problem of recognizing spam blogs (splogs). In our work, we’ve found that local features work well, but splogs can also be recognized by looking at the network structure as well."

The death of mass advertising?

Facebook Tries 'Social Advertising'. ..."a Facebook user who rents a movie on Blockbuster.com will be asked if he would like to have his movie choice broadcast out to all his friends on Facebook. And those friends would have no choice but to receive that movie message, along with an ad from Blockbuster."

MySpace reveals 'targeted' ads - "a pilot scheme that allows it to sell advertisements targeted to the individual tastes and interests of its millions of users...[It] will give advertisers the ability to drill down into 100 different user segments. This will allow them to differentiate between fans of romantic comedy films and action films, for example."