bcds.phison.gm
Class Spreaders<V,E>

java.lang.Object
  bcds.phison.gm.GraphMetricBase<V,E>
      bcds.phison.gm.Spreaders<V,E>

All Implemented Interfaces:

GraphMetric<V,E>, WithEnvParams

public class Spreaders<V,E>
extends GraphMetricBase<V,E>
implements GraphMetric<V,E>

Performs a k-shell decomposition of the nodes of a topology as a GraphMetric.

"The most efficient spreaders are those located within the core of the network as identified by the k-shell decomposition analysis". Reference Maksim Kitsak, Lazaros K. Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H. Eugene Stanley, and Hernan A. Makse. Identification of influential spreaders in complex networks. Nat Phys, 6(11):888–893, November 2010.

The definition of the k-shell decomposition implemented can be found in: Miorandi, Daniele; De Pellegrini, Francesco; , "K-shell decomposition for dynamic complex networks," Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2010 Proceedings of the 8th International Symposium on , vol., no., pp.488-496, May 31 2010-June 4 2010.

An example can be found in: J. Ignacio Alvarez-Hamelin; "How the k-core decomposition helps in understanding the Internet Topology", a slides presentation available here

Additionally, it provides a method to carry out the k-shell decomposition without being accessible to the GraphMetric interface.

Author:

mmanzano

Constructor Summary

Spreaders()
Default constructor.

Spreaders(SimGraph<V,E> g, Environ env)
Creates a new instance and calls setup to complete the initialization.

Method Summary

java.lang.String	getDescription() Returns a string describing the metric, for example, article where it has been published, URL where to find reference implementation, etc.
java.lang.String	getLabel() Returns the string "Spreaders".
java.util.Map<V,java.lang.Double>	getNodeMetric() Returns the k-shell index of each node of a topology.
java.util.Map<java.lang.Integer,java.util.Set<V>>	getSpreaders() Returns the set of nodes associated with each k-shell index.
boolean	isApplicableTo(MetricTarget m) Returns true if m is MetricTarget.NODE.
void	kShellDecomposition(int k) Recursive k-shell decomposition algorithm.
boolean	nodesWithDegree(SimGraph<V,E> sg, int k) Returns true if there is a node with degree k .
SimGraph<V,E>	removeNodesOfDegree(SimGraph<V,E> sg, int k) Removes all the nodes with degree k from the graph 'sg' and returns the consequently subgraph.
void	run() Performs the k-shell decomposition.

Methods inherited from class bcds.phison.gm.GraphMetricBase

dump, getEdgeMetric, getEnviron, getEnvParams, getGraph, getGraphMetric, getGraphMetricStdev, getName, setup

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface bcds.phison.gm.GraphMetric

dump, getEdgeMetric, getGraphMetric, getGraphMetricStdev, setup

Methods inherited from interface bcds.phison.WithEnvParams

getEnviron, getEnvParams, getName

Constructor Detail

Spreaders

public Spreaders()

Default constructor.

Spreaders

public Spreaders(SimGraph<V,E> g,
                 Environ env)

Creates a new instance and calls setup to complete the initialization.

Method Detail

isApplicableTo

public boolean isApplicableTo(MetricTarget m)

Returns true if m is MetricTarget.NODE.

Specified by:

isApplicableTo in interface GraphMetric<V,E>

Overrides:

isApplicableTo in class GraphMetricBase<V,E>

removeNodesOfDegree

public SimGraph<V,E> removeNodesOfDegree(SimGraph<V,E> sg,
                                         int k)

Removes all the nodes with degree k from the graph 'sg' and returns the consequently subgraph. Moreover, it adds the relationship between the nodes and their k-shell index.

nodesWithDegree

public boolean nodesWithDegree(SimGraph<V,E> sg,
                               int k)

Returns true if there is a node with degree k .

kShellDecomposition

public void kShellDecomposition(int k)

Recursive k-shell decomposition algorithm.

run

public void run()

Performs the k-shell decomposition.

Specified by:

run in interface GraphMetric<V,E>

Overrides:

run in class GraphMetricBase<V,E>

getNodeMetric

public java.util.Map<V,java.lang.Double> getNodeMetric()

Returns the k-shell index of each node of a topology. If this was not the metric computed in run, it is computed here before returning.

Specified by:

getNodeMetric in interface GraphMetric<V,E>

Overrides:

getNodeMetric in class GraphMetricBase<V,E>

getLabel

public java.lang.String getLabel()

Returns the string "Spreaders".

Specified by:

getLabel in interface GraphMetric<V,E>

getDescription

public java.lang.String getDescription()

Description copied from interface: GraphMetric

Returns a string describing the metric, for example, article where it has been published, URL where to find reference implementation, etc.

Specified by:

getDescription in interface GraphMetric<V,E>

getSpreaders

public java.util.Map<java.lang.Integer,java.util.Set<V>> getSpreaders()

Returns the set of nodes associated with each k-shell index. This method can not be accessed using the GraphMetric interface.