Finding rellevant links in a network

In the following paper , the authors proposed a new method to compute the most important edges (or links) in a network:

Grady, D., Thiemann, C., & Brockmann, D. (2012). Robust classification of salient links in complex networks. Nature Communications, 3(May), 864:1–864:10. doi:10.1038/ncomms1847

This method automatically finds “salient” links in networks by using the following approach:

  1. Choose a property that defines the weight of an edge in a given network,
  2. Define the distance between two nodes as 1 / the weight,
  3. Using above distance measure, take a node and compute the shortest path to all other nodes in the network,
  4. Combine all edges from the previous step into a set, which is called the Shortest Path Tree (SPT),
  5. For each edge in the SPT, increase a “salience” counter,
  6. Repeat steps 3-5 for every other node in the network,
  7. For each edge, divide its salience counter by the total number of nodes in the network, leading to a salience property with a value in the range [0..1].

You can find an interesting application example in:

Jonatan Samoocha. Finding Important Connections In A Network – Automatically.

This entry was posted in Graph Mining, Information flow, Social network analysis and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s