Browsing by Author "da Fontoura Costa, Luciano"
Now showing 1 - 11 of 11
- Results Per Page
- Sort Options
Working Paper Characterization of Subgraphs Relationships and Distribution in Complex Networks(2008) Antiqueira, Lucas; da Fontoura Costa, Luciano"A network can be analyzed at different topological scales, ranging from single nodes to motifs, communities, up to the complete structure. We propose a novel intermediate-level topological analysis that considers non-overlapping subgraphs (connected components) and their interrelationships and distribution through the network. Though such subgraphs can be completely general, our methodology focuses the cases in which the nodes of these subgraphs share some special feature, such as being critical for the proper operation of the network. Our methodology of subgraph characterization involves two main aspects: (i)a distance histogram containing the distances calculated between all subgraphs, and (ii)a merging algorithm, developed to progressively merge the subgraphs until the whole network is covered. The latter procedure complements the distance histogram by taking into account the nodes lying between subgraphs, as well as the relevance of these nodes to the overall interconnectivity. Experiments were carried out using four types of network models and four instances of real-world networks, in order to illustrate how subgraph characterization can help complementing complex network-based studies."Working Paper Complex Systems Modeled by Multiple Interacting Agents(2008) da Fontoura Costa, Luciano"In this work we investigate learning as performed by agents interacting as they infer models of a complex system representable by a complex network, under the presence of observation errors. The models correspond to estimations of the adjacency matrix of the complex system under investigation. We focus the specific case in which, at each time step, each agent takes into account its just performed observation as well as the average of the models of its neighbors. A series of interesting results are identified with respect for Barab\'asi-Albert interaction networks. First, it is shown that the interaction among agents allows an overall improvement in the quality of the estimated models, a consequence of the averaging among neighbors. We then investigate situations in which one of the agents has different probability of observation error (twice as much higher or lower than the other agents). It is shown that the influence of this special agent over the quality of the models throughout the rest of the network is substantial and varies linearly with the respective degree of the agent with different estimation errors. In case the degree of each agent is taken as a fitness parameter, in the sense that the influence of the node over the other agents is proportional to its degree, the effect of the different estimation error is even more pronounced, becoming superlinear."Working Paper Connectivity and Dynamics of Neuronal Networks as Defined by the Shape of Individual Neurons(2008) Ahnert, Sebastian; da Fontoura Costa, Luciano"Neuronal networks constitute a special class of dynamical systems, as they are formed by individual geometrical components, namely the neurons. In the existing literature, relatively little attention has been given to the influence of neuron shape on the overall connectivity and dynamics of the emerging networks. The current work addresses this issue by considering simplified neuronal shapes consisting of circular regions (soma/axons) with spokes (dendrites). Networks are grown by placing these patterns randomly in the 2D plane and establishing connections whenever a piece of dendrite falls inside an axon. Several topological and dynamical properties of the resulting graph are measured, including the degree distribution, clustering coefficients, symmetry of connections, size of the largest connected component, as well as three hierarchical measurements of the local topology. By varying the number of processes of the individual basic patterns, we can quantify relationships between the individual neuronal shape and the topological and dynamical features of the networks. Integrate-and-fire dynamics on these networks is also investigated with respect to transient activation from a source node, indicating that long-range connections play an important role in the propagation of avalanches."Working Paper Entropy Moments Characterization of Statistical Distributions(2008) da Fontoura Costa, Luciano"This letter reports two moment extensions of the entropy of a distribution. By understanding the traditional entropy as the average of the original distribution up to a random variable transformation, the traditional moments equation become immediately applicable to entropy. We also suggest an alternative family of entropy moments. The discriminative potential of such entropy moment extensions is illustrated with respect to different types of distributions with otherwise indistinguishable traditional entropies."Working Paper Modeling the Concentric Organization of Lattices and Path-Regular Networks(2008) da Fontoura Costa, Luciano"The concentric organization of a complex network with respect to a reference node can provide rich information about both the topology and the dynamics of complex networks. Particularly, measurements such as the hierarchical number of nodes, the hierarchical degree and the intra-ring degree have been recently shown (arXiv:0802.0421 and arXiv:0802.1272) to define important features of non-linear dynamics taking place in complex networks. The current article reports theoretical models capable of reproducing with high accuracy the concentric organization, expressed in terms of the three just-mentioned measurements, of two important types of networks, namely orthogonal lattices and path-regular structures. The potential of such models is illustrated with respect to their application to systematic characterization of non-linear dynamics in those two types of networks, more specifically the prediction of avalanches of spikes and their properties. While the considered orthogonal lattices were found not to exhibit avalanches, the path-regular networks imply avalanches depending of their parametric configurations."Working Paper Sensitivity of Complex Networks Measurements(2008) Villas Boas, P. R.; Rodrigues, Francisco A.; Travieso, G.; da Fontoura Costa, Luciano"Information about real-world networks is often characterized by incompleteness and noise, which are consequences of the lack of complete data as well as artifacts in the acquisition process. Because the characterization, analysis and modeling of complex systems underlain by complex networks are critically affected by the quality of the respective structures, it becomes imperative not only to improve the quality of data, but also to devise methodologies for identifying and quantifying the effect of such sampling problems on the characterization of complex networks. In this article we report such a study, involving 10 different measurements, 4 complex networks models and 5 real world networks. We evaluate the sensitiveness of the measurements to perturbations in the topology of the network. Three particularly important types of progressive perturbations to the network are considered: edge suppression, addition and rewiring. The obtained results allowed conclusions with important practical consequences including the identification that edge removal is less critical than rewiring, followed by edge addition. The measurements allowing a better balance of stability (smaller sensitivity to perturbations) and discriminability (possibility of identification of different network topologies) were also identified."Working Paper Shape Analysis with Trajectory Networks(2008) da Fontoura Costa, Luciano"Image and shape analysis are amongst the most challenging abilities to be replicated artificially. One of the first important steps along these two tasks consists in obtaining comprehensive representations of the involved objects, capable not only of representing most of the original information, but also of emphasizing their less redundant portions. The current work reports an approach to shape characterization and classification which is based on trajectory networks, a special type of knitted geographical networks where the connections take into account not only the proximity between nodes, but also an associated vector field, here assumed to correspond to the electric field induced by the contours of the shapes. In this way, the original shape is mapped into a trajectory network, so that its measurements can reveal important features of the shapes under analysis. Optimal multivariate stochastic methods (namely discriminant analysis) are then applied in order to identify the topological measurements contributing most effectively for the separation between the objects to be analyzed and classified. It is shown that the weveral topological and geometrical measurements contribute differently to the separation between the considered set of shapes. The entropy of the angles defined by the edges, the number of nodes with degree 1, 4 and 5, as well as an alternative type of entropy, are found to contribute more strongly to the discrimination between the considered shapes."Working Paper Spiking Oscillations in Complex Neuronal Networks(2008) da Fontoura Costa, Luciano"Although integrate-and-fire dynamics possesses special importance because of its intrinsic relationship with neuronal information processing, it has been rarely considered in investigations of the structure-dynamics relationship in complex networks. However, the pronounced non-linearities of this type of dynamics implies a particularly rich variety of attractors and activity patterns, including avalanches of spikes and confinement of activation inside topological communities. Both these remarkable phenomena take place during the transient activation regime. In this work we investigate the oscillations and waves which appear in the equilibrium regime of integrate-and-fire complex neuronal networks. In order to do so, one of the restrictions of the equivalent models reported previously, namely a reasonable uniformity of degrees, is circumvented by subsuming the nodes with identical degree found inside each hierarchical levels into respective equivalent nodes. It has been shown, by considering uniformly-random and small-world theoretical types of networks, that the so-obtained model is capable of predicting the respective integrate-and-fire dynamics with great accuracy regarding both temporal dynamics and power spectrum features. The causes and properties of the stable waves emerging along the equilibrium regime of the complex neuronal networks are identified and discussed. Of particular relevance are the twin correlations defined by the different frequencies of groups of nodes at different concentric levels. The transient and equilibrium regimes are also clearly identifiable from the total activation in the networks, corresponding respectively to conservative and dissipative dynamics."Working Paper Trajectory Networks and their Topological Changes Induced by Geographical Infiltration(2008) da Fontoura Costa, Luciano"In this article we investigate the topological changes undergone by trajectory networks as a consequence of progressive geographical infiltration. Trajectory networks, a type of knitted network, are obtained by establishing paths between geographically distributed nodes while following an associated vector field. For instance, the nodes could correspond to neurons along the cortical surface and the vector field could correspond to the gradient of neurotrophic factors, or the nodes could represent towns while the vector fields would be given by economical and/or geographical gradients. Therefore trajectory networks are natural models of a large number of geographical structures. The geographical infiltrations correspond to the addition of new local connections between nearby existing nodes. As such, these infiltrations could be related to several real-world processes such as contaminations, diseases, attacks, parasites, etc. The way in which progressive geographical infiltrations affect trajectory networks is investigated in terms of the degree, clustering coefficient, size of the largest component and the lengths of the existing chains measured along the infiltrations. It is shown that the maximum infiltration distance plays a critical role in the intensity of the induced topological changes. For large enough values of this parameter, the chains intrinsic to the trajectory networks undergo a collapse which is shown not to be related to the percolation of the network also implied by the infiltrations."Working Paper Trees = Networks?(2008) da Fontoura Costa, Luciano; Rodrigues, Francisco A."This work addresses the intrinsic relationship between trees and networks (i.e. graphs). A complete (invertible) mapping is presented which allows trees to be mapped into weighted graphs and then backmapped into the original tree without loss of information. The extension of this methodology to more general networks, including unweighted structures, is also discussed and illustrated. It is shown that the identified duality between trees and graphs underlies several key concepts and issues of current interest in complex networks, including comprehensive characterization of trees and community detection. For instance, additional information about tree structures (e.g. phylogenetic trees) can be immediately obtained by taking into account several off-the-shelf network measurements--such as the clustering coefficient, degree correlations and betweenness centrality. At the same time, the hierarchical structure of networks, including the respective communities, becomes clear when the network is represented in terms of the respective tree. Indeed, the network-tree mapping described in this work provides a simple and yet effective means of community detection."Working Paper The Web of Connections between Tourism Companies in Elba: Structure and Dynamics(2008) da Fontoura Costa, Luciano; Baggio, Rodolfo"Tourism destination networks are amongst the most complex dynamical systems, involving a myriad of human-made and natural resources. In this work we report a complex network-based systematic analysis of the Elba (Italy) tourism destination network, including the characterization of its structure in terms of a set of several traditional measurements, the investigation of its modularity, as well as its comprehensive study in terms of the recently reported superedges approach. In particular, structural (the number of paths of distinct lengths between pairs of nodes, as well as the number of reachable companies) and dynamical features (transition probabilities and the inward/outward activations and accessibilities) are measured and analyzed, leading to a series of important findings related to the interactions between tourism companies. Among the several reported results, it is shown that the type and size of the companies influence strongly their respective activations and accessibilities, while their geographical position does not seem to matter. It is also shown that the Elba tourism network is largely fragmented and heterogeneous, so that it could benefit from increased integration."