Methods to Determine Node Centrality and Clustering in Graphs with Uncertain Structure

Details Methods to Determine Node Centrality and Clustering in Graphs with Uncertain Structure Methods to Determine Node Centrality and Clustering in Graphs with Uncertain Structure

2011-04-02

arxiv.org/abs/1104.0319v1

Computer Science

Social and Information Networks

Longer version of paper appearing in Fifth International AAAI Conference on Weblogs and Social Media. 9 pages, 4 Figures

Scientific paper

Much of the past work in network analysis has focused on analyzing discrete graphs, where binary edges represent the "presence" or "absence" of a relationship. Since traditional network measures (e.g., betweenness centrality) utilize a discrete link structure, complex systems must be transformed to this representation in order to investigate network properties. However, in many domains there may be uncertainty about the relationship structure and any uncertainty information would be lost in translation to a discrete representation. Uncertainty may arise in domains where there is moderating link information that cannot be easily observed, i.e., links become inactive over time but may not be dropped or observed links may not always corresponds to a valid relationship. In order to represent and reason with these types of uncertainty, we move beyond the discrete graph framework and develop social network measures based on a probabilistic graph representation. More specifically, we develop measures of path length, betweenness centrality, and clustering coefficient---one set based on sampling and one based on probabilistic paths. We evaluate our methods on three real-world networks from Enron, Facebook, and DBLP, showing that our proposed methods more accurately capture salient effects without being susceptible to local noise, and that the resulting analysis produces a better understanding of the graph structure and the uncertainty resulting from its change over time.

Affiliated with

Also associated with

No associations

Rating

Methods to Determine Node Centrality and Clustering in Graphs with Uncertain Structure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Methods to Determine Node Centrality and Clustering in Graphs with Uncertain Structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods to Determine Node Centrality and Clustering in Graphs with Uncertain Structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-335060