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 degree-related properties or influence-related 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 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 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 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) { // 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. ## Degree-relatedNode 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 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 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 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.## 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(); ## 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(); ## 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(); ## 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 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.## 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(); ## HITSThe 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.## Eigenvector centralityAs 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 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(); ## 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(); ## LeaderRank## LinksThis 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## Link embeddedness## Link neighborhood overlap## Link neighborhood size## Link rays## OthersThis section comprehends different structural network properties that do not fit in other categories. ## Clustering coefficient## Robustness coefficient |

Wiki >