This section describes the large collection of algorithms included in NOESIS for computing different structural network properties. These metrics allow a better understanding of the network topology and structure. These algorithms are organized into different categories, including degreerelated properties or influencerelated metrics, among others. Computing structural network propertiesStructural 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 noderelated structural network property. NOESIS also supports several linkrelated 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 the 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 propertyNOESIS can be extended with custom structural network properties. In this section we describe how to create metrics both for nodes and for links. In order to create a noderelated 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) { // Compute the node score here double nodeScore = ...; return nodeScore; } } However, many metrics require batch 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 ... // You can set the score of a node as follows int nodeIndex = ... double value = ... score.set(nodeIndex, value); setResult(score); } @Override public double compute(int node) { checkDone(); return getResult(node); } } The implementation of a custom link metric is a very similar procedure. 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); } } Supported structural network propertiesThis section is devoted to describing the different structural network properties currently supported by the NOESIS framework. The different implemented techniques, which are located in the noesis.analysis.structure package, are categorized and described below. In addition, examples of how to use these metrics are provided. DegreerelatedNode 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. DegreeThe 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 outdegree of a given node is shown below: Network network = ... OutDegree outDegreeTask = new OutDegree(network); int nodeIndex = ... int nodeOutDegree = (int) outDegreeTask.compute(nodeIndex); Degree assortativityAssortativity 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 highdegree nodes, whereas lowdegree 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 lowdegree nodes compared to highdegree 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:
ReachabilityNode 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. EccentricityThe 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:
Average path lengthThis 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(); ClosenessThe 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:
DecayThis 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:
BetweennessNode 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 stronglyconnected 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:
InfluenceSeveral 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. PageRankPageRank 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:
HITSThe HyperlinkInduced 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:
Eigenvector centralityAs other influence metrics previously described, eigenvector centrality assigns a higher influence to nodes linked to other highinfluence 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 centralityKatz 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:
Diffusion centralityDiffusion 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(); LeaderRankThe LeaderRank algorithm is very similar to PageRank, but 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:
LinksThis section is devoted to linkrelated structural network properties. In addition to the techniques described here, more linkrelated methods can be found in the Link Scoring & Prediction page. Link betweennessBetweenness 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 embeddednessLink 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 overlapThe 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 sizeThis 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 raysLink 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 indegree and the destination node outdegree. 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); OthersThis section comprehends different structural network properties that do not fit in other categories. Clustering coefficientThe 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 coefficientThe 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. The result of other metrics can be used to specify the node removal order. For example, the following code 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:

Wiki >