Search

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.

In this paper, we focus on how to use random forests based methods to improve the anomaly detection rate for streaming datasets.

Many data sets are described by models that may capture the underlying processes that lead to generation of data, describing a presumed functional or relational relationship between relevant variables. Such models permit comprehension and concise description of the data sets, facilitating identification of data points that are not consistent with such a description.

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.

We address the problem of discretization of continuous variables for machine learning classification algorithms. Existing procedures do not use interdependence between the variables towards this goal. Our proposed method uses clustering to exploit such interdependence. Numerical results show that this improves the classification performance in almost all cases. Even if an existing algorithm can successfully operate with continuous variables, better performance is obtained if the variables are first discretized. An additional advantage of discretization is that it reduces the overall computation time.

Centrality measures are extremely important in the analysis of social networks, with applications such as the identification of the most influential individuals for effective target marketing. Eigenvector centrality and PageRank are among the most useful centrality measures, but computing these measures can be prohibitively expensive for large social networks. This paper explores multiple approaches to improve the computational effort required to compute relative centrality measures. First, we show that small neural networks can be effective in fast estimation of the relative ordering of vertices in a social network based on these centrality measures. Then, we show how network sampling can be used to reduce the running times for calculating the ordering of vertices; degree centrality-based sampling reduces the running time of the key node identification problem. Finally, we propose the approach of incremental updating of centrality measures in dynamic networks.

In this paper, we present a temporal uncertainty-based inferencing paradigm for sensor networks. Multiple sensors observe a phenomenon and then exchange their probability estimates (for the occurrence of an event) with each other. Each node in the network fuses the evidence in such received messages, and computes the probability of occurrence of the relevant event. We develop and apply a temporal relevance decay model that accounts for the possibility that some observations lose their relevance or importance with the passage of time. As an illustrative example, this model is applied to the problems of object detection and tracking using multiple sensors with varying degrees of reliability.

Identification of a set of key players in a given social network is of interest in many disciplines such as sociology, politics, finance, economics, etc. Although many algorithms have been proposed to identify a set of key players, each emphasizes a single objective of their interest. Consequently, the prevailing deficiency of each of these methods is that they perform well only when we consider their objective of interest as the only characteristic the set of key players should have. But in complicated 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. This method allows us to compare other methods of key player identification. The sets of key players identified by this method are better when multiple objectives must be addressed. In addition we propose an algorithm to select the most suitable sets of key players when multiple choices are available. To reduce the computational complexity of the proposed approach for large networks, we propose a new sampling approach based on Degree centrality. We apply these algorithms in eventual influence limitation (EIL) problem and immunization problem and show that our multi-objective methodology outperforms previous key player identification approaches.

We propose a conjunction rule based classification technique that has good classification performance, is simple, automatically identifies important attributes, and is extremely fast. Due to these properties the classifier is most suitable for "big"/streaming data. Empirical study, using multiple datasets, shows that time complexity, compared with other classifiers, is faster by several factors, especially for large number of attributes without sacrificing performance.

Many anomaly detection algorithms have been proposed in recent years, including density-based and rank-based algorithms. In this paper, we propose ensemble methods to improve the performance of these individual algorithms. We evaluate approaches that use score and rank aggregation for these algorithms. We also consider sequential methods in which one detection method is followed by the other. We use several datasets to evaluate the performance of the proposed ensemble methods. Our results show that sequential methods significantly improve the ability to detect anomalous data points.

Centrality measures are extremely important in the analysis of social networks, with applications such as identification of the most influential individuals for effective target marketing. Eigenvector centrality and PageRank are among the most useful centrality measures, but computing these measures can be prohibitively expensive for large social networks. This paper shows that neural networks can be effective in learning and estimating the ordering of vertices in a social network based on these measures, requiring far less computational effort, and proving to be faster than early termination of the power grid method that can be used for computing the centrality measures. Two features describing the size of the social network and two vertex-specific attributes sufficed as inputs to the neural networks, requiring very few hidden neurons.

The behaviors of populations in evolutionary algorithms can be understood in terms of the dynamics of network models whose nodes represent individuals in the population. This paper explores "ancestral networks" in which connections indicate the proximity of the nearest common ancestor of two nodes. Preliminary experimental results show that the formation of large components in such an ancestral network model can be used to identify potential convergence, and to determine when randomly reseeding part of a population can prove beneficial.

Interrelationships between rules can be used to develop network models that can usefully represent the dynamics of Learning Classifier Systems. We examine two different kinds of rule networks and study their significance by testing them on the 20-mux problem. Through this experimentation, we establish that there is latent information in the evolving rule networks alongside the usual information that we gain from the XCS. We analyze these interrelationships using metrics from Network Science. We also show that these network measures behave as reliable indicators of rule set convergence.

In recent years, with the advent of fast sequencing technology, the genomic database is growing rapidly. Researchers in 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 compared with random background libraries on the same chip. Hash functions are widely used in substring comparison, sequence alignment and clustering tools. We have developed a light-weighted tool that takes advantage of the hash functions to reduce the size of genomic data and conducts k-neighbor searches on the centroid sequence. This greatly improves the efficiency of the search compared with the existing tool. Furthermore, the calculation of k-neighbor hash values decreases the mutant searching overhead. In a dataset of 1 million sequences, the program accurately counted the frequency of the Human alpha-Thrombin sequence and found the mutant versions of the target sequence in less than 40 seconds, whereas the existing method takes 8280 seconds (2 hours 13 minutes).

We address the online anomalous time series detection problem among a set of series, combining three simple distance measures. This approach, akin to control charts, makes it easy to determine when a series begins to differ from other series. Empirical evidence shows that this novel online anomalous time series detection algorithm performs very well, while being efficient in terms of time complexity, when compared to approaches previously discussed in the literature.

Rank-based algorithms provide a promising approach for outlier detection, but currently used rank-based measures of outlier detection suffer from two deficiencies: first they assign a large value to an object near a cluster whose density is high even through the object may not be an outlier and second the distance between the object and its nearest cluster plays a mild role though its rank with respect to its neighbor. To correct for these deficiencies we introduce the concept of modified-rank and propose new algorithms for outlier detection based on this concept. Our method performs better than several density-based methods, on some synthetic data sets as well as on some real data sets.

Network theoretic analyses have been shown to be extremely useful in multiple fields and applications. We propose this approach to study the dynamic behavior of evolutionary algorithms, the first such analysis to the best of our knowledge. Evolving populations are represented as dynamic networks, and we show that changes in population characteristics can be recognized at the level of the networks representing successive generations, with implications for possible improvements in the evolutionary algorithm, e.g., in deciding when a population is prematurely converging, and when a reinitialization of the population may be beneficial to reduce computational effort. In this paper, we show that network-theoretic analyses of evolutionary algorithms help in: (i) studying community-level behaviors, and (ii) using graph properties and metrics to analyze evolutionary algorithms.

Several metrics and indicators have been suggested in the past to evaluate multi-objective evolutionary and non-evolutionary algorithms. However, these metrics are known to have many problems that make their application sometimes unsound, and sometimes infeasible. This paper proposes a new approach, in which metrics are parameterized with respect to a reference set, on which depend the properties of any metric.

In this paper, we consider the problem of indoor surveillance and propose a feature selection scheme for occupancy classification in an indoor environment. The classifier aims to determine whether there is exactly one occupant or more than one occupant. Data are obtained from six seismic sensors (geophones) that are deployed in a typical building hallway. Four proposed features exploit amplitude and temporal characteristics of the seismic time series. A neural network classifier achieves performance ranging between 77% to 95% on the test data, depending on the type of construction of the location in the building being monitored.

We present a force-directed layout algorithm to detect community ­structure within a network. Our algorithm places nodes in a two-dimensional grid and continuously updates their positions based on two opposing forces: nodes pull connected nodes closer and push non-connected nodes away. To compute the strength of the forces between nodes we make use of two insightful community properties: high-degree nodes contribute more inter-community edges than low-degree nodes and the graph-distance between two nodes is inversely proportional to the probability that they belong to the same community. We present empirical evidence in support of both of these claims. In conjunction, we use a clustering algorithm to monitor and interpret the current community structure. Running our algorithm on well-known social networks, we find that we produce accurate results that avoid some common pitfalls of alternative approaches.

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.

This paper describes experiments and analysis of seismic signals in addressing the problem of personnel detection for indoor surveillance. Data was collected using geophones to detect footsteps from walking and running in indoor environments such as hallways. Our analysis of the data shows the significant presence of nonlinearity, when tested using the surrogate data method. This necessitates the need for novel detector designs that are not based on linearity assumptions. We present one such method based on empirical mode decomposition (EMD) and functional data analysis (FDA) and evaluate its applicability on our collected dataset.

In this paper, a new approach for multi-class classification problems is applied to the Semantic Role Labeling (SRL) problem, which is an important task for natural language processing systems to achieve better semantic understanding of text. The new approach applies to any classification problem with large feature sets. Data is partitioned using clusters on a subset of the features. A multi-label classifier is then trained individually on each cluster, using automatic feature selection to customize the larger feature set for the cluster. This algorithm is applied to the Semantic Role Labeling problem and achieves improvements in accuracy for both the argument identification classifier and the argument labeling classifier.

Several surveillance applications are characterized by the ability to gather information about the scene from more than one sensor modality, and heterogeneous sensor data must then be fused by the decision-maker. In this paper, we discuss the issues relevant to developing a model for fusion of information from audio and visual sensors, and present a framework to enhance decision-making capabilities. In particular, our methodology focuses on the issues of temporal reasoning, uncertainty representations, and coupling between features inferred from data streams coming from different sensors. We propose a conditional probability-based representation for uncertainty, along with fuzzy rules to assist decision-making, and a matrix representation of the coupling between sensor data streams. We also develop a fusion algorithm that utilizes these representations.

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.

A recurrent connectionist network has been designed to model sunspot data. The network architecture, sunspot data, and statistical models are described, and experimental results are provided. This preliminary experimental work shows that the network can produce competitive prediction results that compare with those of traditional autoregressive models. The method is not problem specific and could be applied to other problems in dynamical system modeling, recognition, prediction, and control fields. >

This paper takes a fresh look at some of the key ideas of genetic algorithms, using concepts drawn from the theory of majorization and probabilistic databases. We show the intimate relationships between GAs and the theory of probabilistic databases. We show how deception is well described using Saari's theorem, and its relationships with the Simpson and other paradoxes in decision theory. Reconstructability, a concept of fundamental importance in databases, is proposed as a useful substitute for deception. The database projection operator is connected with hyperplane partitions, and is used to show the nexus between point crossover operators and the join operator. Using results from probabilistic databases, we show that crossover may be considered as a majorization operator.

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 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.

The design, development, and performance of CM-RCS, a neural network simulator for the Connection Machine (CM), are described. The design of the simulator is based on the Rochester Connectionist Simulator (RCS) for connectionist networks. The CM-RCS can be used as a stand-alone system or as a high-performance parallel back end to RCS. In the latter case, once the network has been built by RCS, the back-end system constructs and executes an equivalent network on the CM processor array. The CM-RCS facilitates the exploitation of the massive parallelism inherent in connectionist networks. It also enables substantial reduction in the training times of connectionist networks. >

This paper presents three approaches to improve fault tolerance of neural networks. In two approaches, the traditional backpropagation training algorithm is itself modified so that the trained net works have improved fault tolerance; we achieve better results than others who had also explored this possibility. Our first method is to coerce weights to have low magnitudes, during the training process, since fault tolerance is degraded by the use of high magnitude weights; at the same time, additional hidden nodes are added dynamically to the network to ensure that desired performance can be reached. Our second method is to add artificial faults to various components (nodes and links) of a network during training. This leads to the development of networks that perform well even when faults occur in the network. The third method repeatedly eliminates nodes of least sensitivity, then "splits" the most sensitive nodes and retrains the system. This generally results in the best performance, although it requires a small amount of additional retraining after a network is built. Experimental results have shown that these methods can obtain better robustness than backpropagation training,and compare favorably with other approaches. >