Search

Recently time series prediction based on network analysis has become a hot research topic. However, how to more accurately forecast time series with good efficiency is still an open question. To address this issue, we propose an efficient time series forecasting method based on the DC algorithm and visibility relations on the vertexes set. Firstly, the time series is mapped into the network by the DC algorithm, which is a more efficient approach to generate the visibility graph. Then, we use the variation trends (slope) of those nodes that have visibility relation with the last node to get the preliminary predictive values. Afterward, the value of the last node is adopted to obtain the revised predictive values, which are assigned different weights according to node degree and time distance to get the final weighted result. To better demonstrate the prediction performance and applicability of the proposed method, the proposed method is applied to different time series data sets. The empirical results show that the proposed method could provide a higher level of forecasting accuracy than many methods with relatively lower time complexity.

Reconstructing complex networks from observed data is a fundamental problem in network science. Compressive sensing, widely used for recovery of sparse signals, has also been used for network reconstruction under the assumption that networks are sparse. However, heterogeneous networks are not exactly sparse. Moreover, when using compressive sensing to recover signals, the projection matrix is usually a random matrix that satisfies the restricted isometry property (RIP) condition. This condition is much harder to satisfy during network reconstruction because the projection matrix depends on time-series data of network dynamics. To overcome these shortcomings, we devised a novel approach by adapting the alternating direction method of multipliers to find a candidate adjacency matrix. Then we used clustering to identify high-degree nodes. Finally, we replaced the elements of the candidate adjacency vectors of high-degree nodes, which are likely to be incorrect, with the corresponding elements of small-degree nodes, which are likely to be correct. The proposed method thus overcomes the shortcomings of compressive sensing and is suitable for reconstructing heterogeneous networks. Experiments with both artificial scale-free and empirical networks showed that the proposed method is accurate and robust.

In diffusion tensor imaging, structural connectivity between brain regions is often measured by the number of white matter fiber tracts connecting them. Other features such as the length of tracts or fractional anisotropy (FA) are also used in measuring the strength of connectivity. In this study, we investigated the effects of incorporating the number of tracts, the tract length and FA-values into the connectivity model. Using various node-degree based graph theory features, the three connectivity models are compared. The methods are applied in characterizing structural networks between normal controls and maltreated children, who experienced maltreatment while living in post-institutional settings before being adopted by families in the US.

Natural and engineered networks, such as interconnected neurons, ecological and social networks, coupled oscillators, wireless terminals and power loads, are characterized by an appreciable heterogeneity in the local connectivity around each node. For instance, in both elementary structures such as stars and complex graphs having scale-free topology, a minority of elements are linked to the rest of the network disproportionately strongly. While the effect of the arrangement of structural connections on the emergent synchronization pattern has been studied extensively, considerably less is known about its influence on the temporal dynamics unfolding within each node. Here, we present a comprehensive investigation across diverse simulated and experimental systems, encompassing star and complex networks of Rössler systems, coupled hysteresis-based electronic oscillators, microcircuits of leaky integrate-and-fire model neurons, and finally recordings from in-vitro cultures of spontaneously-growing neuronal networks. We systematically consider a range of dynamical measures, including the correlation dimension, nonlinear prediction error, permutation entropy, and other information-theoretical indices. The empirical evidence gathered reveals that under situations of weak synchronization, wherein rather than a collective behavior one observes significantly differentiated dynamics, denser connectivity tends to locally promote the emergence of stronger signatures of nonlinear dynamics. In deterministic systems, transition to chaos and generation of higher-dimensional signals were observed; however, when the coupling is stronger, this relationship may be lost or even inverted. In systems with a strong stochastic component, the generation of more temporally-organized activity could be induced. These observations have many potential implications across diverse fields of basic and applied science, for example, in the design of distributed sensing systems based on wireless coupled oscillators, in network identification and control, as well as in the interpretation of neuroscientific and other dynamical data.

In the vision of the Internet of Things (IoT), objects become smart by aggregating in a network and exchanging information. Thanks to this shared knowledge, the objects can interact for performing advanced tasks. The obtrusiveness of the services is guaranteed by the mobility of the smart objects. For example, mobile sensors are used to follow dynamic phenomena, whereas smartphones and wearable devices are always accessible to the user. The interaction among the smart devices can be described by means of a graph, where nodes, representing IoT objects, are linked if they can communicate. This paper studies the node degree (i.e., the number of links of the node) in a graph developed for describing heterogeneous wireless networks. With respect to previous work, the mobility of the network, which can change the degree of every node, is considered for the first time. Formulas for the degree distribution and the average degree are theoretically computed and then validated with simulations. In particular, as a case study the proposed formulas are applied considering IoT objects following the random waypoint model, one of the most common mobility models.

Refined topological relations play an important role in spatial database quality control. Currently, there is no unified and reasonable method to represent refined line/region and line/line topological relations in two-dimensional (2D) space. In addition, the existing independent line/region and line/line models have some drawbacks such as incomplete type discrimination and too many topological invariants. In this paper, a refined line/region and line/line topological relations are represented uniformly by the sequence, dimension, and topological type of the intersection components. To make the relevant definitions conform to the traditional cognitions in 2D Euclidean space, the (simple) spatial object is defined based on manifold topology, and the spatial intersection components are defined based on the whole-whole object intersection set. Then the topological invariant of node degree is introduced, and the adjacent point kinds (e.g., &ldquo, Null&rdquo, &ldquo, On&rdquo, In&rdquo, and &ldquo, Out&rdquo, ) are defined to distinguish the intersection component types. Excluding impossible and symmetrical types, 29 types of intersection-lines (including 21 between lines/regions and 8 between lines/lines), and 6 types of intersection-points (including 2 between lines/regions and 4 between lines/lines) are classified. On this basis, a node degree-based whole-whole object intersection sets (N-WWIS) model for refined line/region and line/line topological relations is presented, and it can be combined with the Euler number-based whole object intersection and difference (E-WID) model (coarse level) to form a hierarchical representation method of topological relations. Furthermore, a prototype system based on the N-WWIS model for automatic topological integrity checking is developed and some evaluation experiments are conducted with OpenStreetMap (OSM) data is presented based on the classification of intersection components. The experimental results show that the N-WWIS model will enable the geographic information systems (GIS) community to develop automated topological conflict checking and dealing tools for spatial data updates and quality control.

Social networking has been a feature of human society. From the early hunter-gatherer tribes, medieval guilds, the twentieth century workplaces, up to online entities like Facebook and Twitter, it is difficult to think of a time or place where all people did not belong to at least one cooperative group. It follows that social network formation has been studied extensively in the past decades and will continue to be a popular area of research. Past research has primarily confined itself to considering cases in which new members are introduced into the networks by making a constant number of connections to those who are already present in the networks. Our study aims to fill the glaring gap in the variety of network formation modelling. Most notably, we want to consider scenarios in which the number of connections new members make to those already present in the networks is determined by chance. More specifically, the number of connections made to existing members when a new one is introduced into the network is characterized by a positive integer-valued random variable. The objective of the study is to determine the distribution of degree of a node in this kind of social networks. It is determined that the node degree distribution is a mixture of geometric distributions. Three numerical examples are provided in the study to demonstrate the validity of our findings.

For efficient running of wireless sensor network applications, energy conservation of the sensors becomes a prime paradigm for prolonging lifetime of the network. Taking this aspect into consideration, a cluster head weight selection method called Cluster Chain Weight Metrics approach (CCWM) has been discussed that takes service parameters for enhancing performance of the overall network. In a clustering based approach one of the main concerns is selection of appropriate cluster heads in the network and the formation of balanced clusters. Cluster heads are selected first in a network based on weight metric and then cluster formation takes place. This approach not only aims to conserve energy of sensors but also balances load. A local clustering mechanism is adopted within the cluster to reduce computation and communication cost. Also, a new technique for data transmission is explored. The results of the proposed approach are compared through simulation with LEACH, WCA and IWCA. The proposed approach shows an improvement on an average over rounds by 51% over LEACH, 27% from WCA and 18.8% from IWCA in terms of lifetime and energy consumption.

Being able to generate large synthetic graphs resembling those found in the real world, is of high importance for the design of new graph algorithms and benchmarks. In this paper, we first compare several probability models in terms of goodness-of-fit, when used to model the degree distribution of real graphs. Second, after confirming that the MOEZipf model is the one that gives better fits, we present a method to generate MOEZipf distributions. The method is shown to work well in practice when implemented in a scalable synthetic graph generator.

Date of Conference: 19-25 April 2009 Conference name: INFOCOM 2009. 28th IEEE International Conference on Computer Communications Designing an overlay network for publish/subscribe communication in a system where nodes may subscribe to many different topics of interest is of fundamental importance. For scalability and efficiency, it is important to keep the degree of the nodes in the publish/subscribe system low. It is only natural then to formalize the following problem: Given a collection of nodes and their topic subscriptions, connect the nodes into a graph that has least possible maximum degree in such a way that for each topic t, the graph induced by the nodes interested in t is connected. We present the first polynomial-time logarithmic approximation algorithm for this problem and prove an almost tight lower bound on the approximation ratio. Our experimental results show that our algorithm drastically improves the maximum degree of publish/subscribe overlay systems. We also propose a variation of the problem by enforcing that each topic-connected overlay network be of constant diameter while keeping the average degree low. We present three heuristics for this problem that guarantee that each topic-connected overlay network will be of diameter 2 and that aim at keeping the overall average node degree low. Our experimental results validate our algorithms, showing that our algorithms are able to achieve very low diameter without increasing the average degree by much. © 2011 IEEE.

The paper deals with radio network distributed algorithms where nodes are not aware of their one hop neighborhood. Given an n-node graph modeling a multihop network of radio devices, we give a O(log^2 n) time distributed algorithm that computes w.h.p., a constant approximation value of the degree of each node. We also provide a O( \Delta log n + log^2 n) time distributed algorithm that computes w.h.p., a constant approximation value of the local maximum degree of each node, where the global maximum degree \Delta of the graph is not known. Using our algorithms as a plug-and-play procedure, we show that many existing distributed algorithms requiring the knowledge of to execute efficiently can be run with essentially the same time complexity by using the local maximum degree instead of . In other words, using the local maximum degree is sufficient to break the symmetry in a local and efficient manner. We illustrate this claim by investigating the complexity of some basic problems. First, we investigate the generic problem of simulating any classical message passing algorithm in the radio network model. Then, we study the fundamental edge/node coloring problem in the special case of unit disk graphs. The obtained results show that knowing the local maximum degree allows to coordinate the nodes locally and avoid interferences in radio networks.

We propose a distributed algorithm to construct a balanced communication tree that serves in gathering data from the network nodes to a sink. Our algorithm constructs a near-optimally balanced communication tree with minimum overhead. The balancing of the node degrees results in the minimization of packet collisions during query execution, that would otherwise require numerous retransmissions and reduce the lifetime of the network. We compare our simple distributed algorithm against previous work and a centralized solution and show that for most network layouts it outperforms competition and achieves tree balance very close to the centralized algorithm. It also has the smallest energy overhead possible to construct the tree, increasing the lifetime of the network even more. Copyright 2010 ACM. 33 40 Sponsors: ACM SIGMOD Conference code: 82003 Cited By :11

As a branch of topology control, power control is of great importance to prolong the survival time of the network. A transmission power control algorithm is proposed under the minimum connected average node degree constraint in this paper. Using a Poisson point process in two dimensions, we derive an analytical expression that determines the required transmission range to achieve a specified connectivity probability for a given node density, and then the minimum connected average node degree is obtained. Based on the above results, an algorithm named MCAND is designed to achieve the given connected probability by adjusting the transmission power of each node dynamically, with the node degree equal to the minimum connected average node degree. Simulation results show that the performance of our algorithm is superior to that of the related algorithms based on node degree in terms of coverage and connectivity.