Link Prediction in Complex Networks: A Mutual Information Perspective

Topological properties of networks are widely applied to study the link-prediction problem recently. Common Neighbors, for example, is a natural yet efficient framework. Many variants of Common Neighbors have been thus proposed to further boost the discriminative resolution of candidate links. In this paper, we reexamine the role of network topology in predicting missing links from the perspective of information theory, and present a practical approach based on the mutual information of network structures. It not only can improve the prediction accuracy substantially, but also experiences reasonable computing complexity.     

A Noise-Filtering Method for Link Prediction in Complex Networks

Link prediction plays an important role in both finding missing links in networked systems and complementing our understanding of the evolution of networks. Much attention from the network science community are paid to figure out how to efficiently predict the missing/future links based on the observed topology. Real-world information always contain noise, which is also the case in an observed network. This problem is rarely considered in existing methods. In this paper, we treat the existence of observed links as known information. By filtering out noises in this information, the underlying regularity of the connection information is retrieved and then used to predict missing or future links. Experiments on various empirical networks show that our method performs noticeably better than baseline algorithms.     

Link Prediction in Criminal Networks: A Tool for Criminal Intelligence Analysis

The problem of link prediction has recently received increasing attention from scholars in network science. In social network analysis, one of its aims is to recover missing links, namely connections among actors which are likely to exist but have not been reported because data are incomplete or subject to various types of uncertainty. In the field of criminal investigations, problems of incomplete information are encountered almost by definition, given the obvious anti-detection strategies set up by criminals and the limited investigative resources. In this paper, we work on a specific dataset obtained from a real investigation, and we propose a strategy to identify missing links in a criminal network on the basis of the topological analysis of the links classified as marginal, i.e. removed during the investigation procedure. The main assumption is that missing links should have opposite features with respect to marginal ones. Measures of node similarity turn out to provide the best characterization in this sense. The inspection of the judicial source documents confirms that the predicted links, in most instances, do relate actors with large likelihood of co-participation in illicit activities.     

自适应指数加权互信息配准医学图像的测度及相应算法

为配准医学图像,本文提出了一种新的自适应指数加权的互信息(Adaptive Exponential Weighted Mutual Informa- tion,AEWMI)测度,分析表明:通过对互信息(Mutual Information,MI)测度进行指数加权可以提高测度曲线的峰值尖锐性和平滑性;而指数的权值则可以通过评估待配准图像的质量和分辨率大小来自适应确定。仿真实验结果在验证分析结果的同时也表明,基于本文AEWMI测度的配准方案,对图像噪声、分辨率差异等有较高的鲁棒性,且可有效地提高配准的成功率。     

Cluster Analysis of Weighted Bipartite Networks: A New Copula-Based Approach

In this work we are interested in identifying clusters of “positional equivalent” actors, i.e. actors who play a similar role in a system. In particular, we analyze weighted bipartite networks that describes the relationships between actors on one side and features or traits on the other, together with the intensity level to which actors show their features. We develop a methodological approach that takes into account the underlying multivariate dependence among groups of actors. The idea is that positions in a network could be defined on the basis of the similar intensity levels that the actors exhibit in expressing some features, instead of just considering relationships that actors hold with each others. Moreover, we propose a new clustering procedure that exploits the potentiality of copula functions, a mathematical instrument for the modelization of the stochastic dependence structure. Our clustering algorithm can be applied both to binary and real-valued matrices. We validate it with simulations and applications to real-world data.     

WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks

In this paper, we propose an on-demand distributed clustering algorithm for multi-hop packet radio networks. These types of networks, also known as ad hoc networks, are dynamic in nature due to the mobility of nodes. The association and dissociation of nodes to and from clusters perturb the stability of the network topology, and hence a reconfiguration of the system is often unavoidable. However, it is vital to keep the topology stable as long as possible. The clusterheads, form a dominant set in the network, determine the topology and its stability. The proposed weight-based distributed clustering algorithm takes into consideration the ideal degree, transmission power, mobility, and battery power of mobile nodes. The time required to identify the clusterheads depends on the diameter of the underlying graph. We try to keep the number of nodes in a cluster around a pre-defined threshold to facilitate the optimal operation of the medium access control (MAC) protocol. The non-periodic procedure for clusterhead election is invoked on-demand, and is aimed to reduce the computation and communication costs. The clusterheads, operating in dual power mode, connects the clusters which help in routing messages from a node to any other node. We observe a trade-off between the uniformity of the load handled by the clusterheads and the connectivity of the network. Simulation experiments are conducted to evaluate the performance of our algorithm in terms of the number of clusterheads, reaffiliation frequency, and dominant set updates. Results show that our algorithm performs better than existing ones and is also tunable to different kinds of network conditions.     

Prediction of Heterodimeric Protein Complexes from Weighted Protein-Protein Interaction Networks Using Novel Features and Kernel Functions

Since many proteins express their functional activity by interacting with other proteins and forming protein complexes, it is very useful to identify sets of proteins that form complexes. For that purpose, many prediction methods for protein complexes from protein-protein interactions have been developed such as MCL, MCODE, RNSC, PCP, RRW, and NWE. These methods have dealt with only complexes with size of more than three because the methods often are based on some density of subgraphs. However, heterodimeric protein complexes that consist of two distinct proteins occupy a large part according to several comprehensive databases of known complexes. In this paper, we propose several feature space mappings from protein-protein interaction data, in which each interaction is weighted based on reliability. Furthermore, we make use of prior knowledge on protein domains to develop feature space mappings, domain composition kernel and its combination kernel with our proposed features. We perform ten-fold cross-validation computational experiments. These results suggest that our proposed kernel considerably outperforms the naive Bayes-based method, which is the best existing method for predicting heterodimeric protein complexes.     

Informal Exchange Networks in Formal Systems: A Theoretical Model

Studies of the informal economy in the Third World have evolved toward defining the informal sector in relationship to the state. This article analyzes some activities that escape the control of the state, with special attention to centrally planned economies. Informal exchanges include bureaucratic favors (connections), clientelism, different forms of corruption, and the parallel system of production and marketing. I show that economic laws are not sufficient to understand the logic of these economies.     

基于径向基函数神经网络的温室室内温度预测模型

试验证实径向基函数神经网络(Radial Basias Function Neural Network)在函数逼近能力、训练速度方面都有良好的性能．采用最小正交二乘法为训练算法,基于传统的数学分析,用PRIVA公司温室监控系统采集数据,选用当前时刻室外温度、风速、太阳辐照度、顶窗开度、内帘幕展开度、水温、室内温度、相对湿度,再加上1个时间间隔、2个时间间隔以前的室内温度作为输入向量,获得了满意的温室室内温度一步预测模型(均方差等于0．0073)．该模型为设计温室环境控制器及分析温室性能奠定了良好基础．     

CD-Based Indices for Link Prediction in Complex Network

Lots of similarity-based algorithms have been designed to deal with the problem of link prediction in the past decade. In order to improve prediction accuracy, a novel cosine similarity index CD based on distance between nodes and cosine value between vectors is proposed in this paper. Firstly, node coordinate matrix can be obtained by node distances which are different from distance matrix and row vectors of the matrix are regarded as coordinates of nodes. Then, cosine value between node coordinates is used as their similarity index. A local community density index LD is also proposed. Then, a series of CD-based indices include CD-LD-k, CD*LD-k, CD-k and CDI are presented and applied in ten real networks. Experimental results demonstrate the effectiveness of CD-based indices. The effects of network clustering coefficient and assortative coefficient on prediction accuracy of indices are analyzed. CD-LD-k and CD*LD-k can improve prediction accuracy without considering the assortative coefficient of network is negative or positive. According to analysis of relative precision of each method on each network, CD-LD-k and CD*LD-k indices have excellent average performance and robustness. CD and CD-k indices perform better on positive assortative networks than on negative assortative networks. For negative assortative networks, we improve and refine CD index, referred as CDI index, combining the advantages of CD index and evolutionary mechanism of the network model BA. Experimental results reveal that CDI index can increase prediction accuracy of CD on negative assortative networks.     

Information Networks in Amenity Transition Communities: A Comparative Case Study

Amenity transition, a major socio demographic trend in areas rich in natural resources, is characterized by economic and population growth as a result of retirement in-migration, increased rates of second home ownership, and increases in the number of industries that do not need to be proximate to a specific geographic location. Amenity transition is also characterized by increased intra-community conflict between long-term residents and in-migrants. This research analyzes whether the population growth accompanying amenity transition is associated with variations in the structure and characteristics of intra-community informational networks, as sociological theory would suggest. Methodologically, this is accomplished through a comparative analysis of the structure and characteristics of informational networks in three communities undergoing amenity transition. The analyses suggest population density is not related to either the structure of informational networks or the concentration of trust/distrust within them. When considered in conjunction with previous empirical work, these findings suggest the conflicts associated with amenity transition are more likely to arise because of conflicting value systems and ideologies as opposed to social structural changes in the communities themselves.     

FctClus: A Fast Clustering Algorithm for Heterogeneous Information Networks

It is important to cluster heterogeneous information networks. A fast clustering algorithm based on an approximate commute time embedding for heterogeneous information networks with a star network schema is proposed in this paper by utilizing the sparsity of heterogeneous information networks. First, a heterogeneous information network is transformed into multiple compatible bipartite graphs from the compatible point of view. Second, the approximate commute time embedding of each bipartite graph is computed using random mapping and a linear time solver. All of the indicator subsets in each embedding simultaneously determine the target dataset. Finally, a general model is formulated by these indicator subsets, and a fast algorithm is derived by simultaneously clustering all of the indicator subsets using the sum of the weighted distances for all indicators for an identical target object. The proposed fast algorithm, FctClus, is shown to be efficient and generalizable and exhibits high clustering accuracy and fast computation speed based on a theoretic analysis and experimental verification.     

A Universal Model of Commuting Networks

We show that a recently proposed model generates accurate commuting networks on 80 case studies from different regions of the world (Europe and United-States) at different scales (e.g. municipalities, counties, regions). The model takes as input the number of commuters coming in and out of each geographic unit and generates the matrix of commuting flows between the units. The single parameter of the model follows a universal law that depends only on the scale of the geographic units. We show that our model significantly outperforms two other approaches proposing a universal commuting model [1], [2], particularly when the geographic units are small (e.g. municipalities).     

A Null Model for Pearson Coexpression Networks

Gene coexpression networks inferred by correlation from high-throughput profiling such as microarray data represent simple but effective structures for discovering and interpreting linear gene relationships. In recent years, several approaches have been proposed to tackle the problem of deciding when the resulting correlation values are statistically significant. This is most crucial when the number of samples is small, yielding a non-negligible chance that even high correlation values are due to random effects. Here we introduce a novel hard thresholding solution based on the assumption that a coexpression network inferred by randomly generated data is expected to be empty. The threshold is theoretically derived by means of an analytic approach and, as a deterministic independent null model, it depends only on the dimensions of the starting data matrix, with assumptions on the skewness of the data distribution compatible with the structure of gene expression levels data. We show, on synthetic and array datasets, that the proposed threshold is effective in eliminating all false positive links, with an offsetting cost in terms of false negative detected edges.     

Prediction of Cascading Failures in Spatial Networks

Cascading overload failures are widely found in large-scale parallel systems and remain a major threat to system reliability; therefore, they are of great concern to maintainers and managers of different systems. Accurate cascading failure prediction can provide useful information to help control networks. However, for a large, gradually growing network with increasing complexity, it is often impractical to explore the behavior of a single node from the perspective of failure propagation. Fortunately, overload failures that propagate through a network exhibit certain spatial-temporal correlations, which allows the study of a group of nodes that share common spatial and temporal characteristics. Therefore, in this study, we seek to predict the failure rates of nodes in a given group using machine-learning methods.We simulated overload failure propagations in a weighted lattice network that start with a center attack and predicted the failure percentages of different groups of nodes that are separated by a given distance. The experimental results of a feedforward neural network (FNN), a recurrent neural network (RNN) and support vector regression (SVR) all show that these different models can accurately predict the similar behavior of nodes in a given group during cascading overload propagation.     

Oscillations in Large-Scale Cortical Networks: Map-Based Model

We develop a new computationally efficient approach for the analysis of complex large-scale neurobiological networks. Its key element is the use of a new phenomenological model of a neuron capable of replicating important spike pattern characteristics and designed in the form of a system of difference equations (a map). We developed a set of map-based models that replicate spiking activity of cortical fast spiking, regular spiking and intrinsically bursting neurons. Interconnected with synaptic currents these model neurons demonstrated responses very similar to those found with Hodgkin-Huxley models and in experiments. We illustrate the efficacy of this approach in simulations of one- and two-dimensional cortical network models consisting of regular spiking neurons and fast spiking interneurons to model sleep and activated states of the thalamocortical system. Our study suggests that map-based models can be widely used for large-scale simulations and that such models are especially useful for tasks where the modeling of specific firing patterns of different cell classes is important.     

Information Recovery in Behavioral Networks

In the context of agent based modeling and network theory, we focus on the problem of recovering behavior-related choice information from origin-destination type data, a topic also known under the name of network tomography. As a basis for predicting agents'' choices we emphasize the connection between adaptive intelligent behavior, causal entropy maximization, and self-organized behavior in an open dynamic system. We cast this problem in the form of binary and weighted networks and suggest information theoretic entropy-driven methods to recover estimates of the unknown behavioral flow parameters. Our objective is to recover the unknown behavioral values across the ensemble analytically, without explicitly sampling the configuration space. In order to do so, we consider the Cressie-Read family of entropic functionals, enlarging the set of estimators commonly employed to make optimal use of the available information. More specifically, we explicitly work out two cases of particular interest: Shannon functional and the likelihood functional. We then employ them for the analysis of both univariate and bivariate data sets, comparing their accuracy in reproducing the observed trends.