首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
Complex networks appear in almost every aspect of science and technology. Previous work in network theory has focused primarily on analyzing single networks that do not interact with other networks, despite the fact that many real-world networks interact with and depend on each other. Very recently an analytical framework for studying the percolation properties of interacting networks has been introduced. Here we review the analytical framework and the results for percolation laws for a Network Of Networks (NONs) formed by n interdependent random networks. The percolation properties of a network of networks differ greatly from those of single isolated networks. In particular, because the constituent networks of a NON are connected by node dependencies, a NON is subject to cascading failure. When there is strong interdependent coupling between networks, the percolation transition is discontinuous (first-order) phase transition, unlike the well-known continuous second-order transition in single isolated networks. Moreover, although networks with broader degree distributions, e.g., scale-free networks, are more robust when analyzed as single networks, they become more vulnerable in a NON. We also review the effect of space embedding on network vulnerability. It is shown that for spatially embedded networks any finite fraction of dependency nodes will lead to abrupt transition.  相似文献   

2.
In this article, we introduce a framework to address filtering and smoothing with mobile sensor networks for distributed parameter systems. The main problem is formulated as the minimization of a functional involving the trace of the solution of a Riccati integral equation with constraints given by the trajectory of the sensor network. We prove existence and develop approximation of the solution to the Riccati equation in certain trace-class spaces. We also consider the corresponding optimization problem. Finally, we employ a Galerkin approximation scheme and implement a descent algorithm to compute optimal trajectories of the sensor network. Numerical examples are given for both stationary and moving sensor networks.  相似文献   

3.
On effectiveness of wiretap programs in mapping social networks   总被引:1,自引:0,他引:1  
Snowball sampling methods are known to be a biased toward highly connected actors and consequently produce core-periphery networks when these may not necessarily be present. This leads to a biased perception of the underlying network which can have negative policy consequences, as in the identification of terrorist networks. When snowball sampling is used, the potential overload of the information collection system is a distinct problem due to the exponential growth of the number of suspects to be monitored. In this paper, we focus on evaluating the effectiveness of a wiretapping program in terms of its ability to map the rapidly evolving networks within a covert organization. By running a series of simulation-based experiments, we are able to evaluate a broad spectrum of information gathering regimes based on a consistent set of criteria. We conclude by proposing a set of information gathering programs that achieve higher effectiveness then snowball sampling, and at a lower cost. Maksim Tsvetovat is an Assistant Professor at the Center for Social Complexity and department of Public and International Affairs at George Mason University, Fairfax, VA. He received his Ph.D. from the Computation, Organizations and Society program in the School of Computer Science, Carnegie Mellon University. His dissertation was centered on use of artificial intelligence techniques such as planning and semantic reasoning as a means of studying behavior and evolution of complex social networks, such as these of terrorist organizations. He received a Master of Science degree from University of Minnesota with a specialization in Artificial Intelligence and design of Multi-Agent Systems, and has also extensively studied organization theory and social science research methods. His research is centered on building high-fidelity simulations of social and organizational systems using concepts from distributed artificial intelligence and multi-agent systems. Other projects focus on social network analysis for mapping of internal corporate networks or study of covert and terrorist orgnaizations. Maksim’s vita and publications can be found on Kathleen M. Carley is a professor in the School of Computer Science at Carnegie Mellon University and the director of the center for Compuational Analysis of Social and Organizational Systems (CASOS) which has over 25 members, both students and research staff. Her research combines cognitive science, social networks and computer science to address complex social and organizational problems. Her specific research areas are dynamic network analysis, computational social and organization theory, adaptation and evolution, text mining, and the impact of telecommunication technologies and policy on communication, information diffusion, disease contagion and response within and among groups particularly in disaster or crisis situations. She and her lab have developed infrastructure tools for analyzing large scale dynamic networks and various multi-agent simulation systems. The infrastructure tools include ORA, a statistical toolkit for analyzing and visualizing multi-dimensional networks. ORA results are organized into reports that meet various needs such as the management report, the mental model report, and the intelligence report. Another tool is AutoMap, a text-mining systems for extracting semantic networks from texts and then cross-classifying them using an organizational ontology into the underlying social, knowledge, resource and task networks. Her simulation models meld multi-agent technology with network dynamics and empirical data. Three of the large-scale multi-agent network models she and the CASOS group have developed in the counter-terrorism area are: BioWar a city-scale dynamic-network agent-based model for understanding the spread of disease and illness due to natural epidemics, chemical spills, and weaponized biological attacks; DyNet a model of the change in covert networks, naturally and in response to attacks, under varying levels of information uncertainty; and RTE a model for examining state failure and the escalation of conflict at the city, state, nation, and international as changes occur within and among red, blue, and green forces. She is the founding co-editor with Al. Wallace of the journal Computational Organization Theory and has co-edited several books and written over 100 articles in the computational organizations and dynamic network area. Her publications can be found at: http://www.casos.cs.cmu.edu/bios/carley/publications.php  相似文献   

4.
Given a set of points in the plane and a constant t1, a Euclidean t-spanner is a network in which, for any pair of points, the ratio of the network distance and the Euclidean distance of the two points is at most t. Such networks have applications in transportation or communication network design and have been studied extensively.

In this paper we study 1-spanners under the Manhattan (or L1-) metric. Such networks are called Manhattan networks. A Manhattan network for a set of points is a set of axis-parallel line segments whose union contains an x- and y-monotone path for each pair of points. It is not known whether it is NP-hard to compute minimum Manhattan networks (MMN), i.e., Manhattan networks of minimum total length. In this paper we present an approximation algorithm for this problem. Given a set P of n points, our algorithm computes in O(nlogn) time and linear space a Manhattan network for P whose length is at most 3 times the length of an MMN of P.

We also establish a mixed-integer programming formulation for the MMN problem. With its help we extensively investigate the performance of our factor-3 approximation algorithm on random point sets.  相似文献   


5.
Dynamic structure-based neural networks are being extensively applied in many fields of science and engineering. A novel dynamic structure-based neural network determination approach using orthogonal genetic algorithm with quantization is proposed in this paper. Both the parameter (the threshold of each neuron and the weight between neurons) and the transfer function (the transfer function of each layer and the network training function) of the dynamic structure-based neural network are optimized using this approach. In order to satisfy the dynamic transform of the neural network structure, the population adjustment operation was introduced into orthogonal genetic algorithm with quantization for dynamic modification of the population’s dimensionality. A mathematical example was applied to evaluate this approach. The experiment results suggested that this approach is feasible, correct and valid.  相似文献   

6.
This paper studies the approach to the fourth-generation warfare (4GW) paradigm from the perspective of physical and mathematical disciplines, through the interdisciplinary bridge offered by the analysis of complex networks. The study is within an emerging multidisciplinary field, Sociophysics, which attempts to apply statistical mechanics and the science of complex systems to predict human social behavior. The fourth-generation warfare concept is reviewed, and the war of the Jihadist Islam against the West will be contextualized as 4GW. The paradigm of complex systems has in diverse branches of science changed how collective phenomena are processed. The jihadist networks phenomenon in particular is appropriate for study from the standpoint of complex networks. We present an empirical study of the 9/11 and 11M networks, implemented from public information, and we give a comparison of both networks from the standpoint of complex networks. Several authors have made use of the phenomenon of percolation in complex physical systems to analyse complex networks, particularly jihadist actions like 9/11. The relationship between jihadist networks and percolation is considered. The percolation concept is reviewed and related to 4GW, and the definition of memetic dimension is introduced.  相似文献   

7.
从复杂网络的视角,建立了各产业部门之间的投入产出关联复杂网络模型,利用国民经济核算司发布的投入产出数据,分析了投入产出关联网络的边权分布、强度分布和聚集系数等主要网络属性,尝试揭示了我国国民经济系统中各产业部门之间复杂的投入产出关联关系.  相似文献   

8.
Henderson  W.  Taylor  P.G. 《Queueing Systems》2001,37(1-3):163-197
The seminal paper of Jackson began a chain of research on queueing networks with product-form stationary distributions which continues strongly to this day. Hard on the heels of the early results on queueing networks followed a series of papers which discussed the relationship between product-form stationary distributions and the quasireversibility of network nodes. More recently, the definition of quasireversibility and the coupling mechanism between nodes have been extended so that they apply to some of the later product-form queueing networks incorporating negative customers, signals, and batch movements.In parallel with this research, it has been shown that some special queueing networks can have arrival and service parameters which depend upon the network state, rather than just the node state, and still retain a generalised product-form stationary distribution.In this paper we begin by offering an alternative proof of a product-form result of Chao and Miyazawa and then build on this proof by postulating a state-dependent coupling mechanism for a quasireversible network. Our main theorem is that the resultant network has a generalised product form stationary distribution. We conclude the paper with some examples.  相似文献   

9.
Blocking in queueing network models with finite capacities can lead to deadlock situations. In this paper, deadlock properties are investigated in queueing networks with multiple routing chains. The necessary and sufficient conditions for deadlockfree queueing networks with blocking are provided. An optimization algorithm is presented for finding deadlock-free capacity assignments with the least total capacity. The optimization algorithm maps the queueing network into a directed graph and obtains the deadlock freedom conditions from a specified subset of cycles in the directed graph. In certain network topologies, the number of deadlock freedom conditions can be large, thus, making any optimization computationally expensive. For a special class of topologies, so-calledtandem networks, it is shown that a minimal capacity assignment can be directly obtained without running an optimization algorithm. Here, the solution to the minimal capacity assignment takes advantage of the regular topology of tandem networks.This work was supported by the National Science Foundation under Grant No. CCR-90-11981.  相似文献   

10.
Node importance or centrality evaluation is an important methodology for network analysis. In this paper, we are interested in the study of objects appearing in several networks. Such common objects are important in network-network interactions via object-object interactions. The main contribution of this paper is to model multiple networks where there are some common objects in a multivariate Markov chain framework, and to develop a method for solving common and non-common objects' stationary probability distributions in the networks. The stationary probability distributions can be used to evaluate the importance of common and non-common objects via network-network interactions. Our experimental results based on examples of co-authorship of researchers in different conferences and paper citations in different categories have shown that the proposed model can provide useful information for researcher-researcher interactions in networks of different conferences and for paper-paper interactions in networks of different categories.  相似文献   

11.
In the literature several authors describe methods to construct simplified models of networks. These methods are motivated by the need to gain insight into the main properties of medium sized or large networks. The present paper contributes to this research by setting focus on weighted networks, the geographical component of networks and introducing a class of functions to model how the weights propagate from one level of abstraction to the next. Hierarchies of network models can be constructed from reordering of the adjacency matrix of the network; this is how “hypernodes” are derived in the present paper. The hypernode algorithm is explored and it is shown how it can be formulated to handle weighted networks. Weighted networks enable handling the uncertainty or the strength of the components which make up the network. The hypernode algorithm can be run in an iterative manner so that a hierarchy of simplified models of the network can be derived. Some case studies demonstrate the hypernode algorithm. In the first case the algorithm is compared with a similar implementation described in the literature. In the second case an airline dataset is analysed. This study shows that when networks are embedded in the geographical space hypernodes may relate to clusters in the spatial domain. The selection of the visual variables to illustrate the strength of the edges and nodes in a weighted network is discussed.  相似文献   

12.
对换网络和乘积循环网络的超连通性   总被引:1,自引:0,他引:1  
本文证明了对换网络和乘积循环网络是超连通的。  相似文献   

13.
In research and application, social networks are increasingly extracted from relationships inferred by name collocations in text-based documents. Despite the fact that names represent real entities, names are not unique identifiers and it is often unclear when two name observations correspond to the same underlying entity. One confounder stems from ambiguity, in which the same name correctly references multiple entities. Prior name disambiguation methods measured similarity between two names as a function of their respective documents. In this paper, we propose an alternative similarity metric based on the probability of walking from one ambiguous name to another in a random walk of the social network constructed from all documents. We experimentally validate our model on actor-actor relationships derived from the Internet Movie Database. Using a global similarity threshold, we demonstrate random walks achieve a significant increase in disambiguation capability in comparison to prior models. Bradley A. Malin is a Ph.D. candidate in the School of Computer Science at Carnegie Mellon University. He is an NSF IGERT fellow in the Center for Computational Analysis of Social and Organizational Systems (CASOS) and a researcher at the Laboratory for International Data Privacy. His research is interdisciplinary and combines aspects of bioinformatics, data forensics, data privacy and security, entity resolution, and public policy. He has developed learning algorithms for surveillance in distributed systems and designed formal models for the evaluation and the improvement of privacy enhancing technologies in real world environments, including healthcare and the Internet. His research on privacy in genomic databases has received several awards from the American Medical Informatics Association and has been cited in congressional briefings on health data privacy. He currently serves as managing editor of the Journal of Privacy Technology. Edoardo M. Airoldi is a Ph.D. student in the School of Computer Science at Carnegie Mellon University. Currently, he is a researcher in the CASOS group and at the Center for Automated Learning and Discovery. His methodology is based on probability theory, approximation theorems, discrete mathematics and their geometries. His research interests include data mining and machine learning techniques for temporal and relational data, data linkage and data privacy, with important applications to dynamic networks, biological sequences and large collections of texts. His research on dynamic network tomography is the state-of-the-art for recovering information about who is communicating to whom in a network, and was awarded honors from the ACM SIG-KDD community. Several companies focusing on information extraction have adopted his methodology for text analysis. He is currently investigating practical and theoretical aspects of hierarchical mixture models for temporal and relational data, and an abstract theory of data linkage. Kathleen M. Carley is a Professor of Computer Science in ISRI, School of Computer Science at Carnegie Mellon University. She received her Ph.D. from Harvard in Sociology. Her research combines cognitive science, social and dynamic networks, and computer science (particularly artificial intelligence and machine learning techniques) to address complex social and organizational problems. Her specific research areas are computational social and organization science, social adaptation and evolution, social and dynamic network analysis, and computational text analysis. Her models meld multi-agent technology with network dynamics and empirical data. Three of the large-scale tools she and the CASOS group have developed are: BioWar a city, scale model of weaponized biological attacks and response; Construct a models of the co-evolution of social and knowledge networks; and ORA a statistical toolkit for dynamic social Network data.  相似文献   

14.
Bayer  N.  Kogan  Y.A. 《Queueing Systems》1997,27(3-4):251-269
A new class of models, which combines closed queueing networks with branching processes, is introduced. The motivation comes from MIMD computers and other service systems in which the arrival of new work is always triggered by the completion of former work, and the amount of arriving work is variable. In the variant of branching/queueing networks studied here, a customer branches into a random and state-independent number of offspring upon completing its service. The process regenerates whenever the population becomes extinct. Implications for less rudimentary variants are discussed. The ergodicity of the network and several other aspects are related to the expected total number of progeny of an associated multitype Galton-Watson process. We give a formula for that expected number of progeny. The objects of main interest are the stationary state distribution and the throughputs. Closed-form solutions are available for the multi-server single-node model, and for homogeneous networks of infinite-servers. Generally, branching/queueing networks do not seem to have a product-form state distribution. We propose a conditional product-form approximation, and show that it is approached as a limit by branching/queueing networks with a slowly varying population size. The proof demonstrates an application of the nearly complete decomposability paradigm to an infinite state space. This revised version was published online in June 2006 with corrections to the Cover Date.  相似文献   

15.
Synchronization in complex dynamical networks is in the focus of network science today, where intensive efforts have been devoted to understanding its mechanisms and developing basic theories with applications. However, the sheer sizes of large-scale networks have been the main hurdle in such analysis and applications. Recently, a coarse graining scheme based on network synchronization was proposed to reduce the network size while preserving the synchronizability of the original network. In this research, we investigate the effects of the coarse graining process on synchronizability over complex clustered networks. Numerous experiments demonstrate a close correlation between the degree of clustering of the initial network and the ability of spectral coarse graining in preserving the network synchronizability. It is found that synchronizability can be well preserved after applying the spectral coarse graining if the considered network has a clear cluster structure, whereas this is not so for networks with vague clustering. Since most real-world networks have prominent cluster structures, this research provides new insights into understanding large-scale dynamical networks and analyzing their complex topological characteristics as well as synchronization mechanisms.  相似文献   

16.
Questions related to the evolution of the structure of networks have received recently a lot of attention in the literature. But what is the state of the network given its structure? For example, there is the question of how the structures of neural networks make them behave? Or, in the case of a network of humans, the question could be related to the states of humans in general, given the structure of the social network. The models based on stochastic processes developed in this article, do not attempt to capture the fine details of social or neural dynamics. Rather they aim to describe the general relationship between the variables describing the network and the aggregate behavior of the network. A number of nontrivial results are obtained using computer simulations. © 2005 Wiley Periodicals, Inc. Complexity 10: 42–50, 2005  相似文献   

17.
In this paper we consider closed tandem queueing networks with finite buffers and blocking before service. With this type of blocking, a server is allowed to start processing a job only if there is an empty space in the next buffer. It was recently conjectured that the throughput of such networks is symmetrical with respect to the population of the network. That is, the throughput of the network with population N is the same as that with population CN, where C is the total number of buffer spaces in the network. The main purpose of this paper is to prove this result in the case where the service time distributions are of phase type (PH-distribution). The proof is based on the comparison of the sample paths of the network with populations N and CN. Finally, we also show that this symmetry property is related to a reversibility property of this class of networks.  相似文献   

18.
A class of inhomogenously wired networks called “scale-free” networks have been shown to be more robust against failure than more homogenously connected exponential networks. The robustness of scale-free networks consists in their ability to remain connected even when failure occurs. The diffusion of information and disease across a network only requires a single contact between nodes, making network connectivity the crucial determinant of whether or not these “simple contagions” will spread. However, for “complex contagions,” such as social movements, collective behaviors, and cultural and social norms, multiple reinforcing ties are needed to support the spread of a behavior diffusion. I show that scale-free networks are much less robust than exponential networks for the spread of complex contagions, which highlights the value of more homogenously distributed social networks for the robust transmission of collective behavior.  相似文献   

19.
Three critical factors in wireless mesh network design are the number of hops between supply and demand points, the bandwidth capacity of the transport media, and the technique used to route packets within the network. Most previous research on network design has focused on the issue of hop constraints and/or bandwidth capacity in wired networks while assuming a per-flow routing scheme. However, networks that employ per-packet routing schemes in wireless networks involve different design issues that are unique to this type of problem. We present a methodology for designing wireless mesh networks that consider bandwidth capacity, hop constraints, and profitability for networks employing a per-packet routing system.  相似文献   

20.
Credal networks generalize Bayesian networks by relaxing the requirement of precision of probabilities. Credal networks are considerably more expressive than Bayesian networks, but this makes belief updating NP-hard even on polytrees. We develop a new efficient algorithm for approximate belief updating in credal networks. The algorithm is based on an important representation result we prove for general credal networks: that any credal network can be equivalently reformulated as a credal network with binary variables; moreover, the transformation, which is considerably more complex than in the Bayesian case, can be implemented in polynomial time. The equivalent binary credal network is then updated by L2U, a loopy approximate algorithm for binary credal networks. Overall, we generalize L2U to non-binary credal networks, obtaining a scalable algorithm for the general case, which is approximate only because of its loopy nature. The accuracy of the inferences with respect to other state-of-the-art algorithms is evaluated by extensive numerical tests.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号