Relations between ordinary energy and energy of a self-loop graph.

Let G be a graph on n vertices with vertex set V(G) and let S⊆V(G) with |S|=α. Denote by GS, the graph obtained from G by adding a self-loop at each of the vertices in S. In this note, we first give an upper bound and a lower bound for the energy of GS (E(GS)) in terms of ordinary energy (E(G)), order (n) and number of self-loops (α). Recently, it is proved that for a bipartite graph GS, E(GS)≥E(G). Here we show that this inequality is strict for an unbalanced bipartite graph GS with 0<α

Computing dominant metric dimensions of certain connected networks.

In the studies of the connected networks, metric dimension being a distance-based parameter got much more attention of the researches due to its wide range of applications in different areas of chemistry and computer science. At present its various types such as local metric dimension, mixed metric dimension, solid metric dimension, and dominant metric dimension have been used to solve the problems related to drug discoveries, embedding of biological sequence data, classification of chemical compounds, linear optimization, robot navigation, differentiating the interconnected networks, detecting network motifs, image processing, source localization and sensor networking. Dominant resolving sets are better than resolving sets because they carry the property of domination. In this paper, we obtain the dominant metric dimension of wheel, gear and anti-web wheel network in the form of integral numbers. We observe that the aforesaid networks have bounded dominant metric dimension as the order of the network increases. In particular, we also discuss the importance of the obtained results for the robot navigation networking.

On reciprocal degree distance of graphs.

Given a connected graph H, its reciprocal degree distance is defined asRDD(H)=∑x≠ydH(vx)+dH(vy)dH(vx,vy), where dH(vx) denotes the degree of the vertex vx in the graph H and dH(vx,vy) is the shortest distance between vx and vy in H. The goal of this paper is to establish some sufficient conditions to judge that a graph to be h-hamiltonian, h-path-coverable or h-edge-hamiltonian by employing the reciprocal degree distance.

Conjugated tricyclic graphs with maximum variable sum exdeg index.

The variable sum exdeg index, initially introduced by Vukicevic (2011) [20] for predicting the octanol water partition co-efficient of certain chemical compounds, is an invariant for a graph G and defined as SEIa(G)=∑v∈V(G)(dvadv), where dv is the degree of vertex v∈V(G), a is a positive real number different from 1. In this paper, we defined sub-collections of tricyclic graphs say T2m3,T2m4,T2m6 and T2m7. The graph with maximum variable sum exdeg index is characterized from each collection given above with perfect matching. Consequently, through a comparison among these extremal graphs, we indicate the graph which contains maximum SEIa-value from T2m.

Feature-enriched core percolation in multiplex networks.

Percolation models have long served as a paradigm for unraveling the structure and resilience of complex systems comprising interconnected nodes. In many real networks, nodes are identified by not only their connections but nontopological metadata such as age and gender in social systems, geographical location in infrastructure networks, and component contents in biochemical networks. However, there is little known regarding how the nontopological features influence network structures under percolation processes. In this paper we introduce a feature-enriched core percolation framework using a generic multiplex network approach. We thereby analytically determine the corona cluster, size, and number of edges of the feature-enriched cores. We find a hybrid percolation transition combining a jump and a square root singularity at the critical points in both the network connectivity and the feature space. Integrating the degree-feature distribution with the Farlie-Gumbel-Morgenstern copula, we show the existence of continuous and discrete percolation transitions for feature-enriched cores at critical correlation levels. The inner and outer cores are found to undergo distinct phase transitions under the feature-enriched percolation, all limited by a characteristic curve of the feature distribution.

Percolation of interdependent networks with limited knowledge.

Real-world networks are often not isolated and the interdependence between different networks in a complex system is as important as the topological connectivity within individual networks. We develop a theoretical framework to study the robustness of interdependent networks under attacks with limited knowledge. A node may be attacked if it is the most connected node among a given number of potential victims. This number is referred to as the attacker's knowledge level, which joins the two ends, namely, the random failure with zero knowledge and the intentional attack with full knowledge of the network. We introduce percolation models with attacks over one layer and two layers as well as mixed site-bond percolation. Along with the discontinuous phase transition, we show the existence of a critical knowledge level, which indicates a transition of network robustness under the competition between connectivity and interdependence. It is unraveled that interdependent networks can be extremely fragile to the extent that a random failure on two layers would be more deleterious than a targeted attack with full knowledge over one layer. Moreover, we find that a balanced distribution of attack knowledge on both layers tends to be most destructive if the total knowledge is a conserved quantity.

On the spectral radius and energy of signless Laplacian matrix of digraphs.

Let D be a digraph of order n and with a arcs. The signless Laplacian matrix Q ( D ) of D is defined as Q ( D ) = D e g ( D ) + A ( D ) , where A ( D ) is the adjacency matrix and D e g ( D ) is the diagonal matrix of vertex out-degrees of D. Among the eigenvalues of Q ( D ) the eigenvalue with largest modulus is the signless Laplacian spectral radius or the Q-spectral radius of D. The main contribution of this paper is a series of new lower bounds for the Q-spectral radius in terms of the number of vertices n, the number of arcs, the vertex out-degrees, the number of closed walks of length 2 of the digraph D. We characterize the extremal digraphs attaining these bounds. Further, as applications we obtain some bounds for the signless Laplacian energy of a digraph D and characterize the extremal digraphs for these bounds.

Expected value of first Zagreb connection index in random cyclooctatetraene chain, random polyphenyls chain, and random chain network.

The Zagreb connection indices are the known topological descriptors of the graphs that are constructed from the connection cardinality (degree of given nodes lying at a distance 2) presented in 1972 to determine the total electron energy of the alternate hydrocarbons. For a long time, these connection indices did not receive much research attention. Ali and Trinajstic [Mol. Inform. 37, Art. No. 1800008, 2018] examined the Zagreb connection indices and found that they compared to basic Zagreb indices and that they provide a finer value for the correlation coefficient for the 13 physico-chemical characteristics of the octane isomers. This article acquires the formulae of expected values of the first Zagreb connection index of a random cyclooctatetraene chain, a random polyphenyls chain, and a random chain network with l number of octagons, hexagons, and pentagons, respectively. The article presents extreme and average values of all the above random chains concerning a set of special chains, including the meta-chain, the ortho-chain, and the para-chain.

Percolation of attack with tunable limited knowledge.

Percolation models shed a light on network integrity and functionality and have numerous applications in network theory. This paper studies a targeted percolation (α model) with incomplete knowledge where the highest degree node in a randomly selected set of n nodes is removed at each step, and the model features a tunable probability that the removed node is instead a random one. A "mirror image" process (ß model) in which the target is the lowest degree node is also investigated. We analytically calculate the giant component size, the critical occupation probability, and the scaling law for the percolation threshold with respect to the knowledge level n under both models. We also derive self-consistency equations to analyze the k-core organization including the size of the k core and its corona in the context of attacks under tunable limited knowledge. These percolation models are characterized by some interesting critical phenomena and reveal profound quantitative structure discrepancies between Erdos-Rényi networks and power-law networks.

Resilient Consensus for Expressed and Private Opinions.

This article proposes an opinion formation model featuring both a private and an expressed opinion for a given topic over dynamical networks. Each individual in the network has a private opinion, which is not known by others but evolves under local influence from the expressed opinions of its neighbors, and an expressed opinion, which varies under a peer pressure to conform to the local environment. We design the opinion sifting strategies which are purely distributed and provide resilience to a range of adversarial environment involving locally and globally bounded threats as well as malicious and Byzantine individuals. We establish the sufficient and necessary graph-theoretic criteria for normal individuals to attain opinion consensus in both directed-fixed and time-varying networks. Two classes of opinion clustering problems are introduced as an extension. By designing the resilient opinion separation algorithms, we develop necessary and sufficient criteria, which characterize the resilient opinion clustering in terms of the ratio of opinions as well as the difference of opinions. Numerical examples, including real-world jury deliberations, are presented to illustrate the effectiveness of the proposed approaches and test the correctness of our theoretical results.

Generalized k-core percolation on correlated and uncorrelated multiplex networks.

It has been recognized that multiplexes and interlayer degree correlations can play a crucial role in the resilience of many real-world complex systems. Here we introduce a multiplex pruning process that removes nodes of degree less than k_{i} and their nearest neighbors in layer i for i=1,...,m, and establish a generic framework of generalized k-core (Gk-core) percolation over interlayer uncorrelated and correlated multiplex networks of m layers, where k=(k_{1},...,k_{m}) and m is the total number of layers. Gk-core exhibits a discontinuous phase transition for all k owing to cascading failures. We have unraveled the existence of a tipping point of the number of layers, above which the Gk-core collapses abruptly. This dismantling effect of multiplexity on Gk-core percolation shows a diminishing marginal utility in homogeneous networks when the number of layers increases. Moreover, we have found the assortative mixing for interlayer degrees strengthens the Gk-core but still gives rise to discontinuous phase transitions as compared to the uncorrelated counterparts. Interlayer disassortativity on the other hand weakens the Gk-core structure. The impact of correlation effect on Gk-core tends to be more salient systematically over k for heterogenous networks than homogeneous ones.

Opinion formation in multiplex networks with general initial distributions.

We study opinion dynamics over multiplex networks where agents interact with bounded confidence. Namely, two neighbouring individuals exchange opinions and compromise if their opinions do not differ by more than a given threshold. In literature, agents are generally assumed to have a homogeneous confidence bound. Here, we study analytically and numerically opinion evolution over structured networks characterised by multiple layers with respective confidence thresholds and general initial opinion distributions. Through rigorous probability analysis, we show analytically the critical thresholds at which a phase transition takes place in the long-term consensus behaviour, over multiplex networks with some regularity conditions. Our results reveal the quantitative relation between the critical threshold and initial distribution. Further, our numerical simulations illustrate the consensus behaviour of the agents in network topologies including lattices and, small-world and scale-free networks, as well as for structure-dependent convergence parameters accommodating node heterogeneity. We find that the critical thresholds for consensus tend to agree with the predicted upper bounds in Theorems 4 and 5 in this paper. Finally, our results indicate that multiplexity hinders consensus formation when the initial opinion configuration is within a bounded range and, provide insight into information diffusion and social dynamics in multiplex systems modeled by networks.

Consensus in averager-copier-voter networks of moving dynamical agents.

This paper deals with a hybrid opinion dynamics comprising averager, copier, and voter agents, which ramble as random walkers on a spatial network. Agents exchange information following some deterministic and stochastic protocols if they reside at the same site in the same time. Based on stochastic stability of Markov chains, sufficient conditions guaranteeing consensus in the sense of almost sure convergence have been obtained. The ultimate consensus state is identified in the form of an ergodicity result. Simulation studies are performed to validate the effectiveness and availability of our theoretical results. The existence/non-existence of voters and the proportion of them are unveiled to play key roles during the consensus-reaching process.

Groupies in multitype random graphs.

A groupie in a graph is a vertex whose degree is not less than the average degree of its neighbors. Under some mild conditions, we show that the proportion of groupies is very close to 1/2 in multitype random graphs (such as stochastic block models), which include Erdos-Rényi random graphs, random bipartite, and multipartite graphs as special examples. Numerical examples are provided to illustrate the theoretical results.

Localized recovery of complex networks against failure.

Resilience of complex networks to failure has been an important issue in network research for decades, and recent studies have begun to focus on the inverse recovery of network functionality through strategically healing missing nodes or edges. However, the effect of network recovery is far from fully understood, and a general theory is still missing. Here we propose and study a general model of localized recovery, where a group of neighboring nodes are restored in an invasive way from a seed node. We develop a theoretical framework to compare the effect of random recovery (RR) and localized recovery (LR) in complex networks including Erdos-Rényi networks, random regular networks, and scale-free networks. We find detailed phase diagrams for the subnetwork of occupied nodes and the "complement network" of failed nodes under RR and LR. By identifying the two competitive forces behind LR, we present an analytical and numerical approach to guide us in choosing the appropriate recovery strategy and provide estimation on its effect by using the degree distribution of the original network as the only input. Our work therefore provides insight for quantitatively understanding recovery process and its implications in infrastructure protection in various complex systems.

Impact of self-healing capability on network robustness.

A wide spectrum of real-life systems ranging from neurons to botnets display spontaneous recovery ability. Using the generating function formalism applied to static uncorrelated random networks with arbitrary degree distributions, the microscopic mechanism underlying the depreciation-recovery process is characterized and the effect of varying self-healing capability on network robustness is revealed. It is found that the self-healing capability of nodes has a profound impact on the phase transition in the emergence of percolating clusters, and that salient difference exists in upholding network integrity under random failures and intentional attacks. The results provide a theoretical framework for quantitatively understanding the self-healing phenomenon in varied complex systems.

Laplacian Estrada and normalized Laplacian Estrada indices of evolving graphs.

Large-scale time-evolving networks have been generated by many natural and technological applications, posing challenges for computation and modeling. Thus, it is of theoretical and practical significance to probe mathematical tools tailored for evolving networks. In this paper, on top of the dynamic Estrada index, we study the dynamic Laplacian Estrada index and the dynamic normalized Laplacian Estrada index of evolving graphs. Using linear algebra techniques, we established general upper and lower bounds for these graph-spectrum-based invariants through a couple of intuitive graph-theoretic measures, including the number of vertices or edges. Synthetic random evolving small-world networks are employed to show the relevance of the proposed dynamic Estrada indices. It is found that neither the static snapshot graphs nor the aggregated graph can approximate the evolving graph itself, indicating the fundamental difference between the static and dynamic Estrada indices.

Unveiling robustness and heterogeneity through percolation triggered by random-link breakdown.

It has been commonly recognized that heterogeneously connected networks are robust against random decays but vulnerable to malicious attacks. However, little is known about measures of heterogeneity geared towards robustness of complex networks. Here, we propose two types of percolation on general networks triggered by random-link errors, where occupied links support the nodes to be alive. Rich resilience behaviors are observed in terms of the percolation threshold and the (integrated) fraction of giant cluster. The discrepancy unraveled between the two models allows us to dynamically define compact measures that have acute discrimination in gauging network heterogeneity. The results provide a connection between network performance, structure, and dynamics.

Geometric assortative growth model for small-world networks.

It has been shown that both humanly constructed and natural networks are often characterized by small-world phenomenon and assortative mixing. In this paper, we propose a geometrically growing model for small-world networks. The model displays both tunable small-world phenomenon and tunable assortativity. We obtain analytical solutions of relevant topological properties such as order, size, degree distribution, degree correlation, clustering, transitivity, and diameter. It is also worth noting that the model can be viewed as a generalization for an iterative construction of Farey graphs.

Vulnerability of networks: fractional percolation on random graphs.

We present a theoretical framework for understanding nonbinary, nonindependent percolation on networks with general degree distributions. The model incorporates a partially functional (PF) state of nodes so that both intensity and extensity of error are characterized. Two connected nodes in a PF state cannot sustain the load and therefore break their link. We give exact solutions for the percolation threshold, the fraction of giant cluster, and the mean size of small clusters. The robustness-fragility transition point for scale-free networks with a degree distribution pk ∝ k-α is identified to be α=3. The analysis reveals that scale-free networks are vulnerable to targeted attack at hubs: a more complete picture of their Achilles' heel turns out to be not only the hubs themselves but also the edges linking them together.