Multi-view clustering has been found useful to leverage diverse data sources for accurate and robust underlying data representations. It typically relies on effectively integrating the latent features from different views through allocating weights while simultaneously mining their specificity and consensus information. However, it remains open how to achieve a more fine-grained sample-level weight allocation for promoting view-specific information fusion and view-shared consensus. To address this problem, we propose a novel multi-expert learning framework named Gated Variational Graph AutoEncoder with Competition and Consensus (GVGAE-C2). In particular, it employs multiple view-specific Variational Graph AutoEncoders (VGAEs) as experts to capture the latent features from their own views. Furthermore, we design a fine-grained structure-aware gating network, which dynamically computes sample-level weights based on the proposed structure-aware quality evaluation on each expert, thus facilitating competition among experts. Meanwhile, each expert is trained not only to study its assigned view's specificity features, but also explicitly encouraged to learn consensus-aware features across views. Extensive multi-view clustering experiments on benchmark datasets reveal that GVGAE-C2 significantly outperforms state-of-the-art methods.

Abstract In decision-dependent games, multiple players optimize their decisions under data distributions that shift with their joint actions, creating complex dynamics in applications like market pricing. A practical consequence of these dynamics is the performatively stable equilibrium , where each player’s strategy is a best response under the induced distribution. Prior work relies on $$\beta $$ -smoothness, assuming Lipschitz continuity of loss function gradients with respect to data distributions, which is impractical as the data distribution maps, i.e., the relationship between joint decision and the resulting distribution shifts, are typically unknown, rendering $$\beta $$ unobtainable. To overcome this limitation, we propose a gradient-based $$\hat{\varepsilon }_i$$ -sensitivity measure. It directly quantifies the impact of decision-induced distribution shifts on decision-making and is calculable for arbitrary data distribution maps. Leveraging this measure, we derive convergence guarantees for performatively stable equilibria under a practically feasible assumption of $$\alpha $$ -strong monotonicity. Notably, we establish a linear convergence rate in finite sample scenarios when $$\alpha > 2 \sqrt{\sum _{i = 1}^n \hat{\varepsilon }_i^2}$$ , with a probability depending on sample complexity. Accordingly, we develop a sensitivity-informed repeated retraining algorithm that adjusts players’ loss functions based on the sensitivity measure to achieve the strong monotonicity. This approach ensures the game satisfies the derived convergence condition and thus guarantees convergence to performatively stable equilibria for arbitrary data distribution maps. Experiments with various data distribution maps on prediction error minimization game, Cournot competition, and revenue maximization game show that our approach outperforms state-of-the-art baselines, achieving lower losses and faster convergence, validating the theoretical convergence conditions and confirming the effectiveness of the proposed algorithm.

Abstract Performative prediction refers to scenarios where model predictions influence the underlying data distribution they aim to predict. A desirable property in this context is performative stability , where model predictions are already optimal for the distribution they induce, indicating converged model parameters and no need for further retraining. Achieving performative stability requires characterizing the data distribution map $$\mathcal {D}(\theta )$$ , i.e., the relationship between predictions and the resulting distribution shifts. Current studies typically quantify distribution differences using metrics like $$\mathcal {W}_1$$ distance or $$\chi ^2$$ divergence, which may not provide isometric embeddings or maintain metric equivalence in practical scenarios, limiting their applicability across various data distribution maps. Moreover, the crucial smoothness parameter $$\beta $$ in existing work is often unobtainable in performative scenarios, constraining the real-world utility of current theoretical results and methods. To address these challenges, we develop an algorithm that learns a performatively stable model for arbitrary data distribution maps without requiring the joint smoothness parameter $$\beta $$ . Specifically, we introduce a new $$\hat{\varepsilon }$$ -sensitivity measure for $$\mathcal {D}(\theta )$$ , quantified by the gradient of the loss function, which naturally and directly characterizes how distribution shifts affect the optimization of the objective function. Based on this sensitivity, we formulate a $$\gamma $$ -strongly convex loss function and optimize the deployed model accordingly, where $$\gamma $$ is derived from the defined $$\hat{\varepsilon }$$ , eliminating the need for the $$\beta $$ -joint smoothness assumption. Our theoretical results guarantee the convergence of the deployed model to performative stability. Extensive experiments on synthetic and real-world datasets with diverse data distribution maps demonstrate the superiority of our method over state-of-the-art techniques in two key aspects: prediction accuracy and performative stability.

Time series anomaly detection has garnered significant research attention due to growing demands for temporal data monitoring across diverse domains. Despite the rapid advent of unsupervised anomaly detection models, existing approaches face two critical challenges in understanding the mechanisms of reconstruction-based models when handling diverse temporal dependencies: (1) the insufficient exploration of complex inter-timestamp relationships encompassing both short-term and long-term dependencies, and (2) the lack of integrated frameworks for jointly learning short-term patterns and long-term temporal characteristics. To address these challenges, we propose the novel Multi-Scale Hypergraph Transformer (MSHTrans), which leverages the capacity of hypergraphs for modeling multi-order temporal dependencies. Particularly, our method employs multi-scale downsampling to derive complementary fine-grained and coarse-grained representations, integrated with trainable hypergraph neural networks that can adaptively learn inter-timestamp relationships. The framework further integrates time series decomposition to systematically extract periodic and trend components from multi-granular features, thereby enhancing long-term dependency modeling. Through synergistic integration of learned short-term patterns and long-term temporal structures, the model achieves comprehensive time series reconstruction for effective anomaly detection. Extensive experiments demonstrate that MSHTrans outperforms state-of-the-art competitors with an average performance improvement of 8.21% (without point adjustment) and 3.52% (with point adjustment).

In open-world environments, classification models should be adept at identifying out-of-distribution (OOD) data whose semantics differ from in-distribution (ID) data, leading to the emerging research in OOD detection. As a promising learning scheme, outlier exposure (OE) enables the models to learn from auxiliary OOD data, enhancing model representations in discerning between ID and OOD patterns. However, these auxiliary OOD data often do not fully represent real OOD scenarios, potentially biasing our models in practical OOD detection. Hence, we propose a novel OE-based learning method termed Wasserstein Distribution-agnostic Outlier Exposure (W-DOE), which is both theoretically sound and experimentally superior to previous works. The intuition is that by expanding the coverage of training-time OOD data, the models will encounter fewer unseen OOD cases upon deployment. In W-DOE, we achieve additional OOD data to enlarge the OOD coverage, based on a new data synthesis approach called implicit data synthesis (IDS). It is driven by our new insight that perturbing model parameters can lead to implicit data transformation, which is simple to implement yet effective to realize. Furthermore, we suggest a general learning framework to search for the synthesized OOD data that can benefit the models most, ensuring the OOD performance for the enlarged OOD coverage measured by the Wasserstein metric. Our approach comes with provable guarantees for open-world settings, demonstrating that broader OOD coverage ensures reduced estimation errors and thereby improved generalization for real OOD cases. We conduct extensive experiments across a series of representative OOD detection setups, further validating the superiority of W-DOE against state-of-the-art counterparts in the field.

Subspace learning (SL) plays a key role in various learning tasks, especially those with a huge feature space. When processing multiple high-dimensional learning tasks simultaneously, it is of great importance to make use of the subspace extracted from some tasks to help learn others, so that the learning performance of all tasks can be enhanced together. To achieve this goal, it is crucial to answer the following question: How can the commonality among different learning tasks and, of equal importance, the individuality of each single learning task, be characterized and extracted from the given datasets, so as to benefit the subsequent learning, for example, classification? Existing multitask SL methods usually focused on the commonality among the given tasks, while neglecting the individuality of the learning tasks. In order to offer a more general and comprehensive framework for multitask SL, in this article, we propose a novel method dubbed commonality and individuality-based SL (CISL). First, we formally define the notions and objective functions of both commonality and individuality with respect to multiple SL tasks. Then, we design an iterative algorithm to solve the formulated objective functions, with the convergence of the algorithm being guaranteed. To show the generality of the proposed method, we theoretically analyze its connections to existing single-task and multitask SL methods. Finally, we demonstrate the necessity and effectiveness of incorporating both commonality and individuality by interpreting the learned subspaces and comparing the performance of CISL (in terms of the subsequent classification accuracy) with that of classical and state-of-the-art SL approaches on both synthetic and real-world multitask datasets. The empirical evaluation validates the effectiveness of the proposed method in characterizing the commonality and individuality for multitask SL.

Accurate prediction of sea surface temperature (SST) is crucial in the field of oceanography, as it has a significant impact on various physical, chemical, and biological processes in the marine environment. In this study, we propose a physics-guided attention-based neural network (PANN) to address the spatiotemporal SST prediction problem. The PANN model incorporates data-driven spatiotemporal convolution operations and the underlying physical dynamics of SSTs using a cross-attention mechanism. First, we construct a spatiotemporal convolution module (SCM) using convolutional long short-term memory (ConvLSTM) to capture the spatial and temporal correlations present in the time series of the SST data. We then introduce a physical constraint module (PCM) to mimic the transport dynamics in fluids based on data assimilation techniques used to solve partial differential equations (PDEs). Consequently, we employ an attention fusion module (AFM) to effectively combine the data-driven and PDE-constrained predictions obtained from the SCM and PCM, aiming at enhancing the accuracy of the predictions. To evaluate the performance of the proposed model, we conduct short-term SST forecasts in the East China Sea (ECS) with forecast lead times ranging from one to ten days, by comparing it with several state-of-the-art models, including ConvLSTM, PredRNN, temporal convolutional transformer network (TCTN), convolutional gated recurrent unit (ConvGRU), and SwinLSTM. The experimental results demonstrate that our proposed model outperforms these models in terms of multiple evaluation metrics for short-term predictions.

This paper is a brief personal journal of our relentless pursuit of Web Intelligence (WI). How it all started? What have achieved? Where are we heading? Our search for the ultimate meaning of the Web enables us to see and appreciate the power of the Web for building a better human society through collaboration, co-learning, and co-creation. The Web is a powerful idea, a scientific and technological innovation, and a social creation. Web Intelligence explores the connectivity, diversity, and plasticity of the Web, as well as the global brain supported by the Web. The goal of research on Web Intelligence is to build a better connected world of everything, by people, and for a new intelligent human society.

Infectious disease risk prediction plays a vital role in disease control and prevention. Recent studies in machine learning have attempted to incorporate epidemiological knowledge into the learning process to enhance the accuracy and informativeness of prediction results for decision-making. However, these methods commonly involve single-patch mechanistic models, overlooking the disease spread across multiple locations caused by human mobility. Additionally, these methods often require extra information beyond the infection data, which is typically unavailable in reality. To address these issues, this paper proposes a novel epidemiology-aware deep learning framework that integrates a fundamental epidemic component, the next-generation matrix (NGM), into the deep architecture and objective function. This integration enables the inclusion of both mechanistic models and human mobility in the learning process to characterize within- and cross-location disease transmission. From this framework, two novel methods, Epi-CNNRNN-Res and Epi-Cola-GNN, are further developed to predict epidemics, with experimental results validating their effectiveness.

Complex network models are helpful to explain the evolution rules of network structures, and also are the foundations of understanding and controlling complex networks. The existing studies (e.g., scale-free model, small-world model) are insufficient to uncover the internal mechanisms of the emergence and evolution of communities in networks. To overcome the above limitation, in consideration of the fact that a network can be regarded as a pattern composed of communities, we introduce Turing pattern dynamic as theory support to construct the network evolution model. Specifically, we develop a Reaction-Diffusion model according to Q-Learning technology (RDQL), in which each node regarded as an intelligent agent makes a behavior choice to update its relationships, based on the utility and behavioral strategy at every time step. Extensive experiments indicate that our model not only reveals how communities form and evolve, but also can generate networks with the properties of scale-free, small-world and assortativity. The effectiveness of the RDQL model has also been verified by its application in real networks. Furthermore, the depth analysis of the RDQL model provides a conclusion that the proportion of exploration and exploitation behaviors of nodes is the only factor affecting the formation of communities. The proposed RDQL model has potential to be the basic theoretical tool for studying network stability and dynamics.

The COVID-19 pandemic has caused the society lockdowns and a large number of deaths in many countries. Potential transmission cluster discovery is to find all suspected users with infections, which is greatly needed to fast discover virus transmission chains so as to prevent an outbreak of COVID-19 as early as possible. In this article, we study the problem of potential transmission cluster discovery based on the spatio-temporal logs. Given a query of patient user q and a timestamp of confirmed infection t q , the problem is to find all potential infected users who have close social contacts to user q before time t q . We motivate and formulate the potential transmission cluster model, equipped with a detailed analysis of transmission cluster property and particular model usability. To identify potential clusters, one straightforward method is to compute all close contacts on-the-fly, which is simple but inefficient caused by scanning spatio-temporal logs many times. To accelerate the efficiency, we propose two indexing algorithms by constructing a multigraph index and an advanced BCG-index. Leveraging two well-designed techniques of spatio-temporal compression and graph partition on bipartite contact graphs, our BCG-index approach achieves a good balance of index construction and online query processing to fast discover potential transmission cluster. We theoretically analyze and compare the algorithm complexity of three proposed approaches. Extensive experiments on real-world check-in datasets and COVID-19 confirmed cases in the United States validate the effectiveness and efficiency of our potential transmission cluster model and algorithms.

Data summarization that presents a small subset of a dataset to users has been widely applied in numerous applications and systems. Many datasets are coded with hierarchical terminologies, e.g., gene ontology, disease ontology, to name a few. In this paper, we study the weighted tree summarization. We motivate and formulate our${\mathsf {kWTS}}$-${\mathsf {problem}}$as selecting a diverse set of$k$nodes tosummarize a hierarchicaltree$T$withweighted terminologies. We first propose an efficient greedy tree summarization algorithm${\mathsf {GTS}}$. It solves the problem with$(1-1/e)$-approximation guarantee. Although${\mathsf {GTS}}$achieves quality-guaranteed answers approximately, but it is still not optimal. To tackle the problem optimally, we further develop a dynamic programming algorithm${\mathsf {OTS}}$to obtain optimal answers for${\mathsf {kWTS}}$-${\mathsf {problem}}$in$O(nhk^3)$time, where$n, h$are the node size and height in tree$T$. The algorithm complexity and correctness of${\mathsf {OTS}}$are theoretically analyzed. In addition, we propose a useful optimization technique of tree reduction to remove useless nodes with zero weights and shrink the tree into a smaller one, which ensures the efficiency acceleration of both${\mathsf {GTS}}$and${\mathsf {OTS}}$in real-world datasets. Moreover, we illustrate one useful application of graph visualization based on the answer of$k$-sized tree summarization and show it in a novel case study. Extensive experimental results on real-world datasets show the effectiveness and efficiency of our proposed approximate and optimal algorithms for tree summarization. Furthermore, we conduct a usability evaluation of attractive topic recommendation on ACM Computing Classification System dataset to validate the usefulness of our model and algorithms.

Summary Brain activity recognition research has been a challenging area for many decades since Hans Berger described electroencephalogram (EEG) in 1929. Many previous researches cannot successfully identify EEG status due to dynamic brain activities and complicated brain correlation. This article adopts multiagent‐based methods to analyze EEG datasets, which can enhance the analytical efficiency through incorporating autonomous, self‐coordination characteristics of agents. Intelligent agents are autonomous applications that can improve system compatibility. The preliminary results indicate that the combination of time‐dependency correlation method with multiagent method is an efficient solution for brain activity recognition.

The key to the effective control of a diffusion system lies in how accurately we could predict its unfolding dynamics based on the observation of its current state. However, in the real-world applications, it is often infeasible to conduct a timely and yet comprehensive observation due to resource constraints. In view of such a practical challenge, the goal of this work is to develop a novel computational method for performing active observations, termed active surveillance, with limited resources. Specifically, we aim to predict the dynamics of a large spatio-temporal diffusion system based on the observations of some of its components. Towards this end, we introduce a novel measure, the γ value, that enables us to identify the key components by means of modeling a sentinel network with a row sparsity structure. Having obtained a theoretical understanding of the γ value, we design a backward-selection sentinel network mining algorithm (SNMA) for deriving the sentinel network via group sparse Bayesian learning. In order to be practically useful, we further address the issue of scalability in the computation of SNMA, and moreover, extend SNMA to the case of a non-linear dynamical system that could involve complex diffusion mechanisms. We show the effectiveness of SNMA by validating it using both synthetic datasets and five real-world datasets. The experimental results are appealing, which demonstrate that SNMA readily outperforms the state-of-the-art methods.

Robustness is one of the most important performance criteria for any rail transit network (RTN), because it helps us enhance the efficiency of RTN. Several studies have addressed the issue of RTN robustness primarily from the perspectives of given rail network structures or static distributions of passenger flow. An open problem that remains in fully understanding RTN robustness is how to take the spatio-temporal characteristics of passenger travel into consideration, since the dynamic passenger flow in an RTN can readily trigger unexpected cascading failures. This paper addresses this problem as follows: (1) we propose a two-layer rail transit network (TL-RTN) model that captures the interactions between a rail network and its corresponding dynamic passenger flow network, and then (2) we conduct the cascading failure analysis of the TL-RTN model based on an extended coupled map lattice (CML). Specifically, our proposed model takes the strategy of passenger flow redistribution and the passenger flow capacity of each station into account to simulate the human mobility behaviors and to estimate the maximum passenger flow appeal in each station, respectively. Based on the smart card data of RTN passengers in Shanghai, our experiments show that the TL-RTN robustness is related to both external perturbations and failure modes. Moreover, during the peak hours on weekdays, due to the large passenger flow, a small perturbation will trigger a 20% cascading failure of a network. Having ranked the cascade size caused by the stations, we find that this phenomenon is determined by both the hub nodes and their neighbors.

We propose a general and scalable global optimization framework directly operating on annotated graph data by introducing a Bayesian graph neural network to approximate the expensive-to-evaluate objectives. It prevents the cubical complexity of Gaussian processes and can scale linearly with the number of observations. Its parallelized variant makes it scalable. We provide strict theoretical support on its convergence. Intensive experiments conducted on both artificial and real-world problems, including molecular discovery and urban road network design, demonstrate the effectiveness of the proposed methods compared with the current state of the art.

Single-cell RNA sequencing has enabled to capture the gene activities at single-cell resolution, thus allowing reconstruction of cell-type-specific gene regulatory networks (GRNs). The available algorithms for reconstructing GRNs are commonly designed for bulk RNA-seq data, and few of them are applicable to analyze scRNA-seq data by dealing with the dropout events and cellular heterogeneity. In this paper, we represent the joint gene expression distribution of a gene pair as an image and propose a novel supervised deep neural network called DeepDRIM which utilizes the image of the target TF-gene pair and the ones of the potential neighbors to reconstruct GRN from scRNA-seq data. Due to the consideration of TF-gene pair's neighborhood context, DeepDRIM can effectively eliminate the false positives caused by transitive gene-gene interactions. We compared DeepDRIM with nine GRN reconstruction algorithms designed for either bulk or single-cell RNA-seq data. It achieves evidently better performance for the scRNA-seq data collected from eight cell lines. The simulated data show that DeepDRIM is robust to the dropout rate, the cell number and the size of the training data. We further applied DeepDRIM to the scRNA-seq gene expression of B cells from the bronchoalveolar lavage fluid of the patients with mild and severe coronavirus disease 2019. We focused on the cell-type-specific GRN alteration and observed targets of TFs that were differentially expressed between the two statuses to be enriched in lysosome, apoptosis, response to decreased oxygen level and microtubule, which had been proved to be associated with coronavirus infection.

Medication combination prediction can be applied to the clinical treatment for critical patients with multi-morbidity. The suitable medication combination can help cure patients and keep the treatment medication safe. However, the complexity and uncertainty of clinical circumstances limit the predictive accuracy of medication combination. Thus, this paper proposes a new medication combination prediction model based on the temporal attention mechanism (TAM) and the simple graph convolution (SGC), named as TAMSGC. More specifically, the TAM can capture the temporal sequence information in the medical records, and the SGC is implemented to acquire the medication knowledge from the complicated medication combination. Experiments in a real dataset show that TAMSGC surpasses the baseline models on the predictive accuracy of medication combination.

In offline or online worlds, many social systems can be represented as signed social networks including both positive and negative relationships. Although a variety of studies on signed social networks have been conducted motivated by the great application value of unique polarity characteristics, how to model the process of influence propagation over signed social networks is still an important problem that remains pretty much open. Currently, a few studies extended traditional diffusion models (e.g., Independent Cascade model and Linear Threshold model) from unsigned social networks to signed social networks for estimating positive and negative influence of user sets. However, all of above extension models are stochastic and descriptive models. In order to ensure the accuracy of estimated influence, existing models require a significant number of Monte-Carlo simulations which are very time-consuming and not scalable. Aiming at this issue, we propose the Polarity-related Linear Influence Diffusion (PLID) model which can quickly and accurately calculate polarity-related influence of user sets without simulations. To validate effectiveness and efficiency of our proposed model, we make use of our PLID model to solve the positive influence maximization problem in signed social networks under rigorous mathematical proofs. Extensive experiments demonstrate that our PLID model and approximation algorithm significantly outperform state-of-the-art methods in terms of positive influence spread and running time, using Epinions and Slashdot datasets.

Deep learning has achieved incredible success over the past years, especially in various challenging predictive spatiotemporal analytics (PSTA) tasks, such as disease prediction, climate forecast, and traffic prediction, where intrinsic dependence relationships among data exist and generally manifest at multiple spatiotemporal scales. However, given a specific PSTA task and the corresponding data set, how to appropriately determine the desired configuration of a deep learning model, theoretically analyze the model's learning behavior, and quantitatively characterize the model's learning capacity remains a mystery. In order to demystify the power of deep learning for PSTA in a theoretically sound and explainable way, in this article, we provide a comprehensive framework for deep learning model design and information-theoretic analysis. First, we develop and demonstrate a novel interactively and integratively connected deep recurrent neural network (I2DRNN) model. I2DRNN consists of three modules: an input module that integrates data from heterogeneous sources; a hidden module that captures the information at different scales while allowing the information to flow interactively between layers; and an output module that models the integrative effects of information from various hidden layers to generate the output predictions. Second, to theoretically prove that our designed model can learn multiscale spatiotemporal dependence in PSTA tasks, we provide an information-theoretic analysis to examine the information-based learning capacity (i-CAP) of the proposed model. In so doing, we can tackle an important open question in deep learning, that is, how to determine the necessary and sufficient configurations of a designed deep learning model with respect to the given learning data sets. Third, to validate the I2DRNN model and confirm its i-CAP, we systematically conduct a series of experiments involving both synthetic data sets and real-world PSTA tasks. The experimental results show that the I2DRNN model outperforms both classical and state-of-the-art models on all data sets and PSTA tasks. More importantly, as readily validated, the proposed model captures the multiscale spatiotemporal dependence, which is meaningful in the real-world context. Furthermore, the model configuration that corresponds to the best performance on a given data set always falls into the range between the necessary and sufficient configurations, as derived from the information-theoretic analysis.

To investigate the robustness of complex networks in face of disturbances can help prevent potential network disasters. Percolation on networks is a potent instrument for network robustness analysis. However, existing percolation theories are primarily developed for interdependent or multilayer networks. Little attention is paid to multipartite networks which are an indispensable part of complex networks. In this article, we theoretically explore the robustness of multipartite networks under node failures. We put forward the generic percolation theory for gauging the robustness of multipartite networks with arbitrary degree distributions. Our developed theory is capable of quantifying the robustness of multipartite networks under either random or target node attacks. Our theory unravels the second order phase transition phenomenon for multipartite networks. In order to verify the correctness of the proposed theory, simulations on computer generated multipartite networks have been carried out. The experiments demonstrate that the simulation results coincide quite well with that yielded by the proposed theory.

The digital age has empowered brands with new and more effective targeted marketing tools in the form of key opinion leaders (KOLs). Because of the KOLs' unique capability to draw specific types of audience and cultivate long-term relationship with them, correctly identifying the most suitable KOLs within a social network is of great importance, and sometimes could govern the success or failure of a brand's online marketing campaigns. However, given the high dimensionality of social media data, conducting effective KOL identification by means of data mining is especially challenging. Owing to the generally multiple modalities of the user profiles and user-generated content (UGC) over the social networks, we can approach the KOL identification process as a multimodal learning task, with KOLs as a rare yet far more important class over non-KOLs in our consideration. In this regard, learning the compact and informative representation from the high-dimensional multimodal space is crucial in KOL identification. To address this challenging problem, in this paper, we propose a novel subspace learning algorithm dubbed modality-consistent harmonized discriminant embedding (MCHDE) to uncover the low-dimensional discriminative representation from the social media data for identifying KOLs. Specifically, MCHDE aims to find a common subspace for multiple modalities, in which the local geometric structure, the harmonized discriminant information, and the modality consistency of the dataset could be preserved simultaneously. The above objective is then formulated as a generalized eigendecomposition problem and the closed-form solution is obtained. Experiments on both synthetic example and a real-world KOL dataset validate the effectiveness of the proposed method.

In this paper, we propose a novel oversampling strategy dubbed Entropy-based Wasserstein Generative Adversarial Network (EWGAN) to generate data samples for minority classes in imbalanced learning. First, we construct an entropyweighted label vector for each class to characterize the data imbalance in different classes. Then we concatenate this entropyweighted label vector with the original feature vector of each data sample, and feed it into the WGAN model to train the generator. After the generator is trained, we concatenate the entropy-weighted label vector with random noise feature vectors, and feed them into the generator to generate data samples for minority classes. Experimental results on two benchmark datasets show that the samples generated by the proposed oversampling strategy can help to improve the classification performance when the data are highly imbalanced. Furthermore, the proposed strategy outperforms other state-of-the-art oversampling algorithms in terms of the classification accuracy.

Understanding the dynamic properties of epidemic spreading on complex social networks is essential to make effective and efficient public health policies for epidemic prevention and control. In recent years, the concept of network embedding has attracted lots of attention to deal with various network analytic tasks, the purpose of which is to encode relationships or information of networked elements into a low-dimensional vector space. However, most existing embedding methods have focused mainly on preserving static network information, such as structural proximity, node/edge attributes, and labels. On the contrary, in this paper, we focus on the embedding problem of preserving dynamic characteristics of epidemic spreading on social networks. We propose a novel embedding method, namely EpiRep, to learn node representations of a network by maximizing the likelihood of preserving groups of infected nodes due to the epidemics starting from every single node on the network. Specifically, the Susceptible-Infectious model is adopted to simulate the epidemic dynamics on networks, and the Continuous Bag-of-Words model with negative sampling is used to obtain node representations. Experimental results show that the EpiRep method outperforms two benchmark random-walk based embedding methods in terms of node clustering and classification on several synthetic and real-world networks. The proposed method and findings in this paper may offer new insight for source identification and infection prevention in the face of epidemic spreading on social networks.

Predicting epidemic dynamics is of great value in understanding and controlling diffusion processes, such as infectious disease spread and information propagation. This task is intractable, especially when surveillance resources are very limited. To address the challenge, we study the problem of active surveillance, i.e., how to identify a small portion of system components as sentinels to effect monitoring, such that the epidemic dynamics of an entire system can be readily predicted from the partial data collected by such sentinels. We propose a novel measure, the gamma value, to identify the sentinels by modeling a sentinel network with row sparsity structure. We design a flexible group sparse Bayesian learning algorithm to mine the sentinel network suitable for handling both linear and non-linear dynamical systems by using the expectation maximization method and variational approximation. The efficacy of the proposed algorithm is theoretically analyzed and empirically validated using both synthetic and real-world data.

In this paper we introduce a two-step clustering-based strategy, which can automatically generate prior information from data in order to further improve the accuracy and time efficiency of state-of-the-art algorithms for Bayesian network structure learning. Our clustering-based strategy is composed of two steps. In the first step, we divide the potential nodes into several groups via clustering analysis and apply Bayesian network structure learning to obtain some pre-existing arcs within each cluster. In the second step, with all the within-cluster arcs being well preserved, we learn the between-cluster structure of the given network. Experimental results on benchmark datasets show that a wide range of structure learning algorithms benefit from the proposed clustering-based strategy in terms of both accuracy and efficiency.

As social media grown to become an integral part of many people's daily life, brands are quick to launch targeted social media marketing campaign to acquire new potential customers online. To facilitate the potential customer discovery process, a costly and labor intensive manual selection process is done to build a brand portfolio consisting of multimedia data relevant to the brand. To automate this process in a cost-effective way, in this paper, we propose a novel Multi-Modal Distance Metric Learning (M2DML) method, which learns a data-dependent similarity metric from multi-modal media data, aiming at assisting the brands to retrieve appropriate media data from social networks for potential customer discovery. To comprehensively model the supervised information of multi-modal data, M2DML aims to learn both the intra-modality and inter-modality distance metrics simultaneously. To further explore the unsupervised information of the dataset, M2DML aims to preserve the manifold structure of the multi-modal data. The proposed method is then formulated as a standard eigen-decomposition problem and the closed form solution is efficiently computed. Experiments on a standard multi-modal media dataset and a self-collected dataset validate the effectiveness of the proposed method.

The elderly living in smart homes can have their daily movement recorded and analyzed. As different elders can have their own living habits, a methodology that can automatically identify their daily activities and discover their daily routines will be useful for better elderly care and support. In this article, we focus on automatic detection of behavioral patterns from the trajectory data of an individual for activity identification as well as daily routine discovery. The underlying challenges lie in the need to consider longer-range dependency of the sensor triggering events and spatiotemporal variations of the behavioral patterns exhibited by humans. We propose to represent the trajectory data using a behavior-aware flow graph that is a probabilistic finite state automaton with its nodes and edges attributed with some local behavior-aware features. We identify the underlying subflows as the behavioral patterns using the kernel k -means algorithm. Given the identified activities, we propose a novel nominal matrix factorization method under a Bayesian framework with Lasso to extract highly interpretable daily routines. For empirical evaluation, the proposed methodology has been compared with a number of existing methods based on both synthetic and publicly available real smart home datasets with promising results obtained. We also discuss how the proposed unsupervised methodology can be used to support exploratory behavior analysis for elderly care.

Traditional cluster ensemble approaches have several limitations. (1) Few make use of prior knowledge provided by experts. (2) It is difficult to achieve good performance in high-dimensional datasets. (3) All of the weight values of the ensemble members are equal, which ignores different contributions from different ensemble members. (4) Not all pairwise constraints contribute to the final result. In the face of this situation, we propose double weighting semi-supervised ensemble clustering based on selected constraint projection(DCECP) which applies constraint weighting and ensemble member weighting to address these limitations. Specifically, DCECP first adopts the random subspace technique in combination with the constraint projection procedure to handle high-dimensional datasets. Second, it treats prior knowledge of experts as pairwise constraints, and assigns different subsets of pairwise constraints to different ensemble members. An adaptive ensemble member weighting process is designed to associate different weight values with different ensemble members. Third, the weighted normalized cut algorithm is adopted to summarize clustering solutions and generate the final result. Finally, nonparametric statistical tests are used to compare multiple algorithms on real-world datasets. Our experiments on 15 high-dimensional datasets show that DCECP performs better than most clustering algorithms.

Data summarization that presents a small subset of a dataset to users has been widely applied in numerous applications and systems. Many datasets are coded with hierarchical terminologies, e.g., the international classification of Diseases-9, Medical Subject Heading, and Gene Ontology, to name a few. In this paper, we study the problem of selecting a diverse set of k elements to summarize an input dataset with hierarchical terminologies, and visualize the summary in an ontology structure. We propose an efficient greedy algorithm to solve the problem with (1-1/e)≈ 62%-approximation guarantee. Preliminary experimental results on real-world datasets show the effectiveness and efficiency of the proposed algorithm for data summarization.

Accurate and effective discovery of a brand's key assets, namely, Key Opinion Leaders (KOLs) and potential customers, plays an essential role in marketing campaigns. In a massive online social network, brands are challenged with identifying a small portion of key assets over an enormous volume of irrelevant users, making the problem a highly imbalanced one. Moreover, having to deal with social media data that are usually high-dimensional, the task of brand key asset discovery can be immensely expensive yet inaccurate if the information are not processed efficiently to extract representative features from the original space prior to the learning process. To address the above issues, we propose a novel method dubbed Cluster-wise Biased Discriminant Projection (CBDP) to uncover the compact and informative features from users' data for brand key asset discovery. CBDP conducts a two-layer learning procedure. In the first layer, a Discriminant Clustering (DC) scheme is developed to partition the original dataset into clusters with maximum discriminant capacity. In the second layer, a Biased Discriminant Projection (BDP) algorithm is proposed and performed on each cluster to map the high-dimensional data to the low-dimensional subspace, where the discriminant information of classes with high importance/preference is preserved. A unified mapping function of CBDP is finally established by integrating these two layers. Experiments on both synthetic examples and a real-world brand key asset dataset validate the effectiveness of the proposed method.

Recommender systems are used to accurately and actively provide users with potentially interesting information or services. Collaborative filtering is a widely adopted approach to recommendation, but sparse data and cold-start users are often barriers to providing high quality recommendations. To address such issues, we propose a novel method that works to improve the performance of collaborative filtering recommendations by integrating sparse rating data given by users and sparse social trust network among these same users. This is a model-based method that adopts matrix factorization technique that maps users into low-dimensional latent feature spaces in terms of their trust relationship, and aims to more accurately reflect the users reciprocal influence on the formation of their own opinions and to learn better preferential patterns of users for high-quality recommendations. We use four large-scale datasets to show that the proposed method performs much better, especially for cold start users, than state-of-the-art recommendation algorithms for social collaborative filtering based on trust.

During an epidemic, the spatial, temporal and demographic patterns of disease transmission are determined by multiple factors. In addition to the physiological properties of the pathogens and hosts, the social contact of the host population, which characterizes the reciprocal exposures of individuals to infection according to their demographic structure and various social activities, are also pivotal to understanding and predicting the prevalence of infectious diseases. How social contact is measured will affect the extent to which we can forecast the dynamics of infections in the real world. Most current work focuses on modeling the spatial patterns of static social contact. In this work, we use a novel perspective to address the problem of how to characterize and measure dynamic social contact during an epidemic. We propose an epidemic-model-based tensor deconvolution framework in which the spatiotemporal patterns of social contact are represented by the factors of the tensors. These factors can be discovered using a tensor deconvolution procedure with the integration of epidemic models based on rich types of data, mainly heterogeneous outbreak surveillance data, socio-demographic census data and physiological data from medical reports. Using reproduction models that include SIR/SIS/SEIR/SEIS models as case studies, the efficacy and applications of the proposed framework are theoretically analyzed, empirically validated and demonstrated through a set of rigorous experiments using both synthetic and real-world data.

Diffusion on social networks refers to the process where opinions are spread via the connected nodes. Given a set of observed information cascades, one can infer the underlying diffusion process for social network analysis. The independent cascade model (IC model) is a widely adopted diffusion model where a node is assumed to be activated independently by any one of its neighbors. In reality, how a node will be activated also depends on how its neighbors are connected and activated. For instance, the opinions from the neighbors of the same social group are often similar and thus redundant. In this paper, we extend the IC model by considering that: 1) the information coming from the connected neighbors are similar and 2) the underlying redundancy can be modeled using a dynamic structural diversity measure of the neighbors. Our proposed model assumes each node to be activated independently by different communities (or components) of its parent nodes, each weighted by its effective size. An expectation maximization algorithm is derived to infer the model parameters. We compare the performance of the proposed model with the basic IC model and its variants using both synthetic data sets and a real-world data set containing news stories and Web blogs. Our empirical results show that incorporating the community structure of neighbors and the structural diversity measure into the diffusion model significantly improves the accuracy of the model, at the expense of only a reasonable increase in run-time.

Nonparametric statistical analysis, such as the Friedman test (FT), is gaining more and more attention due to its useful applications in a lot of experimental studies. However, traditional FT for the comparison of multiple learning algorithms on different datasets adopts the naive ranking approach. The ranking is based on the average accuracy values obtained by the set of learning algorithms on the datasets, which neither considers the differences of the results obtained by the learning algorithms on each dataset nor takes into account the performance of the learning algorithms in each run. In this paper, we will first propose three kinds of ranking approaches, which are the weighted ranking approach, the global ranking approach (GRA), and the weighted GRA. Then, a theoretical analysis is performed to explore the properties of the proposed ranking approaches. Next, a set of the modified FTs based on the proposed ranking approaches are designed for the comparison of the learning algorithms. Finally, the modified FTs are evaluated through six classifier ensemble approaches on 34 real-world datasets. The experiments show the effectiveness of the modified FTs.

Conventional semi-supervised clustering approaches have several shortcomings, such as (1) not fully utilizing all useful must-link and cannot-link constraints, (2) not considering how to deal with high dimensional data with noise, and (3) not fully addressing the need to use an adaptive process to further improve the performance of the algorithm. In this paper, we first propose the transitive closure based constraint propagation approach, which makes use of the transitive closure operator and the affinity propagation to address the first limitation. Then, the random subspace based semi-supervised clustering ensemble framework with a set of proposed confidence factors is designed to address the second limitation and provide more stable, robust, and accurate results. Next, the adaptive semi-supervised clustering ensemble framework is proposed to address the third limitation, which adopts a newly designed adaptive process to search for the optimal subspace set. Finally, we adopt a set of nonparametric tests to compare different semi-supervised clustering ensemble approaches over multiple datasets. The experimental results on 20 real high dimensional cancer datasets with noisy genes and 10 datasets from UCI datasets and KEEL datasets show that (1) The proposed approaches work well on most of the real-world datasets. (2) It outperforms other state-of-the-art approaches on 12 out of 20 cancer datasets, and 8 out of 10 UCI machine learning datasets.

Modeling and predicting human dynamic behaviors in the face of stress and uncertainty can help understand and prevent potential irrational behavior, such as panic buying or evacuations, in the wake of extreme events. However, in terms of the types of events and the distinct human psychological factors, such as risk perception (RP) and emotional intensity (EI), human dynamic behaviors exhibit heterogeneous spatiotemporal characteristics. For example, we can observe different collective responses to the same events by people in different regions, with distinct trends unfolding over time. To provide a computational means for understanding the spatiotemporal characteristics of human behaviors during different types of extreme events, here we present a network-based model that enables us to characterize dynamic behaviors. This model assumes the perspective of a dynamic system, whose behavior is driven by human psychological factors and by the network structure of interactions among individuals. By making use of the available data from Twitter and GoogleTrends, we conduct a case study of human dynamic behavioral and emotional responses to the Japanese earthquake in 2011 in order to examine the effectiveness of our proposed model. With this model, we further assess the impacts of an event by evaluating the interrelationships of human RP and levels of EI in terms of observed collective behaviors. The results demonstrate that human behaviors are subjected to personal observations, experiences, and interactions, which can potentially alter perceptions and magnify the impacts of an event.

Cluster ensemble, as one of the important research directions in the ensemble learning area, is gaining more and more attention, due to its powerful capability to integrate multiple clustering solutions and provide a more accurate, stable and robust result. Cluster ensemble has a lot of useful applications in a large number of areas. Although most of traditional cluster ensemble approaches obtain good results, few of them consider how to achieve good performance for noisy datasets. Some noisy datasets have a number of noisy attributes which may degrade the performance of conventional cluster ensemble approaches. Some noisy datasets which contain noisy samples will affect the final results. Other noisy datasets may be sensitive to distance functions.

Complex social network analysis methods have been applied extensively in various domains including online social media, biological complex networks, etc. Complex social networks are facing the challenge of information overload. The demands for efficient complex network analysis methods have been rising in recent years, particularly the extensive use of online social applications, such as Flickr, Facebook and LinkedIn. This paper aims to simplify the network complexity through partitioning a large complex network into a set of less complex networks. Existing social network analysis methods are mainly based on complex network theory and data mining techniques. These methods are facing the challenges while dealing with extreme large social network data sets. Particularly, the difficulties of maintaining the statistical characteristics of partitioned sub-networks have been increasing dramatically. The proposed Normal Distribution (ND) based method can balance the distribution of the partitioned sub-networks according to the original complex network. Therefore, each subnetwork can have its degree distribution similar to that of the original network. This can be very beneficial for analyzing sub-divided networks and potentially reducing the complexity in dynamic online social environment.

With the advent of the Internet of things (IoT) and smart sensor technologies, the data-driven paradigm has been found promising to support human behavioral analysis in a smart home for better healthcare and well-being of senior adults. This work focuses on discovering daily activity routines from sensor data collected in a smart home. By representing the sensor data as a matrix, daily activity routines can be identified using matrix factorization methods. The key challenge rests on the fact that the matrix contains discrete labels as its elements, and decomposing the nominal data matrix into basis vectors of the labels is nontrivial. We propose a novel principled methodology to tackle the nominal matrix factorization problem. Assuming that the similarity matrix of the labels is known, the discrete labels are first projected onto a continuous space with the interlabel distance preserving the given similarity matrix of the labels as far as possible. Then, we extend a hierarchical probabilistic model for ordinal matrix factorization with Bayesian Lasso that the factorization can be more robust to noise and more sparse to ease human interpretation. Our experimental results based on a synthetic data set shows that the factorization results obtained using the proposed methodology outperform those obtained using a number of the state-of-the-art factorization methods in terms of the basis vector reconstruction accuracy. We also applied our model to a publicly available smart home data set to illustrate how the proposed methodology can be used to support daily activity routine analysis.

Community structure detection in complex networks contributes greatly to the understanding of complex mechanisms in many fields. In this article, we propose a multiagent evolutionary method for discovering communities in a complex network. The focus of the method lies in the evolutionary process of computational agents in a lattice environment, where each agent corresponds to a candidate solution to the community detection problem. First, the method uses a connection‐based encoding scheme to model an agent and a random‐walk behavior to construct a solution. Next, it applies three evolutionary operators, i.e., competition, crossover, and mutation, to realize information exchange among agents and solution evolution. We tested the performance of our method using synthetic and real‐world networks. The results show its capability in effectively detecting community structures.

Algorithms inspired by swarm intelligence have been used for many optimization problems and their effectiveness has been proven in many fields. We propose a new swarm intelligence algorithm for structural learning of Bayesian networks, BFO-B, based on bacterial foraging optimization. In the BFO-B algorithm, each bacterium corresponds to a candidate solution that represents a Bayesian network structure, and the algorithm operates under three principal mechanisms: chemotaxis, reproduction, and elimination and dispersal. The chemotaxis mechanism uses four operators to randomly and greedily optimize each solution in a bacterial population, then the reproduction mechanism simulates survival of the fittest to exploit superior solutions and speed convergence of the optimization. Finally, an elimination and dispersal mechanism controls the exploration processes and jumps out of a local optima with a certain probability. We tested the individual contributions of four algorithm operators and compared with two state of the art swarm intelligence based algorithms and seven other well-known algorithms on many benchmark networks. The experimental results verify that the proposed BFO-B algorithm is a viable alternative to learn the structures of Bayesian networks, and is also highly competitive compared to state of the art algorithms.

Genome-wide association studies (GWASs), which assay more than a million single nucleotide polymorphisms (SNPs) in thousands of individuals, have been widely used to identify genetic risk variants for complex diseases. However, most of the variants that have been identified contribute relatively small increments of risk and only explain a small portion of the genetic variation in complex diseases. This is the so-called missing heritability problem. Evidence has indicated that many complex diseases are genetically related, meaning these diseases share common genetic risk variants. Therefore, exploring the genetic correlations across multiple related studies could be a promising strategy for removing spurious associations and identifying underlying genetic risk variants, and thereby uncovering the mystery of missing heritability in complex diseases. We present a general and robust method to identify genetic patterns from multiple large-scale genomic datasets. We treat the summary statistics as a matrix and demonstrate that genetic patterns will form a low-rank matrix plus a sparse component. Hence, we formulate the problem as a matrix recovering problem, where we aim to discover risk variants shared by multiple diseases/traits and those for each individual disease/trait. We propose a convex formulation for matrix recovery and an efficient algorithm to solve the problem. We demonstrate the advantages of our method using both synthesized datasets and real datasets. The experimental results show that our method can successfully reconstruct both the shared and the individual genetic patterns from summary statistics and achieve comparable performances compared with alternative methods under a wide range of scenarios. The MATLAB code is available at: http://www.comp.hkbu.edu.hk/~xwan/iga.zip.

Conventional k -nearest neighbor (KNN) classification approaches have several limitations when dealing with some problems caused by the special datasets, such as the sparse problem, the imbalance problem, and the noise problem. In this paper, we first perform a brief survey on the recent progress of the KNN classification approaches. Then, the hybrid KNN (HBKNN) classification approach, which takes into account the local and global information of the query sample, is designed to address the problems raised from the special datasets. In the following, the random subspace ensemble framework based on HBKNN (RS-HBKNN) classifier is proposed to perform classification on the datasets with noisy attributes in the high-dimensional space. Finally, the nonparametric tests are proposed to be adopted to compare the proposed method with other classification approaches over multiple datasets. The experiments on the real-world datasets from the Knowledge Extraction based on Evolutionary Learning dataset repository demonstrate that RS-HBKNN works well on real datasets, and outperforms most of the state-of-the-art classification approaches.

Distance metric is the basis of many learning algorithms, and its effectiveness usually has a significant influence on the learning results. In general, measuring distance for numerical data is a tractable task, but it could be a nontrivial problem for categorical data sets. This paper, therefore, presents a new distance metric for categorical data based on the characteristics of categorical values. In particular, the distance between two values from one attribute measured by this metric is determined by both the frequency probabilities of these two values and the values of other attributes that have high interdependence with the calculated one. Dynamic attribute weight is further designed to adjust the contribution of each attribute-distance to the distance between the whole data objects. Promising experimental results on different real data sets have shown the effectiveness of the proposed distance metric.

BACKGROUND: High-throughput bio-techniques accumulate ever-increasing amount of genomic and proteomic data. These data are far from being functionally characterized, despite the advances in gene (or gene's product proteins) functional annotations. Due to experimental techniques and to the research bias in biology, the regularly updated functional annotation databases, i.e., the Gene Ontology (GO), are far from being complete. Given the importance of protein functions for biological studies and drug design, proteins should be more comprehensively and precisely annotated. RESULTS: We proposed downward Random Walks (dRW) to predict missing (or new) functions of partially annotated proteins. Particularly, we apply downward random walks with restart on the GO directed acyclic graph, along with the available functions of a protein, to estimate the probability of missing functions. To further boost the prediction accuracy, we extend dRW to dRW-kNN. dRW-kNN computes the semantic similarity between proteins based on the functional annotations of proteins; it then predicts functions based on the functions estimated by dRW, together with the functions associated with the k nearest proteins. Our proposed models can predict two kinds of missing functions: (i) the ones that are missing for a protein but associated with other proteins of interest; (ii) the ones that are not available for any protein of interest, but exist in the GO hierarchy. Experimental results on the proteins of Yeast and Human show that dRW and dRW-kNN can replenish functions more accurately than other related approaches, especially for sparse functions associated with no more than 10 proteins. CONCLUSION: The empirical study shows that the semantic similarity between GO terms and the ontology hierarchy play important roles in predicting protein function. The proposed dRW and dRW-kNN can serve as tools for replenishing functions of partially annotated proteins.

Self-organized regularities in terms of patient arrivals and wait times have been discovered in real-world healthcare services. What remains to be a challenge is how to characterize those regularities by taking into account the underlying patients' or hospitals' behaviors with respect to various impact factors. This paper presents a case study to address such a challenge. Specifically, it models and simulates the cardiac surgery services in Ontario, Canada, based on the methodology of Autonomy-Oriented Computing (AOC). The developed AOC-based cardiac surgery service model (AOC-CSS model) pays a special attention to how individuals' (e.g., patients and hospitals) behaviors and interactions with respect to some key factors (i.e., geographic accessibility to services, hospital resourcefulness, and wait times) affect the dynamics and relevant patterns of patient arrivals and wait times. By experimenting with the AOC-CSS model, we observe that certain regularities in patient arrivals and wait times emerge from the simulation, which are similar to those discovered from the real world. It reveals that patients' hospital-selection behaviors, hospitals' service-adjustment behaviors, and their interactions via wait times may potentially account for the self-organized regularities of wait times in cardiac surgery services.

Performing clustering analysis is one of the important research topics in cancer discovery using gene expression profiles, which is crucial in facilitating the successful diagnosis and treatment of cancer. While there are quite a number of research works which perform tumor clustering, few of them considers how to incorporate fuzzy theory together with an optimization process into a consensus clustering framework to improve the performance of clustering analysis. In this paper, we first propose a random double clustering based cluster ensemble framework (RDCCE) to perform tumor clustering based on gene expression data. Specifically, RDCCE generates a set of representative features using a randomly selected clustering algorithm in the ensemble, and then assigns samples to their corresponding clusters based on the grouping results. In addition, we also introduce the random double clustering based fuzzy cluster ensemble framework (RDCFCE), which is designed to improve the performance of RDCCE by integrating the newly proposed fuzzy extension model into the ensemble framework. RDCFCE adopts the normalized cut algorithm as the consensus function to summarize the fuzzy matrices generated by the fuzzy extension models, partition the consensus matrix, and obtain the final result. Finally, adaptive RDCFCE (A-RDCFCE) is proposed to optimize RDCFCE and improve the performance of RDCFCE further by adopting a self-evolutionary process (SEPP) for the parameter set. Experiments on real cancer gene expression profiles indicate that RDCFCE and A-RDCFCE works well on these data sets, and outperform most of the state-of-the-art tumor clustering algorithms.

Traditional random subspace-based classifier ensemble approaches (RSCE) have several limitations, such as viewing the same importance for the base classifiers trained in different subspaces, not considering how to find the optimal random subspace set. In this paper, we design a general hybrid adaptive ensemble learning framework (HAEL), and apply it to address the limitations of RSCE. As compared with RSCE, HAEL consists of two adaptive processes, i.e., base classifier competition and classifier ensemble interaction, so as to adjust the weights of the base classifiers in each ensemble and to explore the optimal random subspace set simultaneously. The experiments on the real-world datasets from the KEEL dataset repository for the classification task and the cancer gene expression profiles show that: 1) HAEL works well on both the real-world KEEL datasets and the cancer gene expression profiles and 2) it outperforms most of the state-of-the-art classifier ensemble approaches on 28 out of 36 KEEL datasets and 6 out of 6 cancer datasets.

editorial Free Access Share on Introduction to the ACM TIST Special Issue on Intelligent Healthcare Informatics Editors: Carlo Combi View Profile , Jiming Liu View Profile Authors Info & Claims ACM Transactions on Intelligent Systems and TechnologyVolume 6Issue 4August 2015 Article No.: 51pp 1–3https://doi.org/10.1145/2791398Published:04 July 2015Publication History 0citation216DownloadsMetricsTotal Citations0Total Downloads216Last 12 Months30Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Cluster ensemble is one of the main branches in the ensemble learning area which is an important research focus in recent years. The objective of cluster ensemble is to combine multiple clustering solutions in a suitable way to improve the quality of the clustering result. In this paper, we design a new noise immune cluster ensemble framework named as AP2CE to tackle the challenges raised by noisy datasets. AP2CE not only takes advantage of the affinity propagation algorithm (AP) and the normalized cut algorithm (Ncut), but also possesses the characteristics of cluster ensemble. Compared with traditional cluster ensemble approaches, AP2CE is characterized by several properties. (1) It adopts multiple distance functions instead of a single Euclidean distance function to avoid the noise related to the distance function. (2) AP2CE applies AP to prune noisy attributes and generate a set of new datasets in the subspaces consists of representative attributes obtained by AP. (3) It avoids the explicit specification of the number of clusters. (4) AP2CE adopts the normalized cut algorithm as the consensus function to partition the consensus matrix and obtain the final result. In order to improve the performance of AP2CE, the adaptive AP2CE is designed, which makes use of an adaptive process to optimize a newly designed objective function. The experiments on both synthetic and real datasets show that (1) AP2CE works well on most of the datasets, in particular the noisy datasets; (2) AP2CE is a better choice for most of the datasets when compared with other cluster ensemble approaches; (3) AP2CE has the capability to provide more accurate, stable and robust results.

Epidemic prediction is an important problem in epidemic control. Poisson regression methods are often adopted in existing works, mostly with only the (intra-)regional environmental factors considered. As the diffusion of epidemics is affected by not only the intra-regional factors but also inter-regional and external ones, a unified framework based on Poisson regression with the three types of factors incorporated is proposed for the prediction. Specifically, we propose a Poisson-regression-based model first with the intra-regional and inter-regional factors included. The intra-regional factor in a particular time interval is represented by one feature vector with the regionally environmental and social factors considered. The inter-regional factor is modeled by a diffusion matrix which describes the possibilities that the epidemics can spread from one region to another, which in turn accounts for the propagating effects of the infected cases. To learn the structure of the diffusion matrix, we propose two approaches-utilizing some a priori knowledge (e.g., transportation network) and estimating it from scratch via a sparse structure assumption. The resulting optimization problem of the maximum a posterior solution is a convex one and can be efficiently solved by the alternating direction method of multipliers (ADMM). In addition, we incorporate also the external factor, i.e., the imported cases. With one fact that the distribution of the number of infected cases over a year is (approximately) unimodal for most epidemics and one assumption that the importing rate has a small variance over the year, we can approximate the effect of the external factor with a parametric function (e.g., a quadratic function) over time. The resulting optimization problem is still convex and can be also solved by the ADMM algorithm. Empirical evaluations are conducted based on a real data set which records the 16-days-reported cases in the Yunnan province of China for seven years, from 2005 to 2011. The experimental results demonstrate the effectiveness of our proposed models.

Active surveillance is a desirable way to prevent the spread of infectious diseases in that it aims to timely discover individual incidences through an active searching for patients. However, in practice active surveillance is difficult to implement especially when monitoring space is large but available resources are limited. Therefore, it is extremely important for public health authorities to know how to distribute their very sparse resources to high-priority regions so as to maximize the outcomes of active surveillance. In this paper, we raise the problem of active surveillance planning and provide an effective method to address it via modeling and mining spatiotemporal patterns of infection risks from heterogeneous data sources. Taking malaria as an example, we perform an empirical study on real-world data to validate our method and provide our new findings.

During an epidemic, the spatial, temporal and demographical patterns of disease transmission are determined by multiple factors. Besides the physiological properties of pathogenes and hosts, the social contacts of host population, which characterize individuals' reciprocal exposures of infection in view of demographical structures and various social activities, are also pivotal to understand and further predict the prevalence of infectious diseases. The means of measuring social contacts will dominate the extent how precisely we can forecast the dynamics of infections in the real world. Most current works focus their efforts on modeling the spatial patterns of static social contacts. In this work, we address the problem on how to characterize and measure dynamical social contacts during an epidemic from a novel perspective. We propose an epidemic-model-based tensor deconvolution framework to address this issue, in which the spatiotemporal patterns of social contacts are represented by the factors of tensors, which can be discovered by a tensor deconvolution procedure with an integration of epidemic models from rich types of data, mainly including heterogeneous outbreak surveillance, social-demographic census and physiological data from medical reports. Taking SIR model as a case study, the efficacy of the proposed method is theoretically analyzed and empirically validated through a set of rigorous experiments on both synthetic and real-world data.

Multi-view learning, one of the important sub-fields in the area of machine learning, has gained more and more attention in class prediction of gene expression datasets. In this paper, we propose a new classifier ensemble framework, named as multi-view based Ad-a boost classifier ensemble framework (MV-ACE), which not only utilizes a random view generation technique to regulate different views and applies adaboost to adjust the training set, but also designs an adaptive process which explores the feasible combination of multiple views through an optimization process. Traditional multi-view learning focuses on exploring diverse views and the best integration of multiple views in a straight-forward manner, such as the linear combination of different views. Our proposed model, however, additionally applies a progressive training approach to improve the accuracies of the base classifiers. Moreover, we investigate the assembly of views at the model level, and employ an adaptive process to optimize the multi-view learning model to improve its performance. Our experiments on 12 cancer gene data sets for the classification task show that(i) MV-ACE works well on a diverse class of cancer gene expression profiles. (ii) It outperforms most of the state-of-the-art classifier ensemble approaches on these datasets.

MOTIVATION: The post-genome era sees urgent need for more novel approaches to extracting useful information from the huge amount of genetic data. The identification of recurrent copy number variations (CNVs) from array-based comparative genomic hybridization (aCGH) data can help understand complex diseases, such as cancer. Most of the previous computational methods focused on single-sample analysis or statistical testing based on the results of single-sample analysis. Finding recurrent CNVs from multi-sample data remains a challenging topic worth further study. RESULTS: We present a general and robust method to identify recurrent CNVs from multi-sample aCGH profiles. We express the raw dataset as a matrix and demonstrate that recurrent CNVs will form a low-rank matrix. Hence, we formulate the problem as a matrix recovering problem, where we aim to find a piecewise-constant and low-rank approximation (PLA) to the input matrix. We propose a convex formulation for matrix recovery and an efficient algorithm to globally solve the problem. We demonstrate the advantages of PLA compared with alternative methods using synthesized datasets and two breast cancer datasets. The experimental results show that PLA can successfully reconstruct the recurrent CNV patterns from raw data and achieve better performance compared with alternative methods under a wide range of scenarios. AVAILABILITY AND IMPLEMENTATION: The MATLAB code is available at http://bioinformatics.ust.hk/pla.zip.

Tumor clustering is one of the important techniques for tumor discovery from cancer gene expression profiles, which is useful for the diagnosis and treatment of cancer. While different algorithms have been proposed for tumor clustering, few make use of the expert's knowledge to better the performance of tumor discovery. In this paper, we first view the expert's knowledge as constraints in the process of clustering, and propose a feature selection based semi-supervised cluster ensemble framework (FS-SSCE) for tumor clustering from bio-molecular data. Compared with traditional tumor clustering approaches, the proposed framework FS-SSCE is featured by two properties: (1) The adoption of feature selection techniques to dispel the effect of noisy genes. (2) The employment of the binate constraint based K-means algorithm to take into account the effect of experts' knowledge. Then, a double selection based semi-supervised cluster ensemble framework (DS-SSCE) which not only applies the feature selection technique to perform gene selection on the gene dimension, but also selects an optimal subset of representative clustering solutions in the ensemble and improve the performance of tumor clustering using the normalized cut algorithm. DS-SSCE also introduces a confidence factor into the process of constructing the consensus matrix by considering the prior knowledge of the data set. Finally, we design a modified double selection based semi-supervised cluster ensemble framework (MDS-SSCE) which adopts multiple clustering solution selection strategies and an aggregated solution selection function to choose an optimal subset of clustering solutions. The results in the experiments on cancer gene expression profiles show that (i) FS-SSCE, DS-SSCE and MDS-SSCE are suitable for performing tumor clustering from bio-molecular data. (ii) MDS-SSCE outperforms a number of state-of-the-art tumor clustering approaches on most of the data sets.

Recent findings show that online reviews, blogs, and discussion forums on chronic diseases and drugs are becoming important supporting resources for patients. Extracting information from these substantial bodies of texts is useful and challenging. We developed a generative probabilistic aspect mining model (PAMM) for identifying the aspects/topics relating to class labels or categorical meta-information of a corpus. Unlike many other unsupervised approaches or supervised approaches, PAMM has a unique feature in that it focuses on finding aspects relating to one class only rather than finding aspects for all classes simultaneously in each execution. This reduces the chance of having aspects formed from mixing concepts of different classes; hence the identified aspects are easier to be interpreted by people. The aspects found also have the property that they are class distinguishing: They can be used to distinguish a class from other classes. An efficient EM-algorithm is developed for parameter estimation. Experimental results on reviews of four different drugs show that PAMM is able to find better aspects than other common approaches, when measured with mean pointwise mutual information and classification accuracy. In addition, the derived aspects were also assessed by humans based on different specified perspectives, and PAMM was found to be rated highest.

Many real-world problems exhibit phenomena which are best represented as complex networks with dynamic structures (e.g., human communication networks). Network motifs have been shown effective for characterizing the structural properties of such complex networks. Nevertheless, related motif models typically do not consider stochastic structural and sequential variations, hinting their limitations on dynamic network analysis. In this paper, we consider networks with time-stamped edges and model their local structural and temporal variations using a mixture of Markov chains for stochastic temporal network motif detection. The optimal number of motifs is automatically estimated in a Bayesian framework. We evaluated the proposed method using synthetic networks and found to be robust against noise compared to the deterministic approach. Also, we applied it to a mobile phone usage data set to demonstrate how the human communication patterns embedded in the data set can be detected. In addition, we make use of a hidden Markov model with different distributions for the mixing proportions of the motifs defining its states, and demonstrated how the evolution of the communication patterns can also be identified.

Online social networks (OSN) are facing challenges since they have been extensively applied to different domains including online social media, e-commerce, biological complex networks, financial analysis, and so on. One of the crucial challenges for OSN lies in information overload and network congestion. The demands for efficient knowledge discovery and data mining methods in OSN have been rising in recent year, particularly for online social applications, such as Flickr, YouTube, Facebook, and LinkedIn. In this paper, a Belief-Desire-Intention (BDI) agent-based method has been developed to enhance the capability of mining online social networks. Current data mining techniques encounter difficulties of dealing with knowledge interpretation based on complex data sources. The proposed agent-based mining method overcomes network analysis difficulties, while enhancing the knowledge discovery capability through its autonomy and collective intelligence.

Latent Dirichlet allocation (LDA) is an important hierarchical Bayesian model for probabilistic topic modeling, which attracts worldwide interest and touches on many important applications in text mining, computer vision and computational biology. This paper represents the collapsed LDA as a factor graph, which enables the classic loopy belief propagation (BP) algorithm for approximate inference and parameter estimation. Although two commonly used approximate inference methods, such as variational Bayes (VB) and collapsed Gibbs sampling (GS), have gained great success in learning LDA, the proposed BP is competitive in both speed and accuracy, as validated by encouraging experimental results on four large-scale document datasets. Furthermore, the BP algorithm has the potential to become a generic scheme for learning variants of LDA-based topic models in the collapsed space. To this end, we show how to learn two typical variants of LDA-based topic models, such as author-topic models (ATM) and relational topic models (RTM), using BP based on the factor graph representations.

Viruses and malwares can spread from computer networks into mobile networks with the rapid growth of smart cellphone users. In a mobile network, viruses and malwares can cause privacy data leakage, extra charges, and remote listening. Furthermore, they can jam wireless servers by sending thousands of spam messages or track user positions through GPS. Because of the potential damages of mobile viruses, it is important for us to gain a deep understanding of the propagation mechanisms of mobile viruses. In this paper, we propose a two-layer network model for simulating virus propagation through both Bluetooth and SMS. Different from previous work, our work addresses the impacts of human behaviors, i.e., operational behavior and mobile behavior, on virus propagation. Our simulation results provide further insights into the determining factors of virus propagation in mobile networks. Moreover, we examine two strategies for restraining mobile virus propagation, i.e., preimmunization and adaptive dissemination strategies drawing on the methodology of autonomy-oriented computing (AOC). The experimental results show that our strategies can effectively protect large-scale and/or highly dynamic mobile networks.

Effective sharing of diverse social media is often inhibited by limitations in their search and discovery mechanisms, which are particularly restrictive for media that do not lend themselves to automatic processing or indexing. Here, we present the structure and mechanism of an adaptive search engine which is designed to overcome such limitations. The basic framework of the adaptive search engine is to capture human judgment in the course of normal usage from user queries in order to develop semantic indexes which link search terms to media objects semantics. This approach is particularly effective for the retrieval of multimedia objects, such as images, sounds, and videos, where a direct analysis of the object features does not allow them to be linked to search terms, for example, nontextual/icon-based search, deep semantic search, or when search terms are unknown at the time the media repository is built. An adaptive search architecture is presented to enable the index to evolve with respect to user feedback, while a randomized query-processing technique guarantees avoiding local minima and allows the meaningful indexing of new media objects and new terms. The present adaptive search engine allows for the efficient community creation and updating of social media indexes, which is able to instill and propagate deep knowledge into social media concerning the advanced search and usage of media resources. Experiments with various relevance distribution settings have shown efficient convergence of such indexes, which enable intelligent search and sharing of social media resources that are otherwise hard to discover.

Semi-supervised learning is one of the important topics in machine learning, concerning with pattern classification where only a small subset of data is labeled. In this paper, a new network-based (or graph-based) semi-supervised classification model is proposed. It employs a combined random-greedy walk of particles, with competition and cooperation mechanisms, to propagate class labels to the whole network. Due to the competition mechanism, the proposed model has a local label spreading fashion, i.e., each particle only visits a portion of nodes potentially belonging to it, while it is not allowed to visit those nodes definitely occupied by particles of other classes. In this way, a “divide-and-conquer” effect is naturally embedded in the model. As a result, the proposed model can achieve a good classification rate while exhibiting low computational complexity order in comparison to other network-based semi-supervised algorithms. Computer simulations carried out for synthetic and real-world data sets provide a numeric quantification of the performance of the method.

Network communities refer to groups of vertices within which their connecting links are dense but between which they are sparse. A network community mining problem (or NCMP for short) is concerned with the problem of finding all such communities from a given network. A wide variety of applications can be formulated as NCMPs, ranging from social and/or biological network analysis to web mining and searching. So far, many algorithms addressing NCMPs have been developed and most of them fall into the categories of either optimization based or heuristic methods. Distinct from the existing studies, the work presented in this paper explores the notion of network communities and their properties based on the dynamics of a stochastic model naturally introduced. In the paper, a relationship between the hierarchical community structure of a network and the local mixing properties of such a stochastic model has been established with the large-deviation theory. Topological information regarding to the community structures hidden in networks can be inferred from their spectral signatures. Based on the above-mentioned relationship, this work proposes a general framework for characterizing, analyzing, and mining network communities. Utilizing the two basic properties of metastability, i.e., being locally uniform and temporarily fixed, an efficient implementation of the framework, called the LM algorithm, has been developed that can scalably mine communities hidden in large-scale networks. The effectiveness and efficiency of the LM algorithm have been theoretically analyzed as well as experimentally validated.

Most real-world distribution systems can be modeled as distribution networks, where a commodity can flow from source nodes to sink nodes through junction nodes. One of the fundamental characteristics of distribution networks is the functional robustness, which reflects the ability of maintaining its function in the face of internal or external disruptions. In view of the fact that most distribution networks do not have any centralized control mechanisms, we consider the problem of how to improve the functional robustness in a decentralized way. To achieve this goal, we study two important problems: 1) how to formally measure the functional robustness, and 2) how to improve the functional robustness of a network based on the local interaction of its nodes. First, we derive a utility function in terms of network entropy to characterize the functional robustness of a distribution network. Second, we propose a decentralized network pricing mechanism, where each node need only communicate with its distribution neighbors by sending a "price" signal to its upstream neighbors and receiving "price" signals from its downstream neighbors. By doing so, each node can determine its outflows by maximizing its own payoff function. Our mathematical analysis shows that the decentralized pricing mechanism can produce results equivalent to those of an ideal centralized maximization with complete information. Finally, to demonstrate the properties of our mechanism, we carry out a case study on the U.S. natural gas distribution network. The results validate the convergence and effectiveness of our mechanism when comparing it with an existing algorithm.

Complex network theory provides a means for modeling and analyzing complex systems that consist of multiple and interdependent components. Among the studies on complex networks, structural analysis is of fundamental importance as it presents a natural route to understanding the dynamics, as well as to synthesizing or optimizing the functions, of networks. A wide spectrum of structural patterns of networks has been reported in the past decade, such as communities, multipartites, bipartite, hubs, authorities, outliers, and bow ties, among others. In this paper, we are interested in tackling the challenging task of characterizing and extracting multiplex patterns (multiple patterns as mentioned previously coexisting in the same networks in a complicated manner), which so far has not been explicitly and adequately addressed in the literature. Our work shows that such multiplex patterns can be well characterized as well as effectively extracted by means of a granular stochastic blockmodel, together with a set of related algorithms proposed here based on some machine learning and statistical inference ideas. These models and algorithms enable us to further explore complex networks from a novel perspective.

This paper studies the problem of selecting queries to efficiently crawl a deep web data source using a set of sample documents. Crawling deep web is the process of collecting data from search interfaces by issuing queries. One of the major challenge

The ability to discover patterns of networks is fundamental for structural analysis applied to them. Many ubiquitous patterns demonstrated by real-world networks have been discovered, and corresponding tools for finding them also have been developed. Although existing works have greatly improved our understanding on networks, it is still challenging to precisely model and predict their behaviors mainly because their non-trivial structures usually consists of many fold coexisting patterns which cannot be appropriately and totally uncovered by a single tool exclusively designed for pre-defined ones. In this work, we take an effort to address this issue by introducing a parameter-free algorithm aiming to discover such patterns hidden in an explorative network.

Viruses and malwares can spread from computer networks to mobile networks with the rapid growth of smart cellpone users. In a mobile network, viruses and malwares can cause privacy leakage, extra charges, remote listening and accessing private short messages and call history logs etc. Furthermore, they can jam wireless servers by sending thousands of spam messages or track user positions via GPS. Because of the potential damages of mobile viruses, it is important for us to design a realistic propagation model to observe and understand the propagation mechanisms of mobile viruses. In this paper, we propose a two-layer model to simulate the propagation process of BT-based and SMS-based viruses in mobile networks. Different from previous work, here we focus on the impacts of human behavior, i.e., human operations and mobility patterns, on virus propagation. Through simulations, we aim to gain some insights into how human behavior affects the dynamics of virus spread in mobile networks.

Natural language question‐and‐answering is one of the most convenient means for communicating with the Semantic Web, which is typically in the form of online knowledge bases encoded in Web Ontology Language (OWL). To understand a natural language question, it is essential that it can be translated into a query that is understandable by the knowledge bases. This article is concerned with the task of semantic mapping from natural language questions to OWL queries, and proposes an automatic and domain‐independent mapping framework, called Three‐Phases Semantic Mapping (TPSM). The TPSM framework approaches the task of semantic mapping in three interrelated phases: (i) formalizing knowledge, (ii) building semantic mapping, and (iii) combining OWL queries. First, formalizing knowledge formalizes the units of mapping in the natural language and OWL knowledge. Second, semantic mapping builds the transverse mapping between questions and OWL knowledge, as formalized in the first phase, by means of working with the so‐called Fuzzy Constraint Satisfaction Problems (FCSP). Third, combining OWL queries obtains valid Resource Description Framework (RDF) models by applying predefined templates and their corresponding combining methods. We have implemented a prototype semantic mapping system based on the framework, and have conducted a series of experimental validations involving OWL knowledge bases in different domains as queried by various types of questions.

Many communication systems, e.g., internet, can be modeled as complex networks. For such networks, immunization strategies are necessary for preventing malicious attacks or viruses being percolated from a node to its neighboring nodes following their connectivities. In recent years, various immunization strategies have been proposed and demonstrated, most of which rest on the assumptions that the strategies can be executed in a centralized manner and/or that the complex network at hand is reasonably stable (its topology will not change overtime). In other words, it would be difficult to apply them in a decentralized network environment, as often found in the real world. In this paper, we propose a decentralized and scalable immunization strategy based on a self-organized computing approach called autonomy-oriented computing (AOC) [1], [2]. In this strategy, autonomous behavior-based entities are deployed in a decentralized network, and are capable of collectively finding those nodes with high degrees of conductivities (i.e., those that can readily spread viruses). Through experiments involving both synthetic and real-world networks, we demonstrate that this strategy can effectively and efficiently locate highly-connected nodes in decentralized complex network environments of various topologies, and it is also scalable in handling large-scale decentralized networks. We have compared our strategy with some of the well-known strategies, including acquaintance and covering strategies on both synthetic and real-world networks.

Spontaneous brain activity studies have revealed `small-world' property in functional networks based on correlated or positively-correlated relationships. However, studies neither investigated negatively-correlated functional networks, nor checked the `dynamic' properties of the whole functional organization. After subjects performed a specific task, what changes will be caused in the intrinsic organization? In this study, we examined pre-task and post-task resting brains using functional MRI (fMRI). Then we suggested two perspectives with positively-correlated brain functional network (PCBFN) and negatively-correlated brain functional network (NCBFN), by testing whether correlation coefficients were positive or negative. The major findings were: 1) the PCBFN was with small-world architecture but the NCBFN was not, with different motifs, and the PCBFN showed stronger small-world effect at the post-task resting state; 2) Both PCBFN and NCBFN followed an exponentially truncated power law degree distribution. This study may offer a framework to investigate the intrinsic organization of spontaneous brain activity.

This paper presents the coauthor network topic (CNT) model constructed based on Markov random fields (MRFs) with higher-order cliques. Regularized by the complex coauthor network structures, the CNT can simultaneously learn topic distributions as well as expertise of authors from large document collections. Besides modeling the pairwise relations, we model also higher-order coauthor relations and investigate their effects on topic and expertise modeling. We derive efficient inference and learning algorithms from the Gibbs sampling procedure. To confirm the effectiveness, we apply the CNT to the expert finding problem on a DBLP corpus of titles from six different computer science conferences. Experiments show that the higher-order relations among coauthors can improve the topic and expertise modeling performance over the case with pairwise relations, and thus can find more relevant experts given a query topic or document.

In recent years, immunization strategies have been developed for stopping epidemics in complex-network-like environments. Yet it still remains a challenge for existing strategies to deal with dynamically-evolving networks that contain community structures, though they are ubiquitous in the real world. In this paper, we examine the performances of an autonomy-oriented distributed search strategy for tackling such networks. The strategy is based on the ideas of self-organization and positive feedback from Autonomy-Oriented Computing (AOC). Our experimental results have shown that autonomous entities in this strategy can collectively find and immunize most highly-connected nodes in a dynamic, community-based network within a few steps.

Partially observable Markov decision process (POMDP) is a commonly adopted mathematical framework for solving planning problems in stochastic environments. However, computing the optimal policy of POMDP for large-scale problems is known to be intractable, where the high dimensionality of the underlying belief space is one of the major causes. In this paper, we propose a hybrid approach that integrates two different approaches for reducing the dimensionality of the belief space: 1) belief compression and 2) value-directed compression. In particular, a novel orthogonal nonnegative matrix factorization is derived for the belief compression, which is then integrated in a value-directed framework for computing the policy. In addition, with the conjecture that a properly partitioned belief space can have its per-cluster intrinsic dimension further reduced, we propose to apply a k-means-like clustering technique to partition the belief space to form a set of sub-POMDPs before applying the dimension reduction techniques to each of them. We have evaluated the proposed belief compression and clustering approaches based on a set of benchmark problems and demonstrated their effectiveness in reducing the cost for computing policies, with the quality of the policies being retained.

Research has shown that many social networks come into being hierarchically based on some basic building blocks called communities, within which the social interactions are very intensive, but between which they are very weak. Network community mining algorithms aim at efficiently and effectively discovering all such communities from a given network. Many related methods have been proposed and applied to different areas including social network analysis, gene network analysis and web clustering engine. Most of the existing methods for mining communities are centralized. In this paper, we present a multi-agent based decentralized algorithm, in which a group of autonomous agents work together to mine a network through a proposed self-aggregation and self-organization mechanism. Thanks to its decentralized feature, our method is potentially suitable for dealing with distributed networks, whose global structures are hard to obtain due to their geographical distributions, decentralized controls or huge sizes. The effectiveness of our method has been tested against different benchmark networks.

Nowadays ranking function discovery approaches using Evolutionary Computation (EC), especially Genetic Programming (GP), have become an important branch in the Learning to Rank for Information Retrieval (LR4IR) field. Inspired by the GP based learning to rank approaches, we provide a series of generalized definitions and a common framework for the application of EC in learning to rank research. Besides, according to the introduced framework, we propose RankIP, a ranking function discovery approach using Immune Programming (IP). Experimental results demonstrate that RankIP evidently outperforms the baselines.

In this paper we propose the multirelational topic model (MRTM) for multiple types of link modeling such as citation and coauthor links in document networks. In the citation network, the MRTM models the citation link between each pair of documents as a binary variable conditioned on their topic distributions. In the coauthor network, the MRTM models the coauthor link between each pair of authors as a binary variable conditioned on their expertise distributions. The topic discovery is collectively regularized by multiple relations in both citation and coauthor networks. This model can summarize topics from the document network, predict citation links between documents and coauthor links between authors. Efficient inference and learning algorithms are derived based on Gibbs sampling. Experiments demonstrate that the MRTM significantly outperforms other state-of-the-art single-relational link modeling methods for large scientific document networks.

An overwhelming phenomena across natural systems, social systems and ecosystems is discovered in recent years. The phenomena is coined by many terms, such as 1/f noise, Zipf-laws, or scale-free, while power-law distribution of various events or metrics is the fundamental fact that exists in every complex system. It is believed that there exist a mechanism to rule the dynamics of complex system and generate the distribution. In this paper, a general growth model which incorporate Lotka-Volterra dynamics is developed to explain the mechanism of the power-law distribution preliminary. In the model, the influence on power distribution of the spreading rate and the mortality rate can be easily analyzed and explained.

Real-world social networks (e.g., blogosphere) often evolve over time and thus poses challenges on conventional social network analysis techniques which model the underlying networks as static graphs. In this paper, we are interested in detecting dynamic communities and their trend of evolution in a social network by examining the structural and dynamic patterns of interactions. In doing so, we propose an iterative mining algorithm for computing the intensities and bursts of some hidden communities over time. Our method is probabilistic in nature and can be applied to both undirected graphs and directed graphs. Quantitative and qualitative performance comparisons between the proposed method and some representative methods for social network analysis are provided. Evaluation results based on three benchmark datasets, including Reuters terror news network, political blogosphere, and Enron emails, show that the proposed method is both effective and efficient.

The 13 papers in this special issue focus on knowledge and data engineering for e-learning. Some of these papers were recommended submissions from the best ranked papers presented at the Sixth International Conference on Web-Based Learning (ICWL '07), held in August 2007 in Edinburgh, United Kingdom.

The multiagent optimization system (MAOS) is a nature-inspired method, which supports cooperative search by the self-organization of a group of compact agents situated in an environment with certain sharing public knowledge. Moreover, each agent in MAOS is an autonomous entity with personal declarative memory and behavioral components. In this paper, MAOS is refined for solving the traveling salesman problem (TSP), which is a classic hard computational problem. Based on a simplified MAOS version, in which each agent manipulates on extremely limited declarative knowledge, some simple and efficient components for solving TSP, including two improving heuristics based on a generalized edge assembly recombination, are implemented. Compared with metaheuristics in adaptive memory programming, MAOS is particularly suitable for supporting cooperative search. The experimental results on two TSP benchmark data sets show that MAOS is competitive as compared with some state-of-the-art algorithms, including the Lin-Kernighan-Helsgaun, IBGLK, PHGA, etc., although MAOS does not use any explicit local search during the runtime. The contributions of MAOS components are investigated. It indicates that certain clues can be positive for making suitable selections before time-consuming computation. More importantly, it shows that the cooperative search of agents can achieve an overall good performance with a macro rule in the switch mode, which deploys certain alternate search rules with the offline performance in negative correlations. Using simple alternate rules may prevent the high difficulty of seeking an omnipotent rule that is efficient for a large data set.

A social network consists of events and individuals, in which the events denote the activities happening in the system and the individuals denotes the peoples who are attracted into the activities. A memory feature exists in a dynamic social network which leads to the decay of the event attraction, and further influences the structure and the dynamics of the network. In the paper, an agent model for a social memory network is built and implemented. The simulation result reveals the dynamics of the average life span of events. The result also discovers how a social network with a small "diameter" and a large clustering coefficient evolves. The model is validated with the empirical data from USTC bulletin board system (BBS).

In this talk, we will discuss the roles and potential implications of autonomy-oriented computing (AOC) in/to the future of Web intelligence (WI) and brain informatics (BI). Generally speaking, AOC is a methodology for self-organized computing that is well suited for two types of applications: (i) to characterize the working mechanisms that lead to certain emergent behavior in natural and artificial complex systems (e.g., phenomena in ldquoWeb Sciencerdquo, and the dynamics of social networks and neural systems), and (ii) to develop solutions to large-scale, distributed computational problems (e.g., distributed scalable scientific or social computing, and collective intelligence). AOC emphasizes the modeling of autonomous entities or agents that locally interact following certain nature or real-world inspired behavioral rules, resulting in some self-organized behavior of the entities and/or their nonlinearly aggregated effects. Computing based on interacting entities and their self-organization can offer several means as well as advantages for WI and BI development, such as natural formulation, distributed implementation, scalable performance, robustness, and behavioral or first-principle understanding.

Crawling deep web is the process of collecting data from search interfaces by issuing queries. With wide availability of programmable interface encoded in Web services, deep web crawling has received a large variety of applications. One of the major challenges crawling deep web is the selection of the queries so that most of the data can be retrieved at a low cost. We propose a general method in this regard. In order to minimize the duplicates retrieved, we reduced the problem of selecting an optimal set of queries from a sample of the data source into the well-known set-covering problem and adopt a classical algorithm to resolve it. To verify that the queries selected from a sample also produce a good result for the entire data source, we carried out a set of experiments on large corpora including Wikipedia and Reuters. We show that our sampling-based method is effective by empirically proving that 1) The queries selected from samples can harvest most of the data in the original database; 2) The queries with low overlapping rate in samples will also result in a low overlapping rate in the original database; and 3) The size of the sample and the size of the terms from where to select the queries do not need to be very large.

The term of social network communities refers to groups of individuals within which social interactions are intense and between which they are weak. A social network community mining problem (SNCMP) can be stated as the problem of finding all such communities from a given social network. A wide variety of applications can be formulated into SNCMPs, ranging from Web intelligence to social intelligence. So far, many algorithms addressing the SNCMP have been developed; most of them are either optimization or heuristic based methods. Different from all existing work, this paper explores the notion of a social network community and its intrinsic properties, drawing on the dynamics of a stochastic model naturally introduced. In particular, it uncovers an interesting connection between the hierarchical community structure of a network and the metastability of a Markov process constructed upon it. A lot of critical topological information regarding to communities hidden in networks can be inferred from the derived spectral signatures of such networks, without actually clustering them with any particular algorithms. Based upon the above connection, we can obtain a frameworkfor characterizing and analyzing social network communities.

One of the central problems in studying and understanding complex networks, such as online social networks or World Wide Web, is to discover hidden, either physically (e.g., interactions or hyperlinks) or logically (e.g., profiles or semantics) well-defined topological structures. From a practical point of view, a good example of such structures would be so-called network communities. Earlier studies have introduced various formulations as well as methods for the problem of identifying or extracting communities. While each of them has pros and cons as far as the effectiveness and efficiency are concerned, almost none of them has explicitly dealt with the potential relationship between the global topological property of a network and the local property of individual nodes. In order to study this problem, this paper presents a new algorithm, called ICS, which aims to discover natural network communities by inferring from the local information of nodes inherently hidden in networks based on a new centrality, that is, clustering centrality, which is a generalization of eigenvector centrality. As compared with existing methods, our method runs efficiently with a good clustering performance. Additionally, it is insensitive to its built-in parameters and prior knowledge.

The goal of an on-line ontology-based question-answering system is to automatically derive answers from ontology knowledge bases without demanding additional information or intervention from users. This paper focuses on the problem of automatically mapping the tokens of a question into OWL elements, as an important step towards the further construction of answers. This problem can be essentially viewed as that of question understanding. The basic ideas underlying our method can be stated as follows: first we translate the tokens of a question as well as their syntactical and semantic relations (as in NLP) into constrained question variables and functions, and thereafter, we utilize an optimization-based assigning mechanism to substitute the question variables with the corresponding constructs in OWL knowledge bases. In the paper, we discuss our preliminary studies using the questions collected from, and the knowledge base built at, the International WIC Institute (WICI).

We propose a market mechanism that can be implemented on clustering aggregation problem among selfish systems, which tend to lie about their correct clustering during aggregation process. Our study is the preliminary step toward the development of robust distributed data mining among selfish systems.

High dimensionality of POMDP's belief state space is one major cause that makes the underlying optimal policy computation intractable. Belief compression refers to the methodology that projects the belief state space to a low-dimensional one to alleviate the problem. In this paper, we propose a novel orthogonal non-negative matrix factorization (O-NMF) for the projection. The proposed O-NMF not only factors the belief state space by minimizing the reconstruction error, but also allows the compressed POMDP formulation to be efficiently computed (due to its orthogonality) in a value-directed manner so that the value function will take same values for corresponding belief states in the original and compressed state spaces. We have tested the proposed approach using a number of benchmark problems and the empirical results confirms its effectiveness in achieving substantial computational cost saving in policy computation.

Although some preliminary spatial localization results have been reported, the temporal characteristics of human inductive reasoning process have not been investigated. In the present study, event-related potential (ERP) was used to explore the time course of inductive reasoning process. Based on pilot studies and some other related research, we hypothesized that the process of numerical inductive reasoning is composed of number recognition, strategy formation, hypothesis generation and validation, and the above three stages are (partially) dissociable over time. A typical task of inductive reasoning, function-finding, was adopted. Induction tasks and calculation tasks were performed in the experiments, respectively. The mean reaction time of induction tasks was much longer than that of calculation tasks as expected. Statistical analysis revealed that induction showed no significant separations from calculation for the early ERP components and the slow waveforms after about 600ms, while marked dissociations appeared for the late components in the time window of about 250-600ms. It can be preliminarily concluded that, the early components before about 250ms may reflect the process of attention and number recognition, the late components may relate to strategy formation, and hypothesis generation and validation may be performed in about 600-1200ms. On the whole, the results on the behavioral data and ERP data support our hypothesis.

The 0-1 quadratic knapsack problem (QKP) is a hard computational problem, which is a generalization of the knapsack problem (KP). In this paper, a mini-swarm system is presented. Each agent, realized with minor declarative knowledge and simple behavioral rules, searches on a structural landscape of the problem through the guided generate-and-test behavior under the law of socially biased individual learning, and cooperates with others by indirect interactions. The formal decomposition of behaviors allows understanding and reusing elemental operators, while utilizes the heuristic information on the landscape. The results on a collection of the QKP instances by mini-swarm versions are compared with that of both a branch-and-bound algorithm and a greedy genetic algorithm, which show its effectiveness

A social network is composed of social individuals and their relationships. In many real-world applications, such a network will evolve dynamically over time and events. A social network can be naturally viewed as a multiagent system if considering locally-interacting social individuals as autonomous agents. In this paper, we present an Autonomy-Oriented Computing (AOC) based model of a social network, and study the dynamics of the network based on this model. In the AOC model, the profile of agents, service-based interactions, and the evolution of the network are defined, and the autonomy of the agents is emphasized. The model can reveal dynamic relationships among global performance, local interaction (partner selection) strategies, and network topology. The experimental results show that the agent network forms a community with a high clustering coefficient, and the performance of the network is dynamically changing along with the formation of the network and the local interaction strategies of the agents. In this paper, the performance and topology of the agent network are analyzed, and the factors that affect the performance and evolution of the agent network are examined.

Many complex systems in the real world can be modeled as signed social networks that contain both positive and negative relations. Algorithms for mining social networks have been developed in the past, however most of them were designed primarily for networks containing only positive relations and thus not suitable for signed networks. In this work, we propose a new algorithm, called FEC, to mine signed social networks so that both positive within-group relations and negative between-group relations are dense. FEC considers both the sign and the density of relations as the clustering attributes, making itself effective for not only signed networks but also conventional social networks including only positive relations. Also, FEC adopts an agent-based heuristic that makes the algorithm efficient (in linear time with respect to the size of a network) and capable of giving nearly optimal solutions. FEC depends on only one parameter whose value can easily be set, and requires no prior knowledge on hidden community structures. The effectiveness and efficacy of FEC have been demonstrated through a set of rigorous experiments involving both benchmark and randomly-generated signed networks.

Recently, research on social network and Web intelligence (WI) has shown that social intelligence techniques act as the imperative channel for automated email-centric tasks. This paper gives a complete picture of what can we do in the global social e-mail network and how to do. Our main contributions include: (1) we describe two mechanisms for implementing applications in the global social e-mail network; (2) we design operable e-mail for communicating in that network. To our best knowledge, it is the first time to discuss how to implement social intelligence in such a network under the notion of WI. We believe that this work consequentially explores a new and absolutely necessarily needed research field of WI

A social network can be modelled by a multi-agent system, in which the interaction among agents is represented as a service transaction process. In this paper, we present a service-based agent network to simulate and study the dynamics of social networks. In the network, the profiles of agents and service-based interactions are defined deliberately. Autonomy is emphasized as the ability of agents to manage their behaviors according to the local environment and their profiles. The experimental results reveal that network performance, network topology and the profiles of agents all evolve along with local behaviors. The over-shoot phenomenon in the evolution of network is discovered and analyzed. The discoveries are meaningful for understanding the relationship between network dynamics and local behaviors

In order to meet the on-demand requirement of service composition at a large scale, one should go beyond the use of static domain ontologies but allow different focused aspects of the ontologies to be distributed as sub-ontologies. To demonstrate the feasibility of the sub-ontology idea, we suggest a possible implementation using the semantic Web technology and apply it to distributed e-learning.

This paper addresses the distributed resource optimization issue in heterogeneous Web environments, where both resource nodes and service requests may be heterogeneous. Specifically, this paper presents an agent-based mechanism, where agents are employed to carry service requests. Agents are equipped with three behaviors, namely, least-loaded move, less-loaded move, and random move, to search for appropriate resource nodes. Every time, agents probabilistically choose a behavior to perform. As a whole, the multiagent system can accomplish the objective of load balancing and resource optimization. Through experiments on a computing platform, called SSADRO, we validate the effectiveness of the proposed mechanism. As compared to our previously proposed load balancing mechanism in Liu, Jin and Wang, (2005), the one in this paper can address dynamic load balancing in heterogeneous environments.

One of the key research challenges that we will face in developing the Wisdom Web is to make it capable of seamlessly offering solutions to users in dealing with their real-world problems. In order to make this possible, individual contents or services should be developed and written following the syntax and semantics of a pre-defined method for distributed problem solving on the Web. In this paper, we propose a new method for solving problems in a large-scale distributed Web environment. We will also give an illustrative example in this paper to show the service process of the new method.

The next generation Web Intelligence (WI) aims at enabling users to go beyond the existing online information search and knowledge queries functionalities and to gain, from the Web, practical wisdom for problem solving. To support such a Wisdom Web, we envision that a grid‐like computing infrastructure with intelligent service agencies is needed, where these agencies can interact, self‐organize, learn, and evolve their course of actions, identities, and interrelationships for new knowledge creation, as well as scientific and social evolution. In this paper, we first provide an overview of recent development in WI and Semantic/Knowledge Grid. Then, the fundamental capabilities of the Wisdom Web as well as the conceptual architecture of an intelligent Grid for supporting it are described. Technical challenges for realizing Grid Intelligence are highlighted and the recent advancements in related research areas are reviewed.

In this letter, a new nonlinear approach based on a combination of the fuzzy c-means clustering (FCMC), feature vector selection and principal component analysis (PCA) is proposed to extract features of multispectral images when a very large number of samples need to be processed. The main contribution of this letter is to provide a preprocessing method for classifying these images with higher accuracy compared to the single PCA and kernel PCA. Finally, some experimental results demonstrate that our proposed approach is effective and efficient in analyzing multispectral images.

In this paper, we present a macroscopic-characterization of agent-based load balancing in homogeneous minigrid environments. The agent-based load balancing is regarded as agent distribution from a macroscopic point of view. We study two quantities on minigrids: the number and size of teams where agents (tasks) queue. In macroscopic modeling, the load balancing mechanism is characterized using differential equations. We show that the load balancing we concern always converges to a steady state. Furthermore, we show that load balancing with different initial distributions converges to the same steady state gradually. Also, we prove that the steady state becomes an even distribution if and only if agents have complete knowledge about agent teams on minigrids. Utility gains and efficiency are introduced to measure the quality of load balancing. Through numerical simulations, we discuss the utility gains and efficiency of load balancing in different cases and give a series of analysis. In order to maximize the utility gain and the efficiency, we theoretically study the optimization of agents' strategies. Finally, in order to validate our proposed agent- based load balancing mechanism, we develop a computing platform, called simulation system for grid task distribution (SSGTD). Through experimentation, we note that our experimental results in general confirm our theoretical proofs and numerical simulation results from the proposed equation system. In addition, we find a very interesting phenomenon, that is, agent-based load balancing mechanism is topology-independent.

Autonomous multientity systems are plentiful in natural and artificial worlds. Many systems have been studied in depth and some models of them have been built as computational systems for problem solving. Central to these computational systems is the notion of autonomy. This article surveys research work done along this direction and presents autonomy-oriented computing (AOC) as a paradigm to describe systems for solving hard computational problems and for characterizing the behaviors of a complex system. AOC differs from major complex-system-related studies such as artificial life, simulated evolution, and multiagent systems in that AOC is not just intended to replicate complex behavior, emulate evolution, or coordinate the functioning of many interacting agents. AOC emphasizes the modeling of autonomy in the entities of a complex system and the self-organization of them in achieving a specific goal. Through implemented applications, we describe three main approaches to AOC, as well as an AOC framework with formal definitions of essential constructs and their interrelationships, including the notions of emergent autonomy, self-organization, and the interactions among entities and environment.

Web services are becoming important in applications from electronic commerce to application interoperation. While numerous efforts have focused on service composition, service selection among similar services from multiple providers has not been addressed. Such issue is more serious when services are embraced in Grid platforms, which are usually resource-conscious. Experimental results show that our considerations are valid and our preliminary solution works well in our Globus grid network.

While numerous efforts have focused on service composition in the Grid environment, service selection among similar services from multiple providers has not been addressed. In particular, all service composition work done so far are based on a given selection of services under a well set environment. As a result, uncertainty (e.g., server load, network traffic, computation time of the services due to changing memory and other unexpected conditions) under a real, dynamic environment has never been considered. This paper prototypes the service selection under a Grid environment and proposes an uncertainty framework to address the issue. Experimental results show that our considerations are valid and our preliminary solution works well in our Globus Grid network.

The Centre for e-Transformation Research (CTR), also an affiliated Centre of Web Intelligence Consortium (WIC), is established under the Science Faculty of Hong Kong Baptist University, currently funded by Hong Kong Research Grant Council Central Allocation and FRG Strategic Research Grant, Hong Kong Baptist University for developing an Area of Strength in e-transformation research, making high impact to various sectors of the society, from e-business, e-learning, to e-government, to name a few.

The World Wide Web is one of the most popular applications currently running on the Internet, and its size is growing exponentially. Web caching is an important technique that aims to reduce network traffic, server load, and user-perceived retrieval delays by replicating popular contents on proxy servers. Anycast is a new network service widely used for providing auto-configuration and load-balancing. We present an anycast-based cooperative proxy algorithm (ACPA) that brings a server ienearestle to a client to improve overall performance by selective allowing duplicates and migrate objects to other proxies based on request pattern. Analytical and experimental results show that the algorithm outperforms a hash-based algorithm in response time and hop counts.

In this paper, we describe a new evolutionary computation approach, called multiphase genetic programming (MPGP). The special features of this approach lie in its variable-granularity representations of chromosomes and their corresponding genetic operations. In the paper, we provide an overview of the MPGP approach as well as details on how the sumo maneuver evolution experiments are carried out and how the MPGP-based case study differs from others.

Researchers have recently discovered several interesting, self-organized regularities from the World Wide Web, ranging from the structure and growth of the Web to the access patterns in Web surfing. What remains to be a great challenge in Web log mining is how to explain user behavior underlying observed Web usage regularities. We address the issue of how to characterize the strong regularities in Web surfing in terms of user navigation strategies, and present an information foraging agent-based approach to describing user behavior. By experimenting with the agent-based decision models of Web surfing, we aim to explain how some Web design factors as well as user cognitive factors may affect the overall behavioral patterns in Web usage.

With the advent of the World Wide Web, providing just-in-time personalized product recommendations to customers now becomes possible. Collaborative recommender systems utilize correlation between customer preference ratings to identify "like-minded" customers and predict their product preference. One factor determining the success of the recommender systems is the prediction accuracy, which in many cases is limited by lacking adequate ratings (the sparsity problem). Recently, the use of latent class model (LCM) has been proposed to alleviate this problem. In this paper, we first study how the LCM can be extended to handle customers and products outside the training set. In addition, we propose the use of a pair of LCMs (called dual latent class model-DLCM), instead of a single LCM, to model customers' likes and dislikes separately for enhancing the prediction accuracy. Experimental results based on the EachMovie dataset show that DLCM outperforms both LCM and the conventional correlation-based method when the available ratings are sparse.

This paper introduces an adaptive algorithm for distributed caching based on the idea of autonomous proxy caches without the usage of a central coordinator or broadcasting protocol. We show that the algorithm outperforms existing approaches based on hashing algorithms in hot-spot scenarios and common power-law request patterns.

This article proposes a new population-based stochastic search algorithm called evolutionary diffusion optimization (EDO) inspired by diffusion in nature. Each entity in EDO makes the decision to diffuse based on the information shared between its parent and its siblings. The behavior of EDO when solving a typical optimization problem is also discussed.

A new population-based stochastic search algorithm called evolutionary diffusion optimization (EDO) inspired by diffusion in nature has been proposed. This article compares the performance of EDO with simulated annealing and fast evolutionary programming. Experimental results show that EDO performs better than SA and FEP in some cases.

Current attempts to analyze international financial markets include the use of financial technical analysis and data mining techniques. In this paper, we propose a new approach that incorporates implication networks and association rules to form an associated network structure. The proposed approach explicitly addresses the issue of local vs. global influences between financial markets.

In this paper, we extend and modify the ERA approach proposed in Ref. 13 to solve Propositional Satisfiability Problems (SATs). The new ERA approach involves a multiagent system where each agent only senses its local environment and applies some self-organizing rules for governing its movements. The environment, which is a two-dimensional cellular environment, records and updates the local values that are computed and affected according to the movements of individual agents. In solving a SAT with the ERA approach, we first divide variables into several groups, and represent each variable group with an agent whose possible positions correspond to the elements in a Cartesian product of variable domains, and then randomly place each agent onto one of its possible positions. Thereafter, the ERA system will keep on dispatching agents to choose their movements until an exact or approximate solution emerges. The experimental results on some benchmark SAT test-sets have shown that the ERA approach can obtain comparable results as well as stable performances for SAT problems. In particular, it can find approximate solutions for SAT problems in only a few steps. The real value of this approach is that it is a distributed asynchronous approach without any centralized control or evaluation, where the agents can cooperate to solve problems without explicit communication.

This article proposes a novel multiagent approach to optimization inspired by diffusion in nature called Evolutionary Multiagent Diffusion (EMD). Each agent in EMD makes the decision to diffuse based on the information shared between its parent and its siblings. The behavior of EMD is analyzed and its relation to similar search algorithms is discussed.

This paper is concerned with the dynamics of autonomous agents in performing distributed problem-solving tasks. The goal of this work is to show: 1) how certain tasks may be handled by breeds of distributed agents self-reproduced by other agents in response to their local environment and 2) how the behavioral repository of the agents may be constructed based on some well-defined dynamical systems models. The breeds of agents progressively generated in the course of distributed problem-solving are referred to as agentlets. The specific task for demonstrating this dynamical systems-based agentlet-oriented approach is the one in which the agents are required to search and mark certain feature locations in a two-dimensional (2-D) search space by way of divide-and-conquer. In so doing, individual agents may have different dynamical motion, depending on when and where they are bred. This paper provides a detailed description of the agents of different dynamics and shows how the agentlets proceed with this task by moving according to their well-defined dynamics, breeding their offspring agents in the environment., and fine-tuning their dynamical systems parameters. In addition, it is proven that in the given example task, the designed agentlets will guarantee to reach all the feature locations in the search space.

This paper presents a new approach to solving N-queen problems, which involves a model of distributed autonomous agents with artificial life (ALIFE) and a method of representing N-queen constraints in an agent environment. The distributed agents locally interact with their living environment, i.e. a chessboard, and execute their reactive behaviors by applying their behavioral rules for randomized motion, least-conflict position searching, and cooperating with other agents, etc. The agent-based N-queen problem solving system evolves through selection and contest, in which some agents will die or be eaten if their moving strategies are less effective than others. The experimental results have shown that this system is capable of solving large-scale N-queen problems. This paper also provides a model of ALIFE agents for solving general CSPs.

A novel approach based on cubic B-spline wavelet transform is proposed to process Chinese character including character compression, type zooming-in, and typeface composition. The basic idea is that a Chinese character is described by its contours which are represented by cubic B-spline functions, and each contour is decomposed into the details or the control points (wavelet coefficients) at different resolution levels. For character compression, there are two methods, one directly treats the details of wavelet coefficients and the other considers the sub-curves piecing together at the different resolution levels. In the type zooming-in, the wavelet reconstruction is used to scale the Chinese character with arbitrary size and the wavelet filter is used to improve the quality of the enlarged type. For typeface composition, the new style typefaces of Chinese character are obtained by editing and modifying the details at different resolution levels. The concrete algorithms are also given as well as the experimental results.

We are concerned with the problem of measuring the uncertainty in a broad class of belief networks, as encountered in evidential reasoning applications. In our discussion, we give an explicit account of the networks concerned, and call them the Dempster-Shafer (D-S) belief networks. We examine the essence and the requirement of such an uncertainty measure based on well-defined discrete event dynamical systems concepts. Furthermore, we extend the notion of entropy for the D-S belief networks in order to obtain an improved optimal dynamical observer. The significance and generality of the proposed dynamical observer of measuring uncertainty for the D-S belief networks lie in that it can serve as a performance estimator as well as a feedback for improving both the efficiency and the quality of the D-S belief network-based evidential inferencing. We demonstrate, with Monte Carlo simulation, the implementation and the effectiveness of the proposed dynamical observer in solving the problem of evidential inferencing with optimal evidence node selection.

The 21st century is the age of the Internet and the World Wide Web. The Web revolutionizes the way we gather, process, and use information. At the same time, it also redefines the meanings and processes of business, commerce, marketing, finance, publishing, education, research, development, as well as other aspects of our daily life. The revolution is just beginning. Although individual Web based information systems are constantly being deployed, advanced issues and techniques for developing and for benefiting from Web intelligence still remain to be systematically studied. The article defines a new research field, namely Web Intelligence (WI) by giving a complete picture of WI related topics for systematic study on advanced Web technology and developing Web based intelligent information systems. Roughly speaking, WI exploits AI and advanced information technology on the Web and Internet. It is the key and the most urgent research field of IT for business intelligence.

This paper aims at studying the characterization of Dirac-structure edges with wavelet transform, and selecting the suitable wavelet functions to detect them. Three significant characteristics of the local maximum modulus of the wavelet transform with respect to the Dirac-structure edges are presented: (1) slope invariant: the local maximum modulus of the wavelet transform of a Dirac-structure edge is independent on the slope of the edge; (2) grey-level invariant: the local maximum modulus of the wavelet transform with respect to a Dirac-structure edge takes place at the same points when the images with different grey-levels are processed; and (3) width light-dependent: for various widths of the Dirac-structure edge images, the location of maximum modulus of the wavelet transform varies lightly under the certain circumscription that the scale of the wavelet transform is larger than the width of the Dirac-structure edges. It is important, in practice, to select the suitable wavelet functions, according to the structures of edges. For example, Haar wavelet is better to represent brick-like images than other wavelets. A mapping technique is applied in this paper to construct such a wavelet function. In this way, a low-pass function is mapped onto a wavelet function by a derivation operation. In this paper, the quadratic spline wavelet is utilized to characterize the Dirac-structure edges and a novel algorithm to extract the Dirac-structure edges by wavelet transform is also developed.

The paper addresses the problem of automatically programming cooperative behaviors in a group of autonomous robots. The specific task that we consider here is for a group of distributed autonomous robots to cooperatively push an object toward a goal location. The difficulty of this task lies in that the task configurations of the robots with respect to the object do not follow any explicit, global control command, primarily due to certain modeling limitations as well as planning costs as in many real life applications. In such a case, it is important that the individual robots locally modify their motion strategies, and at the same time, create a desirable collective interaction between the distributed robot group and the object that can successfully bring the object to the goal location. In order to solve this problem, we have developed an evolutionary computation approach in which no centralized modeling and control is involved except a high level criterion for measuring the quality of robot task performance. The evolutionary approach to distributed robot behavioral programming is based on a fittest preserved genetic algorithm that takes into account the current positions and orientations of the robots relative to the object and the goal, and a weak global feedback on the collective task performing effect in relation to the goal if some new local motion strategies are employed by the robots.

This paper is concerned with two issues: (1) how to enable distributed robots to dynamically acquire their goal-directed collective behaviors, and (2) how to apply the methodology of collective behavioral learning to solve the world modeling problems in mobile robot navigation. We have developed an evolutionary self-organization approach to collective task handling, and furthermore, demonstrated the implemented approach in tackling the specific problem of collectively constructing a global spatial representation, i.e., an artificial potential field map, in an unknown environment.

This paper describes a dual-agent system capable of learning eye-body-coordinated maneuvers in playing a sumo contest. The two agents rely on each other by either offering feedback information on the physical performance of a certain selected maneuver or giving advice on candidate maneuvers for an improvement over the previous performance. At the core of this learning system lies in a multi-phase genetic-programming approach that is aimed to enable the player to gradually acquire sophisticated sumo maneuvers. As illustrated in the sumo learning experiments involving opponents of complex shapes and sizes, the proposed multi-phase learning allows the development of specialized strategic maneuvers based on the general ones, and hence demonstrates the efficiency of maneuver acquisition. We provide details of the problem addressed and the implemented solutions concerning a mobile robot for performing sumo maneuvers and the computational assistant for coaching the robot. In addition, we show the actual performances of the sumo agent, as a result of coaching, in dealing with a number of difficult sumo situations.

In this paper, a novel approach based on the wavelet orthonormal decomposition is presented to extract features in pattern recognition. The proposed approach first reduces the dimensionality of a two-dimensional pattern, and thereafter performs wavelet transform on the derived one-dimensional pattern to generate a set of wavelet transform subpatterns, namely, several uncorrelated functions. Based on these functions, new features are readily computed to represent the original two-dimensional pattern. As an application, experiments were conducted using a set of printed characters with varying orientations and fonts. The results obtained from these experiments have consistently shown that the proposed feature vectors can yield an excellent classification rate in pattern recognition.

Presents an autonomous agent-based image segmentation approach. In this approach, a digital image is viewed as a two-dimensional cellular environment which the agents inhabit and attempt to label homogeneous segments. In so doing, the agents rely on some reactive behaviors such as breeding and diffusion. The agents that are successful in finding the pixels of a specific homogeneous segment will breed offspring agents inside their neighboring regions. Hence, the offspring agents will become likely to find more homogeneous-segment pixels. In the mean time, the unsuccessful agents will be inactivated, without further search in the environment.

In Chinese document image processing, text and/or graphical block detection serves as an essential step in document layout analysis that in turn permits the effective reasoning about the logical relationships among various text paragraphs and graphical entities for the purpose of document understanding. This paper presents a novel computational paradigm for extracting text/graphic blocks from Chinese document images, which is based on a notion of distributed autonomous agents. The primary features of the agents lie in that they are (1) adaptive to the locality of given images and hence efficient in locating the homogeneous image blocks, (2) reliable in performing image processing as the computation proceeds simultaneously from different image locations, (3) less sensitive to the noise in the given images as the computation disperses gracefully when it is moving away from the homogeneous blocks, and (4) easy to represent in their behaviors and evolvable in their performance. The paper, first of all, describes the formalisms as well as the behavioral characteristics of the agents, which is followed by a demonstration of the agents in detecting document blocks from some real-life images.

In this paper, an off-line recognition system based on multifeature and multilevel classification is presented for handwritten Chinese characters. Ten classes of multifeatures, such as peripheral shape features, stroke density features, and stroke direction features, are used in this system. The multilevel classification scheme consists of a group classifier and a five-level character classifier, where two new technologies, overlap clustering and Gaussian distribution selector are developed. Experiments have been conducted to recognize 5,401 daily-used Chinese characters. The recognition rate is about 90 percent for a unique candidate, and 98 percent for multichoice with 10 candidates.

An automatic form information acquisition and storage system is presented. By semantic meaning analysis and registration of every king of forms in advance, the system as able to recognize incoming forms and extract information from them automatically. An efficient form image storage method is also proposed. Instead of keeping the entire form image, this system greatly reduces the memory needed to store the form images in a database by extracting and storing user filled data images only.

The paper presents a wavelet based approach to edge detection in document processing. According to local analysis of the document images using wavelet theory, a novel method is developed to detect the edges in document processing, including extraction of the contours of characters and extraction of the reference lines in the form document images with gray levels. In this method, the quadratic spline wavelet is utilized. Experiments have been contacted. The positive results show the effectiveness of the application of the quadratic spline wavelet to edge detection, especially to extract the reference lines and image boundaries in document processing.

Based on wavelets, a theoretical method has been developed to process multi-gray level documents. In this method, two-dimensional multiresolution analysis, a wavelet decomposition algorithm, and compactly supported orthonormal wavelets are used to transform a document image into sub-images. According to these sub-images, the reference lines of a multi-gray level document can be extracted, and knowledge about the geometric structure of the document can be acquired. Particularly, this approach is more efficient to process form documents with gray level background. Experiments indicate that this new method can be applied to process documents with promising results.

This paper presents a new approach to image feature extraction which utilizes evolutionary autonomous agents. Image features are often mathematically defined in terms of the gray-level intensity at image pixels. The optimality of image feature extraction is to find all the feature pixels from the image. In the proposed approach, the autonomous agents, being distributed computational entities, operate directly in the 2-D lattice of a digital image and exhibit a number of reactive behaviors. To effectively locate the feature pixels, individual agents sense the local stimuli from their image environment by means of evaluating the gray-level intensity of locally connected pixels, and accordingly activate their behaviors. The behavioral repository of the agents consists of: 1) feature-marking at local pixels and self-reproduction of offspring agents in the neighboring regions if the local stimuli are found to satisfy feature conditions, 2) diffusion to adjacent image regions if the feature conditions are not held, or 3) death if the agents exceed their life span. As part of the behavior evolution, the directions in which the agents self-reproduce and/or diffuse are inherited from the directions of their selected high-fitness parents. Here the fitness of a parent agent is defined according to the steps that the agent takes to locate an image feature pixel.

The paper describes an algorithmic means for inducing implication networks from empirical data samples. The induced network enables efficient inferences about the values of network nodes if certain observations are made. This implication induction method is approximate in nature as probabilistic network requirements are relaxed in the construction of dependence relationships based on statistical testing. In order to examine the effectiveness and validity of the induction method, several Monte Carlo simulations were conducted, where theoretical Bayesian networks were used to generate empirical data samples-some of which were used to induce implication relations, whereas others were used to verify the results of evidential reasoning with the induced networks. The values in the implication networks were predicted by applying a modified version of the Dempster-Shafer belief updating scheme. The results of predictions were, furthermore, compared to the ones generated by Pearl's (1986) stochastic simulation method, a probabilistic reasoning method that operates directly on the theoretical Bayesian networks. The comparisons consistently show that the results of predictions based on the induced networks would be comparable to those generated by Pearl's method, when reasoning in a variety of uncertain knowledge domains-those that were simulated using the presumed theoretical probabilistic networks of different topologies.

This paper describes a generic document segmentation and geometric relation labeling method with applications to document analysis. Unlike the previous document segmentation methods where text spacing, border lines, and/or a priori layout models based template processing are performed, the present method begins with a hierarchy of partitioned image layers where inhomogeneous higher-level regions are recursively positioned into lower-level rectangular subregions and at the same time lower-level smaller homogeneous regions are merged into larger homogeneous regions. The present method differs from the traditional split-and-merge segmentation method in that it orthogonally splits regions using thresholds adaptively computed from projection profiles.

In this paper, we present a novel approach to optical character recognition that utilizes ring-projection-wavelet-fractal-signatures. In particular, the proposed approach reduces the dimensionality of a two-dimensional pattern by way of a ring-projection method, and thereafter, performs Daubechies' wavelet transform on the derived one-dimensional pattern to generate a set of wavelet sub-patterns, namely, curves that are non-self intersecting. Further from the resulting non-self intersecting curves, the divider dimensions are readily computed. These divider dimensions constitute a new characteristic vector for the original two-dimensional pattern, defined over the curves' fractal dimensions.

This paper describes an approach for constructing consistent observers for dynamic systems based on a formalism of nondeterministic event modeling (NEM). The first part of this paper establishes the definitions of NEM with a main focus on the notion of entropy that is extended for measuring the amount of information from nondeterministic events. The paper demonstrates the importance of the proposed entropy measure in contrast to the classical uncertainty measure when used in dynamic systems. The importance of the information measure stems from a potential failure of the classical uncertainty when observing nondeterministic events. Similar problems, which we describe as unobservable states, are often seen in dynamic systems where an uncertainty measure is used in conjunction with some arbitrary decision process. Based on well-defined dynamic systems concepts, the second part of the paper formulates the notion of consistent observer for nondeterministic event modeling. The consistent observer utilizes the monotonically decreasing entropy function of nondeterministic events. An example will be given in this paper which numerically illustrates the notions of NEM and consistent observer.

In this paper, we delineate several task-level operations an the context of robotic assembly, and show how these operations can be organized in the form of a task grammar. The proposed task grammar captures the intrinsic principle on how the sequence of robot operations should be ordered and how one high-level operation can be effectively decomposed into low-level operations. In order to control the process of robot task decomposition, we explicitly represent and apply qualitative heuristic knowledge about task constraints and operation applicability.

A qualitative geometric reasoning approach to the analysis of robot task kinematics is presented. Qualitative geometric reasoning refers to the process of deriving a solution based on a set of geometric rules in which the concepts are described in terms of symbolic qualitative values and partial-ordering relations. The qualitative kinematic analysis scheme permits computationally efficient approximate solutions of kinematic problems without using exact information on the geometry of mechanisms under consideration, and provides a basis for the functional simulation of mechanisms.>

Presents a qualitative reasoning approach to synthesizing robot motion plans from task-level specifications. This method relies on representing the knowledge about robot manipulation as a task grammar augmented with a domain-dependent task analyzer. The task analyzer tests constraints for deriving suboperations pertaining to a higher-level operation and performs commonsense reasoning about the manipulator-level motion strategies. Through several examples, the authors show how syntactical knowledge about robot operations can be formulated for real-world manipulation tasks and how commonsense knowledge can be augmented to constrain the syntactical reasoning.>

For pt.I see ibid., p.487-93 (1991). As augmentations to syntactical task planning, kinematic models facilitate the specification of robot-level motion strategies for mechanism-oriented manipulation tasks. The paper presents a qualitative geometric reasoning approach to the analysis of robot task kinematics. The qualitative approach permits computationally efficient, approximate, solution of kinematic problems without using exact information on the geometry of mechanisms and provides a basis for the functional simulation of robot manipulation. >