Search

Abstract We propose a novel local clustering coefficient (LCC)-based strategy to extract the peripheral layers of a complex network and identify the nodes that be part of one of these layers as well as those that would form the core of the network. The LCC of a node is the probability that any two neighbors of the node are connected. Our hypothesis is that for any given network topology, nodes with a LCC of 1.0 ideally suit to the role of peripheral nodes. We propose an iterative peeling strategy wherein we remove the nodes with a LCC of 1.0 (the LCC values of the residual nodes are recalculated after each iteration) to extract the peripheral nodes at a particular layer (starting from the outermost peripheral layer to the innermost peripheral layer) and penetrate towards the inner core. We stop the iterative peeling when all the residual nodes (left over nodes in the network after the removal of the nodes at the peripheral layers) have a degree of 0 or the LCC values of all the non-zero degree residual nodes are less than 1.0. We show that the proposed LCC-based iterative peeling strategy has the potential to envision an inner most single-layer core and a hierarchical (one or more peripheral layers) peripheral structure for scale-free networks and a single layer of peer nodes (all nodes have a LCC of less than 1.0) for random networks.

We seek to identify one or more computationally light-weight centrality metrics that have a high correlation with that of the maximal clique size (the maximum size of the clique a node is part of) - a computationally hard measure. In this pursuit, we compute three well-known measures of evaluating the correlation between two datasets: Product-moment based Pearson's correlation coefficient, Rank-based Spearman's correlation coefficient and Concordance-based Kendall's correlation coefficient. We compute the above three correlation coefficient values between the maximal clique size and each of the four prominent node centrality metrics (degree, eigenvector, betweenness and closeness) for random network graphsand scale-free network graphs as well as for a suite of ten real-world network graphs whose degree distribution ranges from random to scale-free. We also explore the impact of the operating parameters of the theoretical models for generating random networks and scale-free networks on the correlation between maximal clique size and the centrality metrics.

The Erdos-Renyi (ER) random network model generates graphs under the assumption that there could exist a link u-v between two nodes u and v irrespective of whether or not the two nodes had a common neighbor before the establishment of the link. As a result, random network graphs generated under the ER model are characteristic of having a low clustering coefficient (a measure of the probability for a link to exist between any two neighbors of a node) and low variation in the node degrees, and hence could not match closely to graphs abstracting real-world networks. In this paper, we propose a random network graph model that gives preference to closing the triangle involving three nodes u, w and v with existing links u-w and w-v (i.e., node v is strictly a two-hop neighbor of node u). Accordingly, when node u is looking for a new link to be setup with some other node x, we consider x along with the two-hop neighbors of u and choose one among these nodes with a probability plink as the new neighbor of node u. The proposed Two-Hop Neighbor Preference (THNP)-based model generates random graphs whose clustering coefficient decreases with increase in node degree: matching closely to several real-world network graphs that are commonly studied for complex network analysis.

Abstract We define a bridge node to be a node whose neighbor nodes are sparsely connected to each other and are likely to be part of different components if the node is removed from the network. We propose a computationally light neighborhood-based bridge node centrality (NBNC) tuple that could be used to identify the bridge nodes of a network as well as rank the nodes in a network on the basis of their topological position to function as bridge nodes. The NBNC tuple for a node is asynchronously computed on the basis of the neighborhood graph of the node that comprises of the neighbors of the node as vertices and the links connecting the neighbors as edges. The NBNC tuple for a node has three entries: the number of components in the neighborhood graph of the node, the algebraic connectivity ratio of the neighborhood graph of the node and the number of neighbors of the node. We analyze a suite of 60 complex real-world networks and evaluate the computational lightness, effectiveness, efficiency/accuracy and uniqueness of the NBNC tuple vis-a-vis the existing bridgeness related centrality metrics and the Louvain community detection algorithm.

Abstract We first propose a binary search algorithm to determine the minimum fraction of nodes in a network to be used as initial adopters ( $$f_{IA}^{\min }$$ f IA min ) for a particular threshold fraction (q) of adopted neighbors (related to the cascade capacity of the network) leading to a complete information cascade. We observe the q versus $$f_{IA}^{\min }$$ f IA min distribution for several complex real-world networks to exhibit a step function pattern wherein there is an abrupt increase in $$f_{IA}^{\min }$$ f IA min beyond a certain value of q (q step ); the $$f_{IA}^{\min }$$ f IA min values at q step and the next measurable value of q are represented as $$\underline{{f_{IA}^{\min } }}$$ f IA min ̲ and $$\overline{{f_{IA}^{\min } }}$$ f IA min ¯ respectively. The difference $$\overline{{f_{IA}^{\min } }} - \underline{{f_{IA}^{\min } }}$$ f IA min ¯ - f IA min ̲ is observed to be significantly high (a median of 0.44 for a suite of 40 real-world networks studied in this paper) such that we claim the 1 − q step value (we propose to refer 1 − q step as the Cascade Blocking Index, CBI) for a network could be perceived as a measure of the intra-cluster density of the blocking cluster of the network that cannot be penetrated without including an appreciable number of nodes from the cluster to the set of initial adopters (justifying a relatively larger $$\overline{{f_{IA}^{\min } }}$$ f IA min ¯ value).

We analyze a suite of 48 real-world networks and compute the decay centrality (DEC) of the vertices for the complete range of values for the decay parameter δ ∊ (0, 1) as well as determine the Pearson's correlation coefficient (PCC) between the DECδ values and degree centrality (DEG) and closeness centrality (CLC). We observe PCC(DECδ, DEG) to decrease with increase in δ and PCC(DECδ, CLC) to decrease with decrease in δ. We define the δ-spacer for a real-world network with respect to the DEG, DEC, CLC correlation as the difference between the maximum and minimum δ values under which we observe a particular level of correlation (r) between the DEC, DEG and DEC, CLC metrics respectively. We show that the PCC(DEG, CLC) values for the real-world networks exhibit a very strongly positive correlation with the δ-spacer values and demonstrate that one could predict the δ-spacer value for a real-world network using the PCC(DEG, CLC) value for that network. We also analyze the impact of various topological measures on the δ-spacer values for the real-world networks. Keywords: Decay centrality, Decay parameter, Closeness centrality, Degree centrality, Correlation, Real-world network graphs

We identify three different levels of correlation (pair-wise relative ordering, network-wide ranking and linear regression) 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 most strictest of all the 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 (linear regression-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.

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).

We define the problem of maximal assortativity matching (MAM) for a complex network graph as the problem of maximizing the similarity of the end vertices (with respect to some measure of node weight) constituting the matching. In this pursuit, we introduce a metric called the assortativity weight of an edge, defined as the product of the number of uncovered adjacent edges and the absolute value of the difference in the weights of the end vertices. The MAM algorithm prefers to include edges that have the smallest assortativity weight in each iteration (one edge per iteration) until all edges are covered. The MAM algorithm can also be adapted to determine a maximal dissortative matching (MDM) to maximize the dissimilarity between the end vertices that are part of a matching as well as to determine a maximal node matching (MNM) that simply maximizes the number of vertices that are part of the matching. We run the MAM, MNM and MDM algorithms on real-world network graphs as well as on the theoretical model-based random network graphs and scale-free network graphs and analyze the tradeoffs between the % of node matches and assortativity index (targeted optimal values: 1 for MAM and −1 for MDM).

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.

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.

The need for automated identification of a disease makes the issue of medical biometrics very current in our society. Not all biometric tools available provide real-time feedback. We introduce gas discharge visualization (GDV) technique as one of the biometric tools that have the potential to identify deviations from the normal functional state at early stages and in real time. GDV is a nonintrusive technique to capture the physiological and psychoemotional status of a person and the functional status of different organs and organ systems through the electrophotonic emissions of fingertips placed on the surface of an impulse analyzer. This paper first introduces biometrics and its different types and then specifically focuses on medical biometrics and the potential applications of GDV in medical biometrics. We also present our previous experience with GDV in the research regarding autism and the potential use of GDV in combination with computer science for the potential development of biological pattern/biomarker for different kinds of health abnormalities including cancer and mental diseases.