Search

Hierarchical networks typically get rated to be not assortative on the basis of the degrees of the end vertices of the edges. However, degree centrality is not cognizant of the location of the nodes in the hierarchy. Rather, we propose the use of hierarchy-aware metrics (such as the k-core index of a node: the largest value of k for which the node would be part of a k-core and not part of any k′-core, where k′ > k and the number of k-core levels for which there exists a non-empty k-core for the network) for assortativity calculations. We first determine the assortativity index ( A s s I kcore ) of a network on the basis of the k-core indexes of the vertices. We then conduct principal component analysis (PCA) on a dataset of the A s s I kcore and the number of k-core levels for a suite of 77 real-world networks. We quantify the hierarchical k-core assortativity of a network as the weighted sum of the entries in the two principal components of this dataset. [ABSTRACT FROM AUTHOR]

We propose a quantitative metric (called relative assortativity index, RAI) to assess the extent with which a real-world network would become relatively more assortative due to link addition(s) using a link prediction technique. Our methodology is as follows: for a link prediction technique applied on a particular real-world network, we keep track of the assortativity index values incurred during the sequence of link additions until there is negligible change in the assortativity index values for successive link additions. We count the number of network instances for which the assortativity index after a link addition is greater or lower than the assortativity index prior to the link addition and refer to these counts as relative assortativity count and relative dissortativity count , respectively. RAI is computed as (relative assortativity count − relative dissortativity count) / (relative assortativity count + relative dissortativity count). We analyzed a suite of 80 real-world networks across different domains using 3 representative neighborhood-based link prediction techniques (Preferential attachment, Adamic Adar and Jaccard coefficients [JACs]). We observe the RAI values for the JAC technique to be positive and larger for several real-world networks, while most of the biological networks exhibited positive RAI values for all the three techniques. [ABSTRACT FROM AUTHOR]

We propose a novel network-level metric called Edge Similarity Index (ESI) to quantify the extent of similarity between any two edges of a complex network with respect to the values for a node-level metric (like centrality metric) of its end vertices. To assess the ESI measure for a complex real-world network with respect to a node-level metric, we propose to first construct a logical network whose vertices are the actual edges of the network (with coordinates corresponding to the normalized node-level metric values of the actual end vertices), and there exists a (logical) edge between two logical vertices if the Euclidean distance between their corresponding coordinates is within a threshold distance. We propose a binary search algorithm to determine the minimum value for this threshold distance (distmin thresh) that would result in a connected logical unit-disk graph; the ESI value for the complex network is then computed as 1-min thresh/√2. The ESI values range from 0.0 to 1.0; the larger the ESI value with respect to a node-level metric, we claim that more similar are any two edges in the network with respect to the node-level metric values for their end vertices. [ABSTRACT FROM AUTHOR]

The assortativity index (A. Index) of a complex network has been hitherto computed as the Pearson's correlation coefficient of the remaining degree centrality (R-DEG) of the first-order neighbors (i.e. end vertices of the edges) in the network. In this paper, we seek to evaluate the assortativity of real-world networks with respect to prototypical centrality metrics (in addition to R-DEG) such as eigenvector centrality (EVC), betweenness centrality (BWC) and closeness centrality (CLC). Unlike R-DEG, the centrality values of the vertices with respect to these three metrics are influenced by the centrality values of the vertices in the neighborhood. We propose to use the notion of 'Partial Correlation Coefficient' to nullify the influence of the second-order neighbors (i.e. vertices that are two hops away) and quantify the assortativity of the first-order neighbors with respect to a particular centrality metric (such as EVC, BWC and CLC). We conduct an exhaustive assortativity analysis on a suite of 70 real-world networks of diverse degree distributions. We observe real-world networks to be more assortative (A. Index > 0) with respect to CLC and EVC and relatively more dissortative (A. Index < 0) with respect to BWC and R-DEG. [ABSTRACT FROM AUTHOR]

We seek to quantify the extent of similarity among nodes in a complex network with respect to two or more node-level metrics (like centrality metrics). In this pursuit, we propose the following unit disk graph-based approach: we first normalize the values for the node-level metrics (using the sum of the squares approach) and construct a unit disk graph of the network in a coordinate system based on the normalized values of the node-level metrics. There exists an edge between two vertices in the unit disk graph if the Euclidean distance between the two vertices in the normalized coordinate system is within a threshold value (ranging from 0 tok, where k is the number of node-level metrics considered). We run a binary search algorithm to determine the minimum value for the threshold distance that would yield a connected unit disk graph of the vertices. We refer to "1 − (minimum threshold distance/k)" as the node similarity index (NSI; ranging from 0 to 1) for the complex network with respect to the k node-level metrics considered. We evaluate the NSI values for a suite of 60 real-world networks with respect to both neighborhood-based centrality metrics (degree centrality and eigenvector centrality) and shortest path-based centrality metrics (betweenness centrality and closeness centrality). [ABSTRACT FROM AUTHOR]

The predicted link expiration time (LET)-based approach is currently the only promising approach to determine stable data gathering (DG) trees for mobile sensor networks, and the use of this approach requires the sensor nodes to be location and mobility aware (which is energydraining on the nodes). The objective of this paper is to investigate the use of location and mobility-independent graph theoretic metrics (such as Neighborhood Overlap: NOVER, Bipartivity Index: BPI and Algebraic Connectivity: ALGC) that could be locally computed by each sensor node on the egocentric network of an edge to quantify the stability of the links. The egocentric network of an edge comprises of the end nodes of the edge and their neighbors (as vertices) and links incident on the end nodes of the edge (as edges). We hypothesize that an edge whose egocentric network has a larger NOVER or a smaller BPI or a larger ALGC score should have its end nodes share a significant fraction of their neighbors and be a short distance link that is relatively more stable. Simulation results indicate that the DG trees determined based on the graph theoretic metrics are significantly more stable and energy-efficient compared to that of the LET-based DG trees. [ABSTRACT FROM AUTHOR]

The high-level contribution of this paper is a quantitative measure (called Randomness Index) to assess the extent of randomness in the topology of a complex real-world network. We exploit the observation that the local clustering coefficient (LCC) for a node in a truly random network is independent of the degree of the node and is simply the probability for a link to exist between any two nodes in the network. On the other hand, for real-world networks that are not truly random, nodes with a larger degree are more likely to have a lower LCC value and vice versa. For any complex real-world network, we propose to determine the Randomness Index as the Pearson's correlation coefficient (ranging from −1 to 1) of the degree versus average LCC of the nodes with the particular degree. We evaluate the Randomness Index values for a suite of 48 real-world networks of diverse degree distribution and observe the median value to be −0.72. [ABSTRACT FROM AUTHOR]

We identify three different levels of correlation (pairwise relative ordering, network-wide ranking and prediction through linearity) that could be assessed between a computationally-light centrality metric and a computationally-heavy centrality metric for real-world networks. The Kendall's concordance-based correlation measure could be used to quantitatively assess how well we could consider the relative ordering of two vertices vi and vj with respect to a computationally-light centrality metric as the relative ordering of the same two vertices with respect to a computationally-heavy centrality metric. We hypothesize that the pair-wise relative ordering (concordance)-based assessment of the correlation between centrality metrics is the strictest of all three levels of correlation and claim that the Kendall's concordance-based correlation coefficient will be lower than the correlation coefficient observed with the more relaxed levels of correlation measures (prediction through linearity-based Pearson's product-moment correlation coefficient and the network wide ranking-based Spearman's correlation coefficient). We validate our hypothesis by evaluating the three correlation coefficients between two sets of centrality metrics: the computationally-light degree and local clustering coefficient complement-based degree centrality metrics and the computationally-heavy eigenvector centrality, betweenness centrality and closeness centrality metrics for a diverse collection of 50 real-world networks. [ABSTRACT FROM AUTHOR]

The betweenness centrality (BWC) of a vertex is a measure of the fraction of shortest paths between any two vertices going through the vertex and is one of the widely used shortest path-based centrality metrics for the complex network analysis. However, it takes O( $$\vert V\vert ^{2}+\vert V\vert \vert E\vert )$$ time (where V and E are, respectively, the sets of nodes and edges of a network graph) to compute the BWC of just a single node. Our hypothesis is that nodes with a high degree, but low local clustering coefficient, are more likely to be on the shortest paths of several node pairs and are likely to incur a larger BWC value. Accordingly, we define the local clustering coefficient-based degree centrality (LCCDC) for a node as the product of the degree centrality of the node and one minus the local clustering coefficient of the node. The LCCDC of a node can be computed based on just the knowledge of the two-hop neighborhood of a node and would take significantly lower time. We conduct an exhaustive correlation analysis and observe the LCCDC to incur the largest correlation coefficient values with BWC (compared to other centrality metrics under three different correlation measures) and to hold very strong levels of positive correlation with BWC for at least 14 of the 18 real-world networks analyzed. Hence, we claim the LCCDC to be an apt metric to rank the nodes or compare any two nodes of a real-world network graph in lieu of BWC. [ABSTRACT FROM AUTHOR]

We define the problem of maximal assortativity matching (MAM) as a variant of the maximal matching problem wherein we want to maximize the similarity between the end vertices (with respect to any particular measure for node weight) constituting the matching. The MAM algorithm (with a targeted assortative index value of 1) works on the basis of the assortative weight of an edge, defined as the product of the number of uncovered adjacent edges and the absolute difference of the weights of the end vertices of the edge. The MAM algorithm prefers to include the edge with the smallest assortativity weight (the assortative weight of the edges is updated for each iteration) until all the edges in the graph are covered. We show that the MAM algorithm can be easily adapted to be used for maximal dissortative matching (MDM) with a targeted assortative index of $$-$$ 1 for the matching as well as for maximal node matching (MNM) algorithm to maximize the percentage of nodes matched. We illustrate the execution of the MAM, MDM and MNM algorithms on complex network graphs such as the random network graphs and scale-free network graphs as well as on real-world network graphs and analyze the tradeoffs. [ABSTRACT FROM AUTHOR]

Matching of vertices in social networks and other complex networks needs to take into consideration the weight of the vertices (like degree) that are matched; arbitrary matching of the vertices with simply the objective of maximizing the number of vertices need not be of any practical benefit. Assortativity of the edges in a network is a measure of the similarity of the end vertices of the edges with respect to any measure of node weight and is quantified in terms of the assortative index. In this paper, we propose to apply the notion of assortativity for one-to-one matching of the vertices such that the assortativity of the matching is maximized or minimized as much as possible, depending on the case. We design algorithms for maximal assortative matching (MAM, to maximize the assortativity index (AI)) and maximal dissortative matching (MDM, to minimize the assortative index) for complex network graphs and compare their performance with that of a maximal node matching (MNM) algorithm that aims to simply maximize the percentage of nodes matched. We execute the MAM, MDM and MNM algorithms on real-world network graphs as well as on theoretically generated complex network graphs and analyze the performance tradeoffs with respect to the percentage of node matches and AI. [ABSTRACT FROM AUTHOR]

The neighborhood overlap (NOVER) of an edge u-v is defined as the ratio of the number of nodes who are neighbors for both u and v to that of the number of nodes who are neighbors of at least u or v. In this paper, we hypothesize that an edge u-v with a lower NOVER score bridges two or more sets of vertices, with very few edges (other than u-v) connecting vertices from one set to another set. Accordingly, we propose a greedy algorithm of iteratively removing the edges of a network in the increasing order of their neighborhood overlap and calculating the modularity score of the resulting network component(s) after the removal of each edge. The network component(s) that have the largest cumulative modularity score are identified as the different communities of the network. We evaluate the performance of the proposed NOVER-based community detection algorithm on nine real-world network graphs and compare the performance against the multi-level aggregation-based Louvain algorithm, as well as the original and time-efficient versions of the edge betweenness-based Girvan-Newman (GN) community detection algorithm. [ABSTRACT FROM AUTHOR]

Aggregation delay is the minimum number of time slots required to aggregate data along the edges of a data gathering tree (DG tree) spanning all the nodes in a wireless sensor network (WSN). We propose a benchmarking algorithm to determine the minimum possible aggregation delay for DG trees in a WSN. We assume the availability of a sufficient number of unique CDMA (Code Division Multiple Access) codes for the intermediate nodes to simultaneously aggregate data from their child nodes if the latter are ready with the data. An intermediate node has to still schedule non-overlapping time slots to sequentially aggregate data from its own child nodes (one time slot per child node). We show that the minimum aggregation delay for a DG tree depends on the underlying design choices (bottleneck node-weight based or bottleneck link-weight based) behind its construction. We observe the bottleneck node-weight based DG trees incur a smaller diameter and a larger number of child nodes per intermediate node; whereas, the bottleneck link-weight based DG trees incur a larger diameter and a much lower number of child nodes per intermediate node. As a result, we observe a complex diameter-aggregation delay tradeoff for data gathering trees in WSNs. [ABSTRACT FROM AUTHOR]

The topology of mobile ad hoc networks (MANETs) change dynamically with time. Connected dominating sets (CDS) are considered to be an effective topology for network-wide broadcasts in MANETs as only the nodes that are part of the CDS need to broadcast the message and the rest of the nodes merely receive the message. However, with node mobility, a CDS does not exist for the entire duration of the network session and has to be regularly refreshed (CDS transition). In an earlier work, we had proposed a benchmarking algorithm to determine a sequence of CDSs (Maximum Stable CDS) such that the number of transitions is the global minimum. In this research, we study the performance (CDS Lifetime and CDS Node Size) of the Maximum Stable CDS when a certain fraction of the nodes in the network are static and compare the performance with that of the degree-based CDSs. We observe the lifetime of the Maximum Stable CDS to only moderately increase (by a factor of 2.3) as we increase the percentage of the static nodes in the network; on the other hand, the lifetime of the degree-based CDS increases significantly (as large as 13 times) as we increase the percentage of static nodes from 0 to 80. [ABSTRACT FROM AUTHOR]

We propose a secure data aggregation (SDA) framework for mobile sensor networks whose topology changes dynamically with time. The SDA framework (designed to be resilient to both insider and outsider attacks) comprises of a pair-wise key establishment mechanism run along the edges of a data gathering tree and a distributed trust evaluation model that is tightly integrated with the data aggregation process itself. If an aggregator node already shares a secret key with its child node, the two nodes locally coordinate to refresh and establish a new pair-wise secret key; otherwise, the aggregator node requests the sink to send a seed-secret key message that is used as the basis to establish a new pair-wise secret key. The trust evaluation model uses the two-sided Grubbs' test to identify outlier data in the periodic beacons collected from the child nodes/neighbor nodes. Once the estimated trust score for a neighbor node falls below a threshold, the sensor node "locally" classifies its neighbor node as a "Compromised or Faulty" (CF) node, and discards the data or aggregated data received from the CF node. This way, the erroneous data generated by the CF nodes could be filtered at various levels of the data gathering tree and are prevented from reaching the root node (sink node). Finally, we assess the effectiveness of our trust evaluation model through a comprehensive simulation study. [ABSTRACT FROM AUTHOR]