This paper proposes a classifier for predicting the location of followers of a Twitter influencer using their account creation times. Time is a universal feature and thus it can be used to characterize influencers from different parts of the world. In addition, the language of the location is used to improve classification performance. In the first step of the proposed two-step approach influencer's followers' account creation times are used to create a time distribution to predict the time zone's Coordinated Universal Time (UTC) offset. In the second step, language features are used to constrain locations associated with the UTC offset. The approach is illustrated by categorizing 320K Twitter celebrity influencers by their country. High confidence influencer predictions are used as training data for an improved geocoder. This geocoder automatically learns popular ways that Twitter users refer to locations within the country and can handle foreign alphabets.

The smart grid interconnects a power grid (network) and a communication network, and enables bi-directional flow of electricity and information. To prevent the cascading failures which occur when the disruptions in one network cause disruptions in the other network, robustness should be enhanced by increasing the number of links (edges) between the power grid and the information flow network. Given a budget which constrains the number of new links that can be added to `strengthen' the network, the best strategy to determine where to add those new links remains an open research problem. This paper presents a multi-objective approach to identify the best locations in the power network where new links can be added, to improve the overall robustness of the smart grid when constrained by resource limitations. Simulation results show that substantially greater robustness is obtained by using this approach, when compared to other link addition algorithms.

In social networks that change with time, an important problem is the prediction of new links that may be formed in the future. Existing works on link prediction have focused only on networks where links are permanent, an assumption that is not valid in many real world social networks. In many real world networks, in addition to new links being created, existing links also get removed. In this paper, we extend existing link prediction methods and apply a supervised learning algorithm to networks with non-permanent links. The results we obtain on Twitter @-mention networks show that our method performs very well in such networks.

A rising star is an individual who shows the potential to become a star in the near future. We investigate the problem of finding rising stars when heterogeneous data sources are available to define the same person. The proposed solution examines multiple data sources to determine how the importance of an individual improves over time. Scores from different data sources are combined using a multi-objective optimization approach, as well as a rank aggregation approach. Compared with existing methods, our approach identifies rising stars with higher h-index, number of papers and citation count in the academic domain. Further, we show that the new approach can also be applied to other data sources such as the Information Security Stack Exchange question answer forum.

Identification of a set of key players in a given social network is of interest in many disciplines such as sociology, politics, finance, and economics. Each of the current algorithms for this task addresses a single objective, but does not perform well from the perspective of other objectives. In real life applications, we need a set of key players which can perform well with respect to multiple objectives of interest. In this paper, we propose a new perspective for key player identification, based on optimizing multiple objectives of interest, and illustrate its applicability. In addition we propose an algorithm to select the most suitable sets of key players when the user can identify a subset of objectives as important. We apply these algorithms to the Eventual Influence Limitation problem and show that our multi-objective approach outperforms previous approaches.

In recent years, with the advent of fast sequencing technology, the genomic database is growing rapidly. Researchers in the bioinformatics field are expecting faster and more accurate tools to effectively analyze the gigantic data sets. In the context of aptamer search, the goal is to search for the over-represented DNA sequences from the randomly generated aptamer libraries. Hash functions are widely used in substring comparison, sequence alignment and clustering tools. We have developed a light-weight tool that takes advantage of the hash functions to reduce the size of genomic data and conducts η-neighbor searches on the centroid sequence. This greatly improves the efficiency of the search compared with existing tools. Furthermore, the prior calculation of hash values of η-neighbors decreases the searching overhead. In a dataset of 2.23 million sequences, the proposed algorithm accurately count the frequency of the Human α-Thrombin aptamer sequences in less than 40 seconds, whereas the current script-based method takes 2 hours and 18 minutes.

In most social networks that are observed over time, we find that some individuals leave and others join the network. It is often important to modify the connections in the resulting network to satisfy desired properties associated with the network as well as individual nodes. We formulate this as a multi-objective optimization problem that requires maximization of two measures: the network Information Flow Quality (IFQ) and the Personal Satisfaction Quality(PSQ). Algorithms are developed to accomplish these optimization tasks, and shown to result in satisfactory network reconfiguration.

Gene regulatory networks (GRNs) describe epistatic relationship of genes and how the expression of some genes influence the expression of other genes. This information is critical for understanding molecular mechanisms regulating various biological processes and molecular basis of several diseases. Current research work mostly attempts to infer such regulatory relationships (and GRN architecture topology) from gene expression data. This paper improves on this methodology by utilizing additional information available that describes which cis-elements are present in which genes, and at what locations. Using the underlying principle that target genes of a transcription factor should share the same binding site in their promoter regions, we propose a scoring method that facilitates the refinement of a candidate GRN. Improvements are demonstrated with three data sets, on which GRNs are first obtained from existing dataset (AtRegNet) or using an existing approach (ARACNe), and then modified using cis-element information.

The mainstream approach for community detection focuses on the optimization of a metric that measures the quality of a partition over a given network. Optimizing a global metric is akin to community assignment by a centralized decision maker. In liu of global optimization, we treat each node as a player in a hedonic game and focus on their ability to form fair and stable community structures. Application on real-world networks and a well-known benchmark demonstrates that our approach produces better results than modularity optimization.

Abstract Wireless sensor networks can be employed to provide distributed real‐time navigation instructions to users attempting to travel in hazardous environments. In this work, we propose a distributed path planning algorithm for sensor network navigation in dynamic hazardous environments. Using geographic or virtual coordinates of sensors and based on a partial reversal method for directed acyclic graphs (DAG), our algorithm constructs a distributed in‐network directed navigation graph, where each source sensor is guaranteed to have at least one desired directed path to one destination sensor. When the hazardous environment changes due to its dynamic nature, path replanning does not need to reconfigure most of the directed links in the graph unaffected by the changes. Correctness of our algorithm is proved and extensive simulation results demonstrate that the constructed navigation graph provides near‐optimal navigation paths for users, successfully adapts to dynamic hazardous environments, and requires very low communication overhead for maintenance, when compared to other navigation graphs constructed by existing algorithms that use frequent or periodic flooding. Copyright © 2010 John Wiley & Sons, Ltd.

Detecting community structure in complex networks is an active area of research that locates dense regions of connections in networks. We suggest a novel algorithm for community detection using a new node-node association metric (based on Markov chains) and a team formation model.

We propose a set of distributed algorithms for in-network path planning that enables a distributed sensor network navigation service in dynamic environments. Different from existing algorithms that use frequent or periodic flooding, our algorithms exploit geographic information of sensors to construct and maintain navigation links. Based on a partial reversal method of directed acyclic graphs, our algorithms ensure that each source sensor has at least one safe navigation path to one of the multiple destination sensors.

A new algorithm, HAMMER, discovers cis-elements in promoter regions of the co-regulated genes. We show that HAMMER is faster and more accurate than well-known tools currently in use to identify cis-elements. Given input sequences that represent promoter regions of genes, this algorithm searches for subsequences of desired length w whose frequency of occurrence is relatively high, while accounting for slightly corrupted variants (with up to d substitutions). Various w-mers are numerically encoded and represented in a hash table, and d-neighbors are efficiently discovered using a modulo-4 arithmetic operation. Profile matrices are constructed and evaluated using a high-order Markov model based on background data (from a gene database). HAMMER discovers the most frequently occurring w-mers (permitting corruption in at most d positions). Experiment results show that HAMMER is significantly faster and discovers more motifs present in the test sequences, when compared with two well-known motif-discovery tools (MDScan and AlignACE).

This paper considers the problem tracking a moving target in a multisensor environment using distributed particle filters (DPFs). Particle filters have a great potential for solving highly nonlinear and non-Gaussian estimation problems, in which the traditional Kalman filter (KF) and extended Kalman filter (EKF) generally fail. How ever, in a sensor network, the implementation of distributed particle filters requires huge communications between local sensor nodes and the fusion center. To make the DPF approach feasible for real time processing and to reduce communication requirements, we approximate a posteriori distribution obtained from the local particle filters by a Gaussian mixture model (GMM). We propose a modified EM algorithm to estimate the parameters of GMMs obtained locally. These parameters are transmitted to the fusion center where the best linear unbiased estimator (BLUE) is used for fusion. Simulation results are presented to illustrate the performance of the proposed algorithm

An approach for data fusion in wireless sensor networks involves the use of mobile agents that selectively visit the sensors and incrementally fuse the data, thereby eliminating the unnecessary transmission of irrelevant or non-critical data. The order of sensors visited along the route determines the quality of the fused data and the communication cost. We model the mobile agent routing problem as a multi-objective optimization problem, maximizing the total detected signal energy while minimizing the energy consumption and path loss. Simulation results show that this problem can be solved successfully using evolutionary multi-objective algorithms such as EMOCA and NSGA-II. This approach also enables choosing between two alternative routing algorithms, to determine which one results in higher detection accuracy.

The problem of distributed sequential detection in the presence of communication constraints is considered. The observations available at each sensor are first compressed to multibit sensor decisions and sent to the fusion center. At the fusion center, a sequential data fusion scheme is implemented in order to reach a global decision. An algorithm is developed for optimal bandwidth distribution among sensors under a fixed bandwidth constraint. Under symmetry and conditional independence assumptions, the algorithm can be simplified substantially: the cooperative quantizer design algorithm reduces to independent quantizer design. The case when communication bandwidth is the only constraint is also considered.

We have developed a tool that facilitates dynamically updating beliefs with time. This tool addresses directed probabilistic inference networks that may contain cycles, and takes into account the time delays associated with observations and decisions. Relevance of different observers may decay at different rates in the same application, and the belief in a hypothesis decays towards the associated prior probability. Simple models with few parameters have been implemented, with a user interface that facilitates changes to the structure and parameters of the graphical model, and associated conditional probabilities.

Problem-specific knowledge is often implemented in search algorithms using heuristics to determine which search paths are to be explored at any given instant. As in other search methods, utilizing this knowledge will more quickly lead a genetic algorithm (GA) towards better results. In many problems, crucial knowledge is not found in individual components, but in the interrelations between those components. For such problems, we develop an interrelation (linkage) based crossover operator that has the advantage of liberating GAs from the constraints imposed by the fixed representations generally chosen for problems. The strength of linkages between components of a chromosomal structure can be explicitly represented in a linkage matrix and used in the reproduction step to generate new individuals. For some problems, such a linkage matrix is known a priori from the nature of the problem. In other cases, the linkage matrix may be learned by successive minor adaptations during the execution of the evolutionary algorithm. This paper demonstrates the success of such an approach for several problems.

An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen (1993). We prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10/sup -3/ by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.

We study two classes of sigmoids: the simple sigmoids, defined to be odd, asymptotically bounded, completely monotone functions in one variable, and the hyperbolic sigmoids, a proper subset of simple sigmoids and a natural generalization of the hyperbolic tangent. We obtain a complete characterization for the inverses of hyperbolic sigmoids using Euler's incomplete beta functions, and describe composition rules that illustrate how such functions may be synthesized from others. These results are applied to two problems. First we show that with respect to simple sigmoids the continuous Cohen-Grossberg-Hopfield model can be reduced to the (associated) Legendre differential equations. Second, we show that the effect of using simple sigmoids as node transfer functions in a one-hidden layer feedforward network with one summing output may be interpreted as representing the output function as a Fourier series sine transform evaluated at the hidden layer node inputs, thus extending and complementing earlier results in this area. Copyright 1996 Elsevier Science Ltd

The rate of convergence of net output error is very low when training feedforward neural networks for multiclass problems using the backpropagation algorithm. While backpropagation will reduce the Euclidean distance between the actual and desired output vectors, the differences between some of the components of these vectors increase in the first iteration. Furthermore, the magnitudes of subsequent weight changes in each iteration are very small, so that many iterations are required to compensate for the increased error in some components in the initial iterations. Our approach is to use a modular network architecture, reducing a K-class problem to a set of K two-class problems, with a separately trained network for each of the simpler problems. Speedups of one order of magnitude have been obtained experimentally, and in some cases convergence was possible using the modular approach but not using a nonmodular network.

Partitioning graphs into equally large groups of nodes, minimizing the number of edges between different groups, is an extremely important problem in parallel computing. This paper presents genetic algorithms for suboptimal graph partitioning, with new crossover operators (KNUX, DKNUX) that lead to orders of magnitude improvement over traditional genetic operators in solution quality and speed. Our method can improve on good solutions previously obtained by using other algorithms or graph theoretic heuristics in, minimizing the total communication cost or the worst case cost of communication for a single processor. We also extend our algorithm to incremental graph partitioning problems, in which the graph structure or system properties changes with time.>

Abstract The paper presents a new approach that uses neural networks to predict the performance of a number of dynamic decentralized load‐balancing strategies. A distributed multicomputer system using distributed load‐balancing strategies is represented by a unified analytical queuing model. A large simulation data set is used to train a neural network using the back‐propagation learning algorithm based on gradient descent The performance model using the predicted data from the neural network produces the average response time of various load balancing algorithms under various system parameters. The validation and comparison with simulation data show that the neural network is very effective in predicting the performance of dynamic load‐balancing algorithms. Our work leads to interesting techniques for designing load balancing schemes (for large distributed systems) that are computationally very expensive to simulate. One of the important findings is that performance is affected least by the number of nodes, and most by the number of links at each node in a large distributed system.

Soft-decision decoding is an NP-hard problem of great interest to developers of communication systems. We show that this problem is equivalent to the problem of optimizing Walsh polynomials. We present genetic algorithms for soft-decision decoding of binary linear block codes and compare the performance with various other decoding algorithms including the currently developed A* algorithm. Simulation results show that our algorithms achieve bit-error-probabilities as low as 0.00183 for a [104,52] code with a low signal-to-noise ratio of 2.5 dB, exploring only 22,400 codewords, whereas the search space contains 4.5 × 10l5 codewords. We define a new crossover operator that exploits domain-specific information and compare it with uniform and two-point crossover.

The problem of analyzing images containing multiple sparse overlapped patterns is addressed. This problem arises naturally when analyzing the composition of organic macromolecules using data gathered from their NMR spectra. Using a neural network approach, excellent results are obtained in using NMR data to analyze the presence of various amino acids in protein molecules. High correct classification percentages (about 87%) are achieved for images containing as many as five substantially distorted overlapping patterns.

The backpropagation algorithm converges very slowly for two-class problems in which most of the exemplars belong to one dominant class. An analysis shows that this occurs because the computed net error gradient vector is dominated by the bigger class so much that the net error for the exemplars in the smaller class increases significantly in the initial iteration. The subsequent rate of convergence of the net error is very low. A modified technique for calculating a direction in weight-space which decreases the error for each class is presented. Using this algorithm, the rate of learning for two-class classification problems is accelerated by an order of magnitude.

Four random test generation strategies are compared to determine their relative effectiveness: equiprobable 0s and 1s; two weighted random pattern generation algorithms; and the maximum output information entropy principle. The test generation strategies are compared at a variety of target fault coverages. Two statistically based metrics are used to evaluate the techniques: a large-sample test of the difference of means and an upper confidence limit. The two weighted random test pattern generation strategies are found to be generally superior to equiprobable 0s and 1s and maximum output entropy. For a given logic circuit, the same technique is not necessarily optimal at every fault coverage.>

Thispaperpresents aperformance evaluation approachto compare different distributed load balancing schemes on

The Norse bounds state that all codes of strength 1 and length n have covering radius at most n/2 and all self-complementary codes of strength 2 and length n have covering radius at most (n- square root n)/2. This is generalized to arbitrary even values of strength, still assuming self-complementarity, and to odd strengths without this hypothesis. The proof techniques used are probabilistic.>

The relationship between the number of hidden nodes in a neural network, the complexity of a multiclass discrimination problem, and the number of samples needed for effect learning are discussed. Bounds for the number of samples needed for effect learning are given. It is shown that Omega(min (d,n) M) boundary samples are required for successful classification of M clusters of samples using a two-hidden-layer neural network with d-dimensional inputs and n nodes in the first hidden layer.

The relationship between psychological performance and psychological data for human auditory frequency discrimination is addressed. Two theories had been proposed earlier to explain the data available for this task: the single-band theory and the multiband theory. By constructing neural network models of the physiological structure, the authors attempted to substantiate these theories. However, the predictions of both these theories do not correspond well with observed data. The authors formulate a new weighted-band theory, which is suggested and supported by experimental data

The statistical performances of six methods in the finite sample estimation of the autoregressive (AR) parameters and the spectral peak frequencies are comparatively studied. The methods are: the Yule Walker method, Burg's method, the Box Jenkins least square method, the forward error method, the forward backward error method, and Kay's RMLE method. Precise performance statistics are obtained analytically for the AR(1) parameter estimators. For higher order processes similar evaluation is not feasible; computer simulation results are presented. The relative performances of the methods in the processing of stationary AR time series are found to be dependent on the characteristic root positions of the underlying AR processes. Methods that are superior are identified.

The problem of conversion of decision tables to decision trees is treated. In most cases, the construction of optimal decision trees is an NP-complete problem and, therefore, a heuristic approach to this problem is necessary. In this heuristic approach, an application of information theoretic concepts to construct efficient decision trees for decision tables which may include "don't care" entries is made. In contrast to most of the existing heuristic algorithms, this algorithm is systematic and is intuitively appealing from an information theoretic standpoint. The algorithm has low design complexity and yet provides near-optimal decision trees.

Asymptotic expressions are derived for the probability of bit error for optimum bit-by-bit decoding of a linear binary block code for the white Gaussian noise channel.