# Structural Network Properties

This section describes the large collection of algorithms included in NOESIS for computing different structural network properties. These metrics provide a glimpse into the network topology and structure.

NOESIS is able to compute a large collection of structural network properties. Implementations for such structural properties are provided within the **noesis.analysis.structure** package.

## Computing structural network properties

Structural network properties are implemented as NOESIS tasks, providing a unified interface for these metrics. Computing a structural network property requires instantiating the corresponding task first.

For example, in order to compute the node Katz centrality we would create an instance of the KatzCentrality class as follows:

`KatzCentrality katzCentralityTask = `**new** KatzCentrality(network);

Once the task has been created, we can use it to compute the structural network property scores. NOESIS tasks can be synchronously or asynchronously computed. The synchronous alternative blocks the current thread until the metric is computed. Synchronously computing a network property can be done using the **call **method as follows:

`NodeScore scores = katzCentralityTask.call();`

This operation returns a NodeScore object, which is a vector of node scores. We can easily get the score associated with a node using the **get **method as shown below:

`double nodeScore = scores.get(nodeIndex);`

The asynchronous computation of the structural network property is slightly more involved, but it allows a better use of concurrent system resources. NOESIS supports asynchronous tasks through *futures*, which provide an interface for representing the result of the asynchronous task. In order to schedule the computation of the structural network property algorithm and retrieve the associated future, we would call the **getFuture **method as follows:

`Future<NodeScore> katzCentralityFuture = katzCentralityTask.getFuture();`

This method call launches the algorithm execution, but it does not block the current thread. In order to retrieve the computed scores, we need to use the **get **method implemented by the Future, as shown below:

`NodeScore scores = katzCentralityFuture.get();`

If this call is carried out when the execution of the algorithm has already finished, it directly returns the scores associated to the nodes. However, if the algorithm is still being executed, this call blocks the current thread until the computation finishes.

In the previous example, we have shown how to compute a node-related structural network property. NOESIS also supports several link-related metrics through the interface provided by the **LinkScoreTask** class. Both interfaces provided by **NodeScoreTask **and **LinkScoreTask** are very similar, but the latter returns a **LinkScore **object instead of a **NodeScore **object.

For example, we would compute link betweenness as follows:

`LinkBetweenness linkBetweennessTask = `**new** LinkBetweenness(network);

`LinkScore linkBetweennessScores = linkBetweennessTask.call();`

Given the computed **LinkScore **object, we can obtain the link betweenness of a link as shown below:

`double score = linkBetweennessScores.get(sourceNodeIndex, targetNodeIndex);`

## Creating a custom structural network property

NOESIS can be extended with custom structural network properties. In this section we describe how to create metrics both for nodes and for links.

### Creating a custom node property

In order to create a node-related structural network property, we must implement a class extending the **NodeScoreTask **class. This requires implementing the **compute **method, which takes the index of a node and returns the score associated to it, as shown in the following example:

**public** **class** MyLocalNodeScore **extends** NodeScoreTask

`{`

` `**public** MyLocalNodeScore(Network network)

` {`

` `**super**(network);

` }`

` @Override`

` `**public** double compute(int node)

` {`

` double nodeScore = ...; // Compute the node score here`

` `**return** nodeScore;

` }`

`}`

However, many metrics require computing all node scores at once. This type of network structure properties can be implemented as shown below:

**public** **class** MyGlobalNodeScore **extends** NodeScoreTask

`{`

` `**public** MyGlobalNodeScore(Network network)

` {`

` `**super**(network);

` }`

` @Override`

` `**public** void compute ()

` {`

` Network network = getNetwork(); `

` NodeScore score = `**new** NodeScore(**this**,network);

` `

` // Implement your algorithm here`

` ...`

` // Set the score for each a node as follows`

` int nodeIndex = ...`

` double value = ...`

` score.set(nodeIndex, value);`

` `

` setResult(score);`

` }`

` `

` @Override`

` `**public** double compute(int node)

` {`

` checkDone(); `

` `**return** getResult(node);

` }`

`}`

### Creating a custom link property

The implementation of a custom link metric is similar. You must extend the **LinkScoreTask **class, which requires implementing the compute method. This time, the compute method takes the index of the source and the target nodes of the link as parameters. The batch computation of all link scores can be carried out in a similar fashion to the previous example, as shown below:

**public** **class** MyGlobalLinkScore **extends** LinkScoreTask

`{`

` `**public** MyGlobalLinkScore(Network network)

` {`

` `**super**(network);

` }`

` @Override`

` `**public** void compute ()

` {`

` Network network = getNetwork(); `

` LinkScore score = `**new** LinkScore(**this**,network);

` `

` // Implement your algorithm here`

` ...`

` `

` // You can set the score of a link as follows`

` int sourceNodeIndex = ...`

` int targetNodeIndex = ...`

` double value = ...`

` score.set(sourceNodeIndex, targetNodeIndex, value);`

` `

` setResult(score);`

` }`

` @Override`

` `**public** double compute(int source, int destination)

` {`

` checkDone(); `

` `**return** getResult().get(source, destination);

` }`

`}`

## Degree-related properties

Node degree is a central concept in network analysis. This subsection covers different structural network properties related to node degree, including different types of degrees and metrics for degree assortativity.

### Degree

The degree of a node is defined as number of links the node has. NOESIS provides three different metrics for node degree: **InDegree**, **OutDegree**, and **Degree**, which measure node degree considering incoming links, outgoing links, and both types of links, respectively. A normalized version of these metrics, which computes the fraction of nodes in the network a node is connected to, is also provided with **NormalizedInDegree**, **NormalizedOutDegree**, and **NormalizedDegree**.

An example of how to compute the out-degree of a given node is shown below:

`Network network = ...`

`OutDegree outDegreeTask = `**new** OutDegree(network);

`int nodeIndex = ...`

`int nodeOutDegree = (int) outDegreeTask.compute(nodeIndex);`

### Degree assortativity

Assortativity is the tendency of nodes to connect with other similar ones. This similarity is usually defined in terms of node degree: nodes with a high degree tend to form links with other high-degree nodes, whereas low-degree nodes do the same between themselves. This metric, implemented in the **DegreeAssortativity **class, is based on the idea of measuring the Pearson correlation between the degree of linked nodes in the network.

The following example shows how to compute the overall network degree assortativity:

`Network network = ...`

`DegreeAssortativity degreeAssortativityTask = `**new** DegreeAssortativity(network);

`double assortativity = degreeAssortativityTask.networkAssortativity();`

Since this task is defined as a node metric, we can obtain the contribution of each node, which is known as local assortativity, to the overall assortativity. This local assortativity can be computed as shown below:

`NodeScore nodeAssortativityContrib = degreeAssortativityTask.call();`

By definition, this metric tends to favor higher local assortativity scores for low-degree nodes compared to high-degree nodes. NOESIS implements a variant, proposed in the scientific literature, which overcomes this limitation. This technique is implemented by the **UnbiasedDegreeAssortativity **class, which has the same interface than the **DegreeAssortativity **class.

**References:**

- Piraveenan, M., Prokopenko, M., & Zomaya, A. Y. (2008). Local assortativeness in scale-free networks. Europhysics Letters, 84(2), 28002. DOI: 10.1209/0295-5075/84/28002.
- Piraveenan, M., Prokopenko, M., & Zomaya, A. Y. (2010). Classifying complex networks using unbiased local assortativity. In ALIFE (pp. 329-336).

## Reachability properties

Node reachability measures how well a node can be reached from the other nodes in the network. These techniques revolve around the concept of path length between pairs of nodes. NOESIS implements different approaches for measuring node reachability, which are introduced in this section.

### Eccentricity

The eccentricity of a node is defined as the length of the longest shortest path to any other node in the network. Note that the highest eccentricity score in the network is equal to the network diameter.

This metric can be computed using the **Eccentricity **class as shown below:

`Network network = ...`

`Eccentricity eccentricityTask = `**new** Eccentricity(network);

`NodeScore eccentricity = eccentricityTask.call();`

**References:**

- Hage, P. and Harary, F. (1995). Eccentricity and centrality in networks. Social Networks, 17(1):57–63. DOI: 10.1016/0378-8733(94)00248-9.

### Average path length

This metric defines node reachability as the average length of the shortest path to all the other nodes in the network.

An example of how to use this metric, implemented by the **AveragePathLength **class, is shown in the following code snippet:

`Network network = ...`

`AveragePathLength aplTask = `**new** AveragePathLength(network);

`NodeScore apl = aplTask.call();`

### Closeness

The closeness of a node is defined as the inverse of the average path length to other nodes.

The **Closeness **class, which implements this metric, can be used as shown below:

`Network network = ...`

`Closeness closenessTask = `**new** Closeness(network);

`NodeScore closeness = closenessTask.call();`

**References:**

- Freeman, L. C. (1978). Centrality in social networks conceptual clarification. Social networks, 1(3), 215-239. DOI: 10.1016/0378-8733(78)90021-7.

### Decay

This metric, implement by the **Decay **class, defines node reachability as the sum of the exponential decay of the path length to other nodes in the network. This algorithms takes a decay parameter, with a value between 0 and 1, indicating the decay degree of the path length between pairs of nodes. On the one hand, if decay is set to 0, all paths would count equally regardless of their length. On the other hand, if decay is set to 1, there would be no decay at all, contributing each path according to its specific length.

An example of how to compute this structural network property, using a decay value of 0.4, is shown below:

`Network network = ...`

`Decay decayTask = `**new** Decay(network, 0.4);

`NodeScore decay = decayTask.call();`

**References:**

- Jackson, M. O. (2008). Social and economic networks. Princeton University Press, Princeton, NJ, USA.

## Betweenness

Node betweenness has been widely studied in the field of network theory. This structural network property measures node centrality according to the amount of shortest paths between pairs of nodes that contain a given node.

In NOESIS, the classical Freeman's betweenness is implemented by the **Betweenness **class. An example how to use this class in shown in the following code snippet:

`Network network = ...`

`Betweenness betweennessTask = `**new** Betweenness(network);

`NodeScore betweenness = betweennessTask.call();`

Since betweenness depends on the number of nodes in the network, this metric could be biased if there are different strongly-connected component in the network. An alternative definition of betweenness, which adjusts Betweenness centrality to component sizes, is provided by **AdjustedBetweenness**.

NOESIS also provides a normalized implementation of **AdjustedBetweenness**, yielding values between 0 and 1, through the **NormalizedBetweenness** class.

**References:**

- Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 35-41. DOI: 10.2307/3033543.

## Influence metrics

Several algorithms have been proposed in the scientific literature to measure the influence of a node within a network. In this section, different algorithms implemented in NOESIS for measuring node influence are introduced, including examples of how to use them.

### PageRank

PageRank is a popular algorithm for measuring the importance of each node in a network. This algorithm iteratively estimates the probability distribution of reaching each node through random walks starting from the other nodes in the network. PageRank also introduces a damping factor, with a value between 0 and 1, indicating the probability of moving to an adjacent node in the random walk versus jumping to a random node in the network.

The following example shows how to compute PageRank using a damping factor of 0.9 for a given network:

`Network network = ...`

`PageRank pageRankTask = `**new** PageRank(network,0.9);

`NodeScore pageRank = pageRankTask.call();`

**References:**

- Page, L., Brin, S., Motwani, R., & Winograd, T. (1998). The PageRank citation ranking: bringing order to the web. Technical report, Stanford InfoLab.

### HITS

The Hyperlink-Induced Topic Search (HITS) algorithm measures node relevance using two concepts: hubs and authorities. On the one hand, hubs are nodes linked to many other nodes. On the other hand, authorities are nodes linked by many hubs. The HITS algorithm iteratively computes a pair of scores for each node: one for the degree of being a hub and other for the degree of being an authority.

An example of how to use this metric is shown below:

`Network network = ...`

`HITS hitsTask = `**new** HITS(network);

**List**<NodeScore> hits = hitsTask.call();

` `

`NodeScore hub = hits.get(0);`

`NodeScore authority = hits.get(1);`

Note that this metric, which is implemented as a **NodeScoreGroupTask**, returns a list of **NodeScore **objects. The first position in this list contains the **NodeScore **object that represents the hub centrality of each node, while the second position contains the **NodeScore **that represents the authority centrality of each node.

**References:**

- Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5), 604-632. DOI: 10.1145/324133.324140.

### Eigenvector centrality

As other influence metrics previously described, eigenvector centrality assigns a higher influence to nodes linked to other high-influence nodes. This structural network property uses the power iteration algorithm on the network adjacency matrix in order to find its greatest eigenvalue and its associated eigenvector. Each element of this eigenvector can be considered as a measure of node influence for the associated node.

An example of how to use this metric is shown in the following code snippet:

`Network network = ...`

`EigenvectorCentrality ecTask = `**new** EigenvectorCentrality(network);

`NodeScore centrality = ecTask.call();`

### Katz centrality

Katz centrality is a generalization of eigenvector centrality, as this technique also uses the power iteration algorithm to find the eigenvector associated to the greatest eigenvalue of the adjacency matrix. However, Katz centrality introduces two parameters in this process. On the one hand, an attenuation factor alpha regulates the influence of each path between pairs of nodes. On the other hand, a beta parameter controlling the initial node centrality.

An example of how to compute Katz centrality with alpha and beta set to 0.1 and 0.5, respectively, is shown in the following code fragment:

`Network network = ...`

`KatzCentrality katzTask = `**new** KatzCentrality(network, 0.1, 0.5);

`NodeScore centrality = katzTask.call();`

**References:**

- Katz, L. (1953). A new status index derived from sociometric analysis. Psychometrika, 39–43. DOI: 10.1007/BF02289026.

### Diffusion centrality

Diffusion centrality measures node influence in terms of the number of paths with length equal to or less than a value indicated by a parameter. This model also requires specifying a passing probability parameter, which determines the degree of influence for paths with different length.

The following example shows how to compute this structural network property with paths of length up to 4 and a passing probability of 0.2:

`Network network = ...`

`DiffusionCentrality diffCentTask = `**new** DiffusionCentrality(network, 0.2, 4);

`NodeScore centrality = diffCentTask.call();`

### LeaderRank

The LeaderRank algorithm is very similar to PageRank, with the difference that, in LeaderRank, all nodes are connected to a virtual ground node through bidirectional links. The classical PageRank algorithm is applied over this augmented network to obtain the influence degree of each node. Its original authors suggest that this simple change allows LeaderRank to converge faster than PageRank.

An example of how to use the LeaderRank algorithm is shown below:

`Network network = ...`

`LeaderRank leaderRankTask = `**new** LeaderRank(network);

`NodeScore influence = leaderRankTask.call();`

**References:**

- Lü, L., Zhang, Y. C., Yeung, C. H., & Zhou, T. (2011). Leaders in social networks, the delicious case. PloS one, 6(6), e21202. DOI: 10.1371/journal.pone.0021202.

## Link properties

This section is devoted to link-related structural network properties. In addition to the techniques described here, more link-related methods can be found in the Link Scoring & Prediction page.

### Link betweenness

Betweenness can be also defined for links as the number of shortest paths between pairs of nodes that contain a given link. This structural network property has very interesting applications. For example, it is used for detecting communities in networks by the Girvan–Newman algorithm, described in the Community Detection section.

The following example shows how to apply this metric to a given network:

`Network network = ...`

`LinkBetweenness lbTask = `**new** LinkBetweenness(network);

`LinkScore linkBetweenness = lbTask.call();`

### Link embeddedness

Link embeddedness is defined as the number of shared neighbors between the nodes at the ends of the link. This metric can be seen as a measure of the strength of the link. NOESIS includes a large number of metrics for scoring links. More details about these metrics can be found under the Link Scoring & Prediction section.

The following code snippet shows an example of how to use this metric:

`Network network = ...`

`LinkEmbeddedness linkEmbTask = `**new** LinkEmbeddedness(network);

`LinkScore linkEmbeddedness = linkEmbTask.call();`

### Link neighborhood overlap

The link neighborhood overlap is closely related to link embeddedness. This metric is defined as the number of shared neighbors between the nodes involved in the link, divided by the number of neighbors both nodes are connected to.

An example of how to compute the link neighborhood overlap of a link between two nodes, with indices 13 and 22, is shown below:

`Network network = ...`

`LinkNeighborhoodOverlap lnoTask = `**new** LinkNeighborhoodOverlap(network);

`double linkNeighborhoodOverlap = lnoTask.compute(13, 22);`

### Link neighborhood size

This link metric counts the total number of neighbors that nodes at the ends of the link have.

The following example shows how to compute this metric for a link between two nodes with indices 15 and 27:

`Network network = ...`

`LinkNeighborhoodSize lnsTask = `**new** LinkNeighborhoodSize(network);

`double linkNeighborhoodSize = lnsTask.compute(15, 27);`

### Link rays

Link rays count the number of different paths that pass through the link between neighbors of the nodes at the ends. This metric is defined as the product of the source node in-degree and the destination node out-degree.

An example of how to use this metric is shown below:

`Network network = ...`

`LinkRays linkRaysTask = `**new** LinkRays(network);

`LinkScore linkRays = linkRaysTask.call();`

` `

`int linkRaysScore = (int) linkRays.get(13, 28);`

## Clustering coefficient

The clustering coefficient measures the tendency of the neighbors of a node to connect between them. For a given node, this structural network property is defined as the number of closed triangles in which the node takes part divided by the number of potential triangles the node could take part. This fraction is a good indicator of the tendency of nodes in a network to cluster together.

The following example show how to use the **ClusteringCoefficient **class for computing node clustering coefficient:

`Network network = ...`

`ClusteringCoefficient ccTask = `**new** ClusteringCoefficient(network);

`NodeScore clusteringCoefficient = ccTask.call();`

Since the average clustering coefficient is also of interest, a shortcut for its calculation is given by the **averageClusteringCoefficient **method, as shown below:

`double avgClusteringCoefficient = ccTask.averageClusteringCoefficient();`

## Robustness coefficient

The robustness coefficient measures the network resilience to attacks or faults. This structural network property is based on measuring how the largest component size changes as the network goes through disintegration by removing its nodes. Nodes are removed according to the order given by a list passed as an argument. The result of this metric is a final score measuring the network robustness. This value can be computed using the **getRobustness **method of the **RobustnessCoefficient **class. This class is defined as a node score, where each node is assigned the size of the largest component after its removal.

The following code fragment shows an example of how to compute the robustness coefficient using a custom order list in ascending order:

`Network network = ...`

**List** order = ...

`boolean descending = `**false**;

`RobustnessCoefficient rcTask = `**new** RobustnessCoefficient(network, order, descending);

`NodeScore nodeRobustness = rcTask.call();`

` `

`double robustnessCoefficient = rcTask.getRobustness();`

The **nodeRobustness **object contains the scores associated to nodes, whereas the **robustnessCoefficient **variable contains the network robustness coefficient.

Other network properties can be used to specify the node removal order. For example, the following code snippet shows how to compute the robustness coefficient by removing nodes according to their degree in descending order:

`Network network = ...`

`NodeScore degree = `**new** Degree(network).call();

`boolean descending = `**true**;

`RobustnessCoefficient rcTask = `**new** RobustnessCoefficient(network, degree, descending);

`double robustnessCoefficient = rcTask.getRobustness();`

**References:**

- Piraveenan, M., Thedchanamoorthy, G., Uddin, S., & Chung, K. S. K. (2013). Quantifying topological robustness of networks under sustained targeted attacks. Social Network Analysis and Mining, 3(4), 939-952. DOI: 10.1007/s13278-013-0118-8.