Narrow Results

This paper introduces the penmutational graph, a new network topology, which preserves the same desirable properties as those of a star graph topology. A permutational graph can be decomposed into subgraphs induced by node sets defined by equivalence classes. Using this decomposition, its structual properties as well as the relationship among graph families, permutational graphs, star graphs, and complete graphs are studied. Moreover, the diameters of permutational graphs are investigated and good estimates are obtained which are better than those of some network topologies of similar orders.

In a distributed system, each entity has a label (port number) associated to each of its neighbors. It is well known that if the labeling satisfies a global consistency property called Sense of Direction, the communication complexity of many distributed problem can be greatly reduced. This property is assumed to be present and it is implicitly used in most interconnection networks.

In this paper we investigate the nature of the relationship between Sense of Direction and network topology. We first consider the class of labelings which only satisfy the requirement of local orientation; that is, at each node, the outgoing edges have distinct labels. We then consider the class of labelings which also satisfy edge symmetry; that is, there exists a correlation between the labels neighbors give to their connecting edge. This class includes most of used labelings. We completely characterize the interplay between topological constraints and consistency constraints for these two classes of labelings. In fact, for each class, we identify both the set of forbidden subgraphs and the set of feasible graphs, and we show that the characterization is complete.

It is clear that the topological structure of a neural network somehow determines the activity of the neurons within it. In the present work, we ask to what extent it is possible to examine the structural features of a network and learn something about its activity? Specifically, we consider how the centrality (the importance of a node in a network) of a neuron correlates with its firing rate. To investigate, we apply an array of centrality measures, including In-Degree, Closeness, Betweenness, Eigenvector, Katz, PageRank, Hyperlink-Induced Topic Search (HITS) and NeuronRank to Leaky-Integrate and Fire neural networks with different connectivity schemes. We find that Katz centrality is the best predictor of firing rate given the network structure, with almost perfect correlation in all cases studied, which include purely excitatory and excitatory–inhibitory networks, with either homogeneous connections or a small-world structure. We identify the properties of a network which will cause this correlation to hold. We argue that the reason Katz centrality correlates so highly with neuronal activity compared to other centrality measures is because it nicely captures disinhibition in neural networks. In addition, we argue that these theoretical findings are applicable to neuroscientists who apply centrality measures to functional brain networks, as well as offer a neurophysiological justification to high level cognitive models which use certain centrality measures.

In the present work, the effects of spatial constraints on the efficiency of task execution in systems underlain by geographical complex networks are investigated, where the probability of connection decreases with the distance between the nodes. The investigation considers several configurations of the parameters defining the network connectivity, and the Barabási–Albert network model is also considered for comparisons. The results show that the effect of connectivity is significant only for shorter tasks, the locality of connections implied by the spatial constraints reduces efficiency, and the addition of edges can improve the efficiency of the execution, although with increasing locality of the connections the improvement is small.

Network topology is the basic for the development of traffic management and control. In a road network, bayonets with installation of surveillance facilities are key components to recognize traffic congestion from time to time. Therefore, identifying the essential bayonets in a road network becomes one of the most efficient ways to alleviate traffic congestion for traffic engineers and transport department. To do so, this paper aims to propose a novel sorting algorithm based on similarity measurements and traffic flow information to efficiently identify key bayonets in road networks. Our research results show that by analyzing the bayonet data in a fixed period of time in a medium-sized city of China, we have successfully identified the location of key bayonet points. Most of these key bayonet points are closed to residential areas and important traffic stations. The rank of these bayonet points can help the city managers better understand the topological characteristics of the road network as well as the propagation of congestion so as to make the traffic policies or control strategies for traffic congestion alleviation.

This paper investigates the influence of the interconnection network topology of a parallel system on the delivery time of an ensemble of messages, called the communication scheme. More specifically, we focus on the impact on the performance of structure in network topology and communication scheme. We introduce causal structure learning algorithms for the modeling of the communication time. The experimental data, from which the models are learned automatically, is retrieved from simulations. The qualitative models provide insight about which and how variables influence the communication performance. Next, a generic property is defined which characterizes the performance of individual communication schemes and network topologies. The property allows the accurate quantitative prediction of the runtime of random communication on random topologies. However, when either communication scheme or network topology exhibit regularities the prediction can become very inaccurate. The causal models can also differ qualitatively and quantitatively. Each combination of communication scheme regularity type, e.g. a one-to-all broadcast, and network topology regularity type, e.g. torus, possibly results in a different model which is based on different characteristics.

Fault-tolerance and lookup consistency are considered crucial properties for building applications on top of structured overlay networks. Many of these networks use the ring topology for the organization or their peers. The network must handle multiple joins, leaves and failures of peers while keeping the connection between every pair of successor-predecessor correct. This property makes the maintenance of the ring very costly and temporarily impossible to achieve, requiring periodic stabilization for fixing the ring. We introduce the relaxed-ring topology that does not rely on a perfect successor-predecessor relationship and it does not need a any periodic maintenance. Leaves and failures are considered as the same type of event providing a fault-tolerant and self-organizing maintenance of the ring. Relaxed-ring's limitations with respect to failure handling are formally identified, providing strong guarantees to develop applications on top of the architecture. Besides permanent failures, the paper analyses temporary failures and false suspicions caused by broken links, which are often ignored.

In order to deal with multidimensional structure representations of real-world networks, as well as with their worst-case irreducible information content analysis, the demand for new graph abstractions increases. This article investigates incompressible multidimensional networks defined by generalized graph representations. In particular, we mathematically study the lossless incompressibility of snapshot-dynamic networks and multiplex networks in comparison to the lossless incompressibility of more general forms of dynamic networks and multilayer networks, from which snapshot-dynamic networks or multiplex networks are particular cases. Our theoretical investigation first explores fundamental and basic conditions for connecting the sequential growth of information with sequential interdimensional structures such as time in dynamic networks, and secondly it presents open problems demanding future investigation. Although there may be a dissonance between sequential information dynamics and sequential topology in the general case, we demonstrate that incompressibility (or algorithmic randomness) dissolves it, preventing both the algorithmic dynamics and the interdimensional structure of multidimensional networks from displaying a snapshot-like behavior (as characterized by any arbitrary mathematical theory). Thus, beyond methods based on statistics or probability as traditionally seen in random graphs and complex networks models, representational incompressibility implies a necessary underlying constraint in the multidimensional network topology. We argue that the study of how isomorphic transformations and their respective algorithmic information distortions can characterize sequential interdimensional structures in (multidimensional) networks helps the analysis of network topological properties while being agnostic to the chosen theory, algorithm, computation model, and programming language.

As the world is currently in turmoil, geopolitical crises and economic policy uncertainties are increasing significantly. This study aims to provide insight into the dynamics of time–frequency spillovers in the domains of crude oil, geopolitical risk, economic policy uncertainty and stock markets. It represents the first investigation analyzing the time-varying frequency connectedness across the aforementioned domains by adopting the time-varying parameter vector autoregression connectedness combined with the time-varying frequency connectedness measurement [Chatziantoniou et al., 2023]. The study covers the period from January 2004 to February 2023, including the 2008 financial crisis, the COVID-19 pandemic and the turmoil caused by the 2022 Russian–Ukrainian conflict. The analysis finds that short-term frequencies dominate return connectedness, indicating a rapid information processing mechanism responsive to short-run shocks. The stock market indices of oil-exporting countries, the US and the UK act as the primary transmitters of return spillovers. Volatility connectedness is driven by long-term frequencies, with Russia, Canada and the UK serving as the primary volatility spillover transmitters. Economic policy uncertainty is primarily influenced by oil-importing countries. Geopolitical risk mostly serves as the spillover receiver from crude oil, while it primarily transmits spillovers to economic policy uncertainty during major events such as terror attacks, conflicts and wars. The 2022 Russian–Ukrainian conflict amplifies spillovers to economic policy uncertainty. Intriguingly, conflicts deepen economic policy uncertainty, and prior to the conflict, stock market volatility had assimilated the influence of geopolitical risk shocks. The study also employs network topology to visualize spillover transmission mechanisms during the 2022 Russian–Ukrainian conflict.

Community detection is one of the primary tools to discover useful information that is hidden in complex networks. Some community detection algorithms for bipartite networks have been proposed from various viewpoints. However, the performance of these algorithms deteriorates when the community structure becomes unclear. Enhancing community structure remains a nontrivial task. In this paper, we propose a community detection algorithm, called ECD, that enhances community structure in bipartite networks. In the proposed ECD, the topology of a network is modified by reducing unnecessary edges that are connected to neighboring low-weight communities. Therefore, an ambiguous community structure is converted into a structure that is much clearer than the original structure. The experimental results on both artificial and real-world networks verify the accuracy and reliability of our algorithm. Compared with existing community detection algorithms using state-of-the-art methods, our algorithm has better performance.

A social network is composed of social individuals and their relationships. In many real-world applications, such a network will evolve dynamically over time and events. A social network can be naturally viewed as a multiagent system if considering locally-interacting social individuals as autonomous agents. In this paper, we present an Autonomy-Oriented Computing (AOC) based model of a social network, and study the dynamics of the network based on this model. In the AOC model, the profile of agents, service-based interactions, and the evolution of the network are defined, and the autonomy of the agents is emphasized. The model can reveal dynamic relationships among global performance, local interaction (partner selection) strategies, and network topology. The experimental results show that the agent network forms a community with a high clustering coefficient, and the performance of the network is dynamically changing along with the formation of the network and the local interaction strategies of the agents. In this paper, the performance and topology of the agent network are analyzed, and the factors that affect the performance and evolution of the agent network are examined.

We define a new concept, a hyperstructure, which is related to networks and hypernetworks and allows us to represent real problems. We also define the efficiency of this hyperstructure and we apply it to an example.

The aim of this paper is to contribute to the modeling and analysis of complex systems, taking into account the nature of complexity at different stages of the system life-cycle: from its genesis to its evolution. Therefore, some structural aspects of the complexity dynamics are highlighted, leading (i) to implement the morphogenesis of emergent complex network structures, and (ii) to control some synchronization phenomena within complex networks. Specific applications are proposed to illustrate these two aspects, in urban dynamics and in neural networks.

Much research attention has been devoted to the investigation of how the structure of a network affects its intended performance. However, conclusions drawn from the previous studies are often inconsistent and even contradictory. In order to identify the causes of these diverse results and to explore the impact of network topology on performance, we apply the concept of bifurcation in dynamical systems and consider the effect of varying a crucial parameter for networks of different structures. In this paper, we study transmission networks and identify the capacity setting as the parameter. Upon varying this parameter, the behavioral change of the network is observed. Specifically, we focus on communication networks and power grids, and study the improvement or degradation of robustness of such networks under variation of link capacity. We observe that the effect of increasing link capacity on robustness differs for different networks, and a bifurcation point exists in some cases which divides regions of opposite robustness behavior. Our work demonstrates that capacity settings play a crucially important role in determining how network structure affects the intended performance of transmission networks, and clarifies the previous reported contradictory results.

A wireless sensor network (WSN) is a distributed system composed of autonomous sensor nodes wireless connected and randomly scattered into a geographical area to cooperatively monitor physical or environmental conditions. Adequate techniques and strategies are required to manage a WSN in order it works properly, mainly focusing on its reliability. From the system reliability perspective, it is important to take into account that WSN nodes are usually battery-powered and the WSN reliability strongly depends on the power management at node level. Since standby power management policies are often applied at node level and, moreover, interferences among nodes may arise, a WSN can be considered as a system affected by dynamic-dependent behaviors among its components and therefore, the dynamic reliability approach can be applied. Static-structural interactions are specified by the WSN topology. Active–sleep standby policies and interferences due to wireless communications can be instead considered as dynamic aspects. Thus, in order to represent and to evaluate the WSN reliability dynamic reliability block diagrams are used in this paper. The proposed technique allows to overcome the limits of Markov models when considering nonlinear discharge processes, since such models cannot adequately represent the node aging process. In order to demonstrate the effectiveness of the DRBD technique in this context, we investigate some specific WSN network topologies, providing guidelines for their representation and evaluation.

Generalized Hypercube-Connected-Cycles (GHCC), is a challenging interconnection network, proposed earlier in the literature. In this paper, we discuss how some important, useful algorithms, like, matrix transpose, matrix multiplication and sorting can efficiently be implemented on GHCC. Matrix transpose and matrix-by-matrix multiplication of matrices of order n × n, , takes O(l) and time, respectively, on GHCC(l,m), with lm^l processors. Using the same number of processors, a list of m^l numbers can be sorted in O(l²log³ m) time.

Current studies of "messy" broadcasting have so far concentrated on finding worst-case times. However, such worst-case scenarios are extremely unlikely to occur in general. Hence, determining average-case times or tight upper bounds for completing "messy" broadcasting in various network topologies is both necessary and meaningful in practice. In this paper, we focus on seeking the average-case "messy" broadcast times of stars, paths, cycles, and d-ary trees, and finding good upper bounds for hypercubes. Finally, we derive a recursive formula to express the average-case time for a specific "messy" broadcast model on a complete graph using a classical occupancy problem in probability theory, and provide a nice simulation result which indicates that this model behaves like classical broadcasting.

This paper presents a family of minimal-diameter, four-regular nonbipartite circulants on 2a² vertices, where a is odd. If a ≡ 3 mod (4), then the step sizes are 1 and (a − 1)², and if a ≡ 1 mod (4), then the step sizes are 1 and (a + 1)². Each graph is obtainable from the 2a × a rectangular twisted torus by appropriately trading a total of 3a − 1 edges for as many new edges. Further, each admits an almost-square L-shaped embedding in the two-dimensional Cartesian plane, facilitating a plane tessellation that leads to an efficient dimension-order routing algorithm.

We report on replications of early experiments with FEARLUS, using larger numbers of agents, larger numbers of land parcels, and greater network connectivity than in the original work. We find that results from the larger-scale experiments differ from the smaller environments used previously. Whilst results from small communities of agents and environments should not be ignored just because the same effect is not observed in larger communities (and indeed vice versa), this work does raise the extent to which more general conclusions can be drawn from agent-based studies involving fixed population or environment sizes.

In this work, we analyze gossip spreading on weighted networks. We try to define a new metric to classify weighted complex networks using our model. The model proposed here is based on the gossip spreading model introduced by Lind et al. on unweighted networks. The new metric is based on gossip spreading activity in the network, which is correlated with both topology and relative edge weights in the network. The model gives more insight about the weight distribution and correlation of topology with edge weights in a network. It also measures how suitable a weighted network is for gossip spreading. We analyze gossip spreading on real weighted networks of human interactions. Six co-occurrence and seven social pattern networks are investigated. Gossip propagation is found to be a good parameter to distinguish co-occurrence and social pattern networks. As a comparison some miscellaneous networks of comparable sizes and computer generated networks based on ER, BA and WS models are also investigated. They are found to be quite different from the human interaction networks.