Recursive filtration method for detecting community structure in networks

Community detection is a topic of considerable recent interest within complex networks, but most methods proposed so far are divisive and agglomerative methods which delete only one edge each time to split the network, or agglomerating only one node each time until no individual node remains. Unlike those, we propose a method to split networks in parallel by deleting many edges in each filtration operation, and propose a community recursive coefficient (CRC) denoted by M instead of Q (modularity) to quantify the effect of the splitting results in this paper. We proved that recursive optimizing of the local M is equivalent to acquiring the maximal global Q value corresponding to good divisions. For a network with m edges, c communities and arbitrary topology, the method split the network at most c+1 times and detected the community structure in time O(m²+(c+1)m). We give several example applications, and show that the method can detect local communities according to the densities of external links to them in increasing order especially in large networks.     

Preferential survival in models of complex ad hoc networks

There has been a rich interplay in recent years between (i) empirical investigations of real-world dynamic networks, (ii) analytical modeling of the microscopic mechanisms that drive the emergence of such networks, and (iii) harnessing of these mechanisms to either manipulate existing networks, or engineer new networks for specific tasks. We continue in this vein, and study the deletion phenomenon in the web by the following two different sets of websites (each comprising more than 150,000 pages) over a one-year period. Empirical data show that there is a significant deletion component in the underlying web networks, but the deletion process is not uniform. This motivates us to introduce a new mechanism of preferential survival (PS), where nodes are removed according to the degree-dependent deletion kernel, D(k)∝k^−α, with α≥0. We use the mean-field rate equation approach to study a general dynamic model driven by Preferential Attachment (PA), Double PA (DPA), and a tunable PS (i.e., with any α>0), where c nodes (c<1) are deleted per node added to the network, and verify our predictions via large-scale simulations. One of our results shows that, unlike in the case of uniform deletion (i.e., where α=0), the PS kernel when coupled with the standard PA mechanism, can lead to heavy-tailed power-law networks even in the presence of extreme turnover in the network. Moreover, a weak DPA mechanism, coupled with PS, can help to make the network even more heavy-tailed, especially in the limit when deletion and insertion rates are almost equal, and the overall network growth is minimal. The dynamics reported in this work can be used to design and engineer stable ad hoc networks and explain the stability of the power-law exponents observed in real-world networks.     

Transport Properties of Random Walks on Scale-Free/Regular-Lattice Hybrid Networks

We study numerically the mean access times for random walks on hybrid disordered structures formed by embedding scale-free networks into regular lattices, considering different transition rates for steps across lattice bonds (F) and across network shortcuts (f). For fast shortcuts (f/F≫1) and low shortcut densities, traversal time data collapse onto a universal curve, while a crossover behavior that can be related to the percolation threshold of the scale-free network component is identified at higher shortcut densities, in analogy to similar observations reported recently in Newman-Watts small-world networks. Furthermore, we observe that random walk traversal times are larger for networks with a higher degree of inhomogeneity in their shortcut distribution, and we discuss access time distributions as functions of the initial and final node degrees. These findings are relevant, in particular, when considering the optimization of existing information networks by the addition of a small number of fast shortcut connections.     

加权网络权重自相似评判函数及其社团结构检测

提出了权重自相似性加权网络社团结构评判函数,并基于该函数提出一种谱分析算法检测社团结构,结果表明算法能将加权网络划分为同一社团内边权值分布均匀,而社团间边权值分布随机的社团结构.通过建立具有社团结构的加权随机网络分析了该算法的准确性,与WEO和WGN算法相比,在评判权重自相似的阈值系数取较小时,该算法具有较高的准确性.对于一个具有n个节点和c个社团的加权网络,社团结构检测的复杂度为O(cn2/2).通过设置评判权重自相似的阈值系数,可检测出能反映节点联系稳定性的层化性社团结构.这与传统意义上只将加权网络划分为社团中边权值较大而社团间边权值较小的标准不同,从另一个角度更好地提取了加权网络的结构信息.     

Percolation on bipartite scale-free networks

Recent studies introduced biased (degree-dependent) edge percolation as a model for failures in real-life systems. In this work, such process is applied to networks consisting of two types of nodes with edges running only between nodes of unlike type. Such bipartite graphs appear in many social networks, for instance in affiliation networks and in sexual-contact networks in which both types of nodes show the scale-free characteristic for the degree distribution. During the depreciation process, an edge between nodes with degrees k and q is retained with a probability proportional to (kq)^−α, where α is positive so that links between hubs are more prone to failure. The removal process is studied analytically by introducing a generating functions theory. We deduce exact self-consistent equations describing the system at a macroscopic level and discuss the percolation transition. Critical exponents are obtained by exploiting the Fortuin-Kasteleyn construction which provides a link between our model and a limit of the Potts model.     

Impact of initial lattice structures on networks generated by traces of random walks

We show that the platform stage of network evolution plays a principal role in the topology of resulting networks generated by short-cuts stimulated by the movements of a random walker, the mechanism of which tends to produce power-law degree distributions. To examine the numerical results, we have developed a statistical method which relates the power-law exponent γ to random properties of the subgraph developed in the platform stage. As a result, we find that an important exponent in the network evolution is α, which characterizes the size of the subgraph in the form V∼t^α, where V and t denote the number of vertices in the subgraph and the time variable, respectively. 2D lattices can impose specific limitations on the walker’s diffusion, which keeps the value of α within a moderate range and provides typical properties of complex networks. 1D and 3D cases correspond to different ends of the spectrum for α, with 2D cases in between. Especially for 2D square lattices, a discontinuous change of the network structure is observed, which varies according to whether γ is greater or less than 2. For 1D cases, we show that emergence of nearly complete subgraphs is guaranteed by α<1/2, although the transient power-law is permitted at low increase rates of edges. Additionally, the model exhibits a spontaneous emergence of highly clustered structures regardless of its initial structure.     

Adjacency networks

We consider a finite set S={x₁,…,x_r} and associate to each element x_i a probability p_i. We then form sequences (N-strings) by drawing at random N elements from S with respect to the probabilities assigned to them. Each N-string generates a network where the elements of S are represented as vertices and edges are drawn between adjacent vertices. These structures are multigraphs having multiple edges and loops. We show that the degree distributions of these networks are invariant under permutations of the generating N-strings. We describe then a constructive method to generate scale-free networks and we show how scale-free topologies naturally emerge when the probabilities are Zipf distributed.     

Evolutionary prisoner’s dilemma game on weighted scale-free networks

This paper investigates the evolutionary prisoner’s dilemma on weighted scale-free networks. The weighted networks are generated by adopting Barabási-Albert scale-free network and assigning link weight with w_ij=(k_i×k_j)^β. Simulation results show that the cooperation frequency has a strong dependence on β. The value of β which is associated with the maximal cooperation frequency has been sought out. Moreover, Gini coefficient and Pareto exponent of the system’s wealth distribution are investigated. The inequality of wealth distribution is minimized at β≈−1.     

Exact solution of the 1D Hubbard model with NN and NNN interactions in the narrow-band limit

In this paper, we propose a family of weighted extended Koch networks based on a class of extended Koch networks. They originate from a r-complete graph, and each node in each r-complete graph of current generation produces mr-complete graphs whose weighted edges are scaled by factor h in subsequent evolutionary step. We study the structural properties of these networks and random walks on them. In more detail, we calculate exactly the average weighted shortest path length (AWSP), average receiving time (ART) and average sending time (AST). Besides, the technique of resistor network is employed to uncover the relationship between ART and AST on networks with unit weight. In the infinite network order limit, the average weighted shortest path lengths stay bounded with growing network order (0 < h < 1). The closed form expression of ART shows that it exhibits a sub-linear dependence (0 < h < 1) or linear dependence (h = 1) on network order. On the contrary, the AST behaves super-linearly with the network order. Collectively, all the obtained results show that the efficiency of message transportation on weighted extended Koch networks has close relation to the network parameters h, m and r. All these findings could shed light on the structure and random walks of general weighted networks.     

Scaling relation for earthquake networks

The scaling relation, 2γ−δ=1, for the exponents of the power-law connectivity distribution, γ, and the power-law eigenvalue distribution of the adjacency matrix, δ, is theoretically predicted to be fulfilled by a locally treelike scale-free network in the “effective medium approximation” (i.e., an analog of the mean field approximation). Here, it is shown that such a relation holds well for the reduced simple earthquake networks (i.e., the network without tadpole-loops and multiple edges) constructed from the seismic data taken from California and Japan. This validates the goodness of the effective medium approximation in the earthquake networks and is consistent with the hierarchical organization of the networks. The present result may be useful for modeling seismicity on complex networks.     

Pruned optical banyan networks on vertical stacking scheme for faster connection establishment

In this paper, we address the issue of faster connection establishment in a large vertically stacked optical Banyan (VSOB) network. The best known global routing algorithm, which turns an N × N crosstalk-free VSOB network into a rearrangeably non-blocking one, has time complexity O (NlogN). This is quite large compared to O (NlogN) time complexity of a single plane banyan network, which is a self-routing network with very high blocking probability. For a large size of switching network this O (NlogN) time complexity may result unacceptably long delay. Therefore, an optical network with very low blocking probability and O (NlogN) time complexity will be useful. Previously proposed Plane Fixed Routing (PFR) algorithm has O (logN) time complexity but results in higher than 2% blocking probability with zero-crosstalk constraint for a network as large as 4096 × 4096 at full load. In this paper, first we propose the pruning of VSOB networks that reduces the hardware cost by almost 30%. The networks can still use the PFR algorithm and results in the same blocking probability. However, we show that the blocking probability can be reduced dramatically while keeping the optimum time complexity O (logN) by allowing only a small amount of crosstalk. Then, we propose a new kind of switching networks in which extra regular banyan planes have been added with the pruned VBOS (P-VSOB) networks. Necessary routing algorithms, namely, PFR_RS and PFR_LS show that this new switching network can reduce the blocking probability to very low value even with zero-crosstalk constraint while keeping the hardware cost 3almost the same as for P-VSOB networks. Both these algorithms also have time complexity O (NlogN).     

Temporal networks

A great variety of systems in nature, society and technology–from the web of sexual contacts to the Internet, from the nervous system to power grids–can be modeled as graphs of vertices coupled by edges. The network structure, describing how the graph is wired, helps us understand, predict and optimize the behavior of dynamical systems. In many cases, however, the edges are not continuously active. As an example, in networks of communication via e-mail, text messages, or phone calls, edges represent sequences of instantaneous or practically instantaneous contacts. In some cases, edges are active for non-negligible periods of time: e.g., the proximity patterns of inpatients at hospitals can be represented by a graph where an edge between two individuals is on throughout the time they are at the same ward. Like network topology, the temporal structure of edge activations can affect dynamics of systems interacting through the network, from disease contagion on the network of patients to information diffusion over an e-mail network. In this review, we present the emergent field of temporal networks, and discuss methods for analyzing topological and temporal structure and models for elucidating their relation to the behavior of dynamical systems. In the light of traditional network theory, one can see this framework as moving the information of when things happen from the dynamical system on the network, to the network itself. Since fundamental properties, such as the transitivity of edges, do not necessarily hold in temporal networks, many of these methods need to be quite different from those for static networks. The study of temporal networks is very interdisciplinary in nature. Reflecting this, even the object of study has many names—temporal graphs, evolving graphs, time-varying graphs, time-aggregated graphs, time-stamped graphs, dynamic networks, dynamic graphs, dynamical graphs, and so on. This review covers different fields where temporal graphs are considered, but does not attempt to unify related terminology—rather, we want to make papers readable across disciplines.     

Field-trial evaluation of the Q-factor penalty introduced by fiber four-wave mixing wavelength converters

The performance of tunable all-optical wavelength converters based on four-wave mixing in optical fibers is experimentally tested in a field-trial network. Two converters were built with two different fibers. The first one was made with a small variation in the zero-dispersion wavelength (ZDW) dispersion shifted fiber and the second one with a highly nonlinear fiber that presents great ZDW variations. In order to compare the tuning ranges obtained in both cases we present an experimental spectral analysis. Numerical simulations that consider the influence of both the dispersion slope and the long-scale ZDW variations of the fiber complement the experiments. The tuning bandwidth was larger in the highly nonlinear fiber case. For a set of different optical signal-to-noise ratios, the measurements of the Q-factor of the signal and those of the converted wave are our main results. These results show that the penalty imposed by the converters is different for each converted wavelength. The maximum penalty obtained for the Q-factor was ∼6 dB, but it was ?3 dB for most cases. In all experiments we used a technique based on a dynamic polarization controller in order to avoid power fluctuations in the converted wave caused by polarization induced variations in the signal.     

一种基于文本互信息的金融复杂网络模型

复杂网络能够解决许多金融问题,能够发现金融市场的拓扑结构特征,反映不同金融主体之间的相互依赖关系.相关性度量在金融复杂网络构建中至关重要.通过将多元金融时间序列符号化,借鉴文本特征提取以及信息论的方法,定义了一种基于文本互信息的相关系数.为检验方法的有效性,分别构建了基于不同相关系数(Pearson和文本互信息)和不同网络缩减方法(阈值和最小生成树)的4个金融复杂网络模型.在阈值网络中提出了使用分位数来确定阈值的方法,将相关系数6等分,取第4部分的中点作为阈值,此时基于Pearson和文本互信息的阈值模型将会有相近的边数,有利于这两种模型的对比.数据使用了沪深两地证券市场地区指数收盘价,时间从2006年1月4日至2016年12月30日,共计2673个交易日.从网络节点相关性看,基于文本互信息的方法能够体现出大约20%的非线性相关关系;在网络整体拓扑指标上,本文计算了4种指标,结果显示能够使所保留的节点联系更为紧密,有效提高保留节点的重要性以及挖掘出更好的社区结构;最后,计算了阈值网络的动态指标,将数据按年分别构建网络,缩减方法只用了阈值方法,结果显示本文提出的方法在小世界动态和网络度中心性等指标上能够成功捕捉到样本区间内存在的两次异常波动.此外,本文构建的地区金融网络具有服从幂律分布、动态稳定性、一些经济欠发达地区在金融地区网络中占据重要地位等特性.     

Magnetic properties of nanographite with modified zigzag edges

Newly proposed aromatic molecules and graphene fragments are shown to have the high-spin ground state by the first-principles electronic structure calculations. Our strategy to predict magnetic carbon materials is based on our previous conclusion that mono-hydrogenated, di-hydrogenated or mono-fluorinated zigzag edges of honeycomb networks are magnetic. Structural optimization as well as determination of the electronic states was performed for various nanographite ribbons and high-spin molecules, e.g. 1,8,9-di-hydro-anthracene, C₁₉H₁₄ and C₁₄F₁₃. For hydrogenated molecules and ribbons, the total spin S determined by the LSDA calculation coincides with the value expected from a counting rule for the total spin on a bipartite network. However, S depends on structures of fluorinated nanographite.     

Synchronization of networks

We study the synchronization of coupled dynamical systems on networks. The dynamics is governed by a local nonlinear oscillator for each node of the network and interactions connecting different nodes via the links of the network. We consider existence and stability conditions for both single- and multi-cluster synchronization. For networks with time-varying topology we compare the synchronization properties of these networks with the corresponding time-average network. We find that if the different coupling matrices corresponding to the time-varying networks commute with each other then the stability of the synchronized state for both the time-varying and the time-average topologies are approximately the same. On the other hand, for non-commuting coupling matrices the stability of the synchronized state for the time-varying topology is in general better than the time-average topology.      

The role of degree-weighted couplings in the synchronous onset of Kuramoto oscillator networks

This paper investigates the role of asymmetrical degree-dependent weighted couplings in synchronization of a network of Kuramoto oscillators, where the conditions of coupling criticality for the onset of phase synchronization in degree-weighted complex networks are arrived at. The numerical simulations visualize that for networks having power-law or exponential degree distributions, asymmetrical degree-weighted couplings (with increasing weighting exponent β) increases the critical coupling to achieve the onset of phase synchronization in the networks.     

Blocking probability analysis of pruned optical banyan networks on vertical stacking scheme with extra banyan planes

Vertically stacked pruned optical banyan networks with extra planes (in short, EP-VSOB networks) have lower switch count and optimal time complexity (O(log₂ N)) for routing N input requests. However, blocking probability is relatively higher than that of a VSOB networks using regular banyan planes. In the EP-VSOB architecture, the number of pruned planes has always been considered as , and a few extra planes (regular banyan) have been added with these pruned planes. In this paper we present the results of blocking analysis of a more generalized architecture in which the number of pruned planes can be 2^x, where x ? 0 in addition to the variable extra planes. This generalization helps us make a compromise between different constraints and performance metrics. Our simulation results show that for some given performance requirements (e.g. cost, speed or blocking probability) we can choose a network that has lower switch count compared to -plane pruned crosstalk-free optical banyan networks. For example, to ensure blocking probability <0.02, previously we would chose a pruned network of 32 pruned planes and 1 extra planes (a regular banyan); however, our simulations results show that a network of 16 pruned planes and 2 extra planes is enough to ensure the same performance. It is notable that, the hardware cost decreases by 28.65% in this new combination of pruned and extra planes. We believe our results will provide more flexibility in choosing a particular EP-VSOB network satisfying given requirements.     

Network topology and correlation features affiliated with European airline companies

The physics information of four specific airline flight networks in European Continent, namely the Austrian airline, the British airline, the France-Holland airline and the Lufthhansa airline, was quantitatively analyzed by the concepts of a complex network. It displays some features of small-world networks, namely a large clustering coefficient and small average shortest-path length for these specific airline networks. The degree distributions for the small degree branch reveal power law behavior with an exponent value of 2-3 for the Austrian and the British flight networks, and that of 1-2 for the France-Holland and the Lufthhansa airline flight networks. So the studied four airlines are sorted into two classes according to the topology structure. Similarly, the flight weight distributions show two kinds of different decay behavior with the flight weight: one for the Austrian and the British airlines and another for the France-Holland airline and the Lufthhansa airlines. In addition, the degree-degree correlation analysis shows that the network has disassortative behavior for all the value of degree k, and this phenomenon is different from the international airline network and US airline network. Analysis of the clustering coefficient (C(k)) versus k, indicates that the flight networks of the Austrian Airline and the British Airline reveal a hierarchical organization for all airports, however, the France-Holland Airline and the Lufthhansa Airline show a hierarchical organization mostly for larger airports. The correlation of node strength (S(k)) and degree is also analyzed, and a power-law fit S(k)∼k^1.1 can roughly fit all data of these four airline companies. Furthermore, we mention seasonal changes and holidays may cause the flight network to form a different topology. An example of the Austrian Airline during Christmas was studied and analyzed.     

Choice of Efficient Linear Scale and Generalized Description of Internal Heat Transfer Coefficient in Porous Structures

The expedience of using the ratio of inertial β and viscous α hydraulic coefficients of a fluid flow in porous structures as the characteristic linear scale, when generalizing the experimental data on internal heat transfer in porous media, is shown. It is demonstrated that the correlation Nu = A · Pe, with both criteria based on β/α ratio, most efficiently describes the experimental data for a wide set of ordered and disordered porous structures, including sintered spheres, network materials, sintered felt and cellular foams of high porosity. The coefficient A depends on porosity and is equal to 0.004 for spheres, networks and felts, and 0.0004 for foams. For any specific case the values of α and β coefficients can be readily obtained from testing materials under consideration, control samples, or full-scale articles.