Search

Temporal causal discovery is a crucial task aimed at uncovering the causal relations within time series data. The latest temporal causal discovery methods usually train deep learning models on prediction tasks to uncover the causality between time series. They capture causal relations by analyzing the parameters of some components of the trained models, e.g., attention weights and convolution weights. However, this is an incomplete mapping process from the model parameters to the causality and fails to investigate the other components, e.g., fully connected layers and activation functions, that are also significant for causal discovery. To facilitate the utilization of the whole deep learning models in temporal causal discovery, we proposed an interpretable transformer-based causal discovery model termed CausalFormer, which consists of the causality-aware transformer and the decomposition-based causality detector. The causality-aware transformer learns the causal representation of time series data using a prediction task with the designed multi-kernel causal convolution which aggregates each input time series along the temporal dimension under the temporal priority constraint. Then, the decomposition-based causality detector interprets the global structure of the trained causality-aware transformer with the proposed regression relevance propagation to identify potential causal relations and finally construct the causal graph. Experiments on synthetic, simulated, and real datasets demonstrate the state-of-the-art performance of CausalFormer on discovering temporal causality. Our code is available at https://github.com/lingbai-kong/CausalFormer.

This paper is an extended abstract of our original work published in KDD23, where we won the best research paper award (Xiangguo Sun, Hong Cheng, Jia Li, Bo Liu, and Jihong Guan. All in one: Multi-task prompting for graph neural networks. KDD 23) The paper introduces a novel approach to bridging the gap between pre-trained graph models and the diverse tasks they're applied to, inspired by the success of prompt learning in NLP. Recognizing the challenge of aligning pre-trained models with varied graph tasks (node level, edge level, and graph level), which can lead to negative transfer and poor performance, we propose a multi-task prompting method for graphs. This method involves unifying graph and language prompt formats, enabling NLP's prompting strategies to be adapted for graph tasks. By analyzing the task space of graph applications, we reformulate problems to fit graph-level tasks and apply meta-learning to improve prompt initialization for multiple tasks. Experiments show our method's effectiveness in enhancing model performance across different graph tasks. Beyond the original work, in this extended abstract, we further discuss the graph prompt from a bigger picture and provide some of the latest work toward this area., Comment: submitted to IJCAI 2024 Sister Conferences Track. The original paper can be seen at arXiv:2307.01504

Molecular property prediction (MPP) is a fundamental but challenging task in the computer-aided drug discovery process. More and more recent works employ different graph-based models for MPP, which have made considerable progress in improving prediction performance. However, current models often ignore relationships between molecules, which could be also helpful for MPP. For this sake, in this paper we propose a graph structure learning (GSL) based MPP approach, called GSL-MPP. Specifically, we first apply graph neural network (GNN) over molecular graphs to extract molecular representations. Then, with molecular fingerprints, we construct a molecular similarity graph (MSG). Following that, we conduct graph structure learning on the MSG (i.e., molecule-level graph structure learning) to get the final molecular embeddings, which are the results of fusing both GNN encoded molecular representations and the relationships among molecules, i.e., combining both intra-molecule and inter-molecule information. Finally, we use these molecular embeddings to perform MPP. Extensive experiments on seven various benchmark datasets show that our method could achieve state-of-the-art performance in most cases, especially on classification tasks. Further visualization studies also demonstrate the good molecular representations of our method.

Single-cell RNA sequencing (scRNA-seq) enables researchers to analyze gene expression at single-cell level. One important task in scRNA-seq data analysis is unsupervised clustering, which helps identify distinct cell types, laying down the foundation for other downstream analysis tasks. In this paper, we propose a novel method called Cluster-aware Iterative Contrastive Learning (CICL in short) for scRNA-seq data clustering, which utilizes an iterative representation learning and clustering framework to progressively learn the clustering structure of scRNA-seq data with a cluster-aware contrastive loss. CICL consists of a Transformer encoder, a clustering head, a projection head and a contrastive loss module. First, CICL extracts the feature vectors of the original and augmented data by the Transformer encoder. Then, it computes the clustering centroids by K-means and employs the student t-distribution to assign pseudo-labels to all cells in the clustering head. The projection-head uses a Multi-Layer Perceptron (MLP) to obtain projections of the augmented data. At last, both pseudo-labels and projections are used in the contrastive loss to guide the model training. Such a process goes iteratively so that the clustering result becomes better and better. Extensive experiments on 25 real world scRNA-seq datasets show that CICL outperforms the SOTA methods. Concretely, CICL surpasses the existing methods by from 14% to 280%, and from 5% to 133% on average in terms of performance metrics ARI and NMI respectively.

Video anomaly detection is to determine whether there are any abnormal events, behaviors or objects in a given video, which enables effective and intelligent public safety management. As video anomaly labeling is both time-consuming and expensive, most existing works employ unsupervised or weakly supervised learning methods. This paper focuses on weakly supervised video anomaly detection, in which the training videos are labeled whether or not they contain any anomalies, but there is no information about which frames the anomalies are located. However, the uncertainty of weakly labeled data and the large model size prevent existing methods from wide deployment in real scenarios, especially the resource-limit situations such as edge-computing. In this paper, we develop a lightweight video anomaly detection model. On the one hand, we propose an adaptive instance selection strategy, which is based on the model's current status to select confident instances, thereby mitigating the uncertainty of weakly labeled data and subsequently promoting the model's performance. On the other hand, we design a lightweight multi-level temporal correlation attention module and an hourglass-shaped fully connected layer to construct the model, which can reduce the model parameters to only 0.56\% of the existing methods (e.g. RTFM). Our extensive experiments on two public datasets UCF-Crime and ShanghaiTech show that our model can achieve comparable or even superior AUC score compared to the state-of-the-art methods, with a significantly reduced number of model parameters.

In the past decade, Artificial Intelligence driven drug design and discovery has been a hot research topic, where an important branch is molecule generation by generative models, from GAN-based models and VAE-based models to the latest diffusion-based models. However, most existing models pursue only the basic properties like validity and uniqueness of the generated molecules, a few go further to explicitly optimize one single important molecular property (e.g. QED or PlogP), which makes most generated molecules little usefulness in practice. In this paper, we present a novel approach to generating molecules with desirable properties, which expands the diffusion model framework with multiple innovative designs. The novelty is two-fold. On the one hand, considering that the structures of molecules are complex and diverse, and molecular properties are usually determined by some substructures (e.g. pharmacophores), we propose to perform diffusion on two structural levels: molecules and molecular fragments respectively, with which a mixed Gaussian distribution is obtained for the reverse diffusion process. To get desirable molecular fragments, we develop a novel electronic effect based fragmentation method. On the other hand, we introduce two ways to explicitly optimize multiple molecular properties under the diffusion model framework. First, as potential drug molecules must be chemically valid, we optimize molecular validity by an energy-guidance function. Second, since potential drug molecules should be desirable in various properties, we employ a multi-objective mechanism to optimize multiple molecular properties simultaneously. Extensive experiments with two benchmark datasets QM9 and ZINC250k show that the molecules generated by our proposed method have better validity, uniqueness, novelty, Fr\'echet ChemNet Distance (FCD), QED, and PlogP than those generated by current SOTA models.

Zero-shot object detection aims to localize and recognize objects of unseen classes. Most of existing works face two problems: the low recall of RPN in unseen classes and the confusion of unseen classes with background. In this paper, we present the first method that combines DETR and meta-learning to perform zero-shot object detection, named Meta-ZSDETR, where model training is formalized as an individual episode based meta-learning task. Different from Faster R-CNN based methods that firstly generate class-agnostic proposals, and then classify them with visual-semantic alignment module, Meta-ZSDETR directly predict class-specific boxes with class-specific queries and further filter them with the predicted accuracy from classification head. The model is optimized with meta-contrastive learning, which contains a regression head to generate the coordinates of class-specific boxes, a classification head to predict the accuracy of generated boxes, and a contrastive head that utilizes the proposed contrastive-reconstruction loss to further separate different classes in visual space. We conduct extensive experiments on two benchmark datasets MS COCO and PASCAL VOC. Experimental results show that our method outperforms the existing ZSD methods by a large margin., Comment: Accepted in ICCV 2023

Scene text image super-resolution (STISR) is an important pre-processing technique for text recognition from low-resolution scene images. Nowadays, various methods have been proposed to extract text-specific information from high-resolution (HR) images to supervise STISR model training. However, due to uncontrollable factors (e.g. shooting equipment, focus, and environment) in manually photographing HR images, the quality of HR images cannot be guaranteed, which unavoidably impacts STISR performance. Observing the quality issue of HR images, in this paper we propose a novel idea to boost STISR by first enhancing the quality of HR images and then using the enhanced HR images as supervision to do STISR. Concretely, we develop a new STISR framework, called High-Resolution ENhancement (HiREN) that consists of two branches and a quality estimation module. The first branch is developed to recover the low-resolution (LR) images, and the other is an HR quality enhancement branch aiming at generating high-quality (HQ) text images based on the HR images to provide more accurate supervision to the LR images. As the degradation from HQ to HR may be diverse, and there is no pixel-level supervision for HQ image generation, we design a kernel-guided enhancement network to handle various degradation, and exploit the feedback from a recognizer and text-level annotations as weak supervision signal to train the HR enhancement branch. Then, a quality estimation module is employed to evaluate the qualities of HQ images, which are used to suppress the erroneous supervision information by weighting the loss of each image. Extensive experiments on TextZoom show that HiREN can work well with most existing STISR methods and significantly boost their performances.

The emergence of vertical federated learning (VFL) has stimulated concerns about the imperfection in privacy protection, as shared feature embeddings may reveal sensitive information under privacy attacks. This paper studies the delicate equilibrium between data privacy and task utility goals of VFL under differential privacy (DP). To address the generality issue of prior arts, this paper advocates a flexible and generic approach that decouples the two goals and addresses them successively. Specifically, we initially derive a rigorous privacy guarantee by applying norm clipping on shared feature embeddings, which is applicable across various datasets and models. Subsequently, we demonstrate that task utility can be optimized via adaptive adjustments on the scale and distribution of feature embeddings in an accuracy-appreciative way, without compromising established DP mechanisms. We concretize our observation into the proposed VFL-AFE framework, which exhibits effectiveness against privacy attacks and the capacity to retain favorable task utility, as substantiated by extensive experiments.

With the rapid amassing of spatial-temporal (ST) ocean data, many spatial-temporal data mining (STDM) studies have been conducted to address various oceanic issues, including climate forecasting and disaster warning. Compared with typical ST data (e.g., traffic data), ST ocean data is more complicated but with unique characteristics, e.g., diverse regionality and high sparsity. These characteristics make it difficult to design and train STDM models on ST ocean data. To the best of our knowledge, a comprehensive survey of existing studies remains missing in the literature, which hinders not only computer scientists from identifying the research issues in ocean data mining but also ocean scientists to apply advanced STDM techniques. In this paper, we provide a comprehensive survey of existing STDM studies for ocean science. Concretely, we first review the widely-used ST ocean datasets and highlight their unique characteristics. Then, typical ST ocean data quality enhancement techniques are explored. Next, we classify existing STDM studies in ocean science into four types of tasks, i.e., prediction, event detection, pattern mining, and anomaly detection, and elaborate on the techniques for these tasks. Finally, promising research opportunities are discussed. This survey can help scientists from both computer science and ocean science better understand the fundamental concepts, key techniques, and open challenges of STDM for ocean science.

Recently, ''pre-training and fine-tuning'' has been adopted as a standard workflow for many graph tasks since it can take general graph knowledge to relieve the lack of graph annotations from each application. However, graph tasks with node level, edge level, and graph level are far diversified, making the pre-training pretext often incompatible with these multiple tasks. This gap may even cause a ''negative transfer'' to the specific application, leading to poor results. Inspired by the prompt learning in natural language processing (NLP), which has presented significant effectiveness in leveraging prior knowledge for various NLP tasks, we study the prompting topic for graphs with the motivation of filling the gap between pre-trained models and various graph tasks. In this paper, we propose a novel multi-task prompting method for graph models. Specifically, we first unify the format of graph prompts and language prompts with the prompt token, token structure, and inserting pattern. In this way, the prompting idea from NLP can be seamlessly introduced to the graph area. Then, to further narrow the gap between various graph tasks and state-of-the-art pre-training strategies, we further study the task space of various graph applications and reformulate downstream problems to the graph-level task. Afterward, we introduce meta-learning to efficiently learn a better initialization for the multi-task prompt of graphs so that our prompting framework can be more reliable and general for different tasks. We conduct extensive experiments, results from which demonstrate the superiority of our method., Comment: KDD 23 Best Research Paper Award, which is the first for Hong Kong and Mainland China. A Python Library is released as ProG: https://github.com/sheldonresearch/ProG Submitted to SIGKDD'23 in 03 Feb 2023; Receive Acceptance in 17 May 2023 (Rating 3 4 4 4); Submit to arXiv 1st time in 4 Jul 2023

Contrastive learning have been widely used as pretext tasks for self-supervised pre-trained molecular representation learning models in AI-aided drug design and discovery. However, exiting methods that generate molecular views by noise-adding operations for contrastive learning may face the semantic inconsistency problem, which leads to false positive pairs and consequently poor prediction performance. To address this problem, in this paper we first propose a semantic-invariant view generation method by properly breaking molecular graphs into fragment pairs. Then, we develop a Fragment-based Semantic-Invariant Contrastive Learning (FraSICL) model based on this view generation method for molecular property prediction. The FraSICL model consists of two branches to generate representations of views for contrastive learning, meanwhile a multi-view fusion and an auxiliary similarity loss are introduced to make better use of the information contained in different fragment-pair views. Extensive experiments on various benchmark datasets show that with the least number of pre-training samples, FraSICL can achieve state-of-the-art performance, compared with major existing counterpart models.

Few-shot object detection (FSOD) is to detect objects with a few examples. However, existing FSOD methods do not consider hierarchical fine-grained category structures of objects that exist widely in real life. For example, animals are taxonomically classified into orders, families, genera and species etc. In this paper, we propose and solve a new problem called hierarchical few-shot object detection (Hi-FSOD), which aims to detect objects with hierarchical categories in the FSOD paradigm. To this end, on the one hand, we build the first large-scale and high-quality Hi-FSOD benchmark dataset HiFSOD-Bird, which contains 176,350 wild-bird images falling to 1,432 categories. All the categories are organized into a 4-level taxonomy, consisting of 32 orders, 132 families, 572 genera and 1,432 species. On the other hand, we propose the first Hi-FSOD method HiCLPL, where a hierarchical contrastive learning approach is developed to constrain the feature space so that the feature distribution of objects is consistent with the hierarchical taxonomy and the model's generalization power is strengthened. Meanwhile, a probabilistic loss is designed to enable the child nodes to correct the classification errors of their parent nodes in the taxonomy. Extensive experiments on the benchmark dataset HiFSOD-Bird show that our method HiCLPL outperforms the existing FSOD methods., Comment: Accepted by ACM MM 2022

Recent works have empirically shown the effectiveness of data augmentation (DA) in NLP tasks, especially for those suffering from data scarcity. Intuitively, given the size of generated data, their diversity and quality are crucial to the performance of targeted tasks. However, to the best of our knowledge, most existing methods consider only either the diversity or the quality of augmented data, thus cannot fully mine the potential of DA for NLP. In this paper, we present an easy and plug-in data augmentation framework EPiDA to support effective text classification. EPiDA employs two mechanisms: relative entropy maximization (REM) and conditional entropy minimization (CEM) to control data generation, where REM is designed to enhance the diversity of augmented data while CEM is exploited to ensure their semantic consistency. EPiDA can support efficient and continuous data generation for effective classifier training. Extensive experiments show that EPiDA outperforms existing SOTA methods in most cases, though not using any agent networks or pre-trained generation networks, and it works well with various DA algorithms and classification models. Code is available at https://github.com/zhaominyiz/EPiDA., Comment: Accepted by NAACL2022

The generic object detection (GOD) task has been successfully tackled by recent deep neural networks, trained by an avalanche of annotated training samples from some common classes. However, it is still non-trivial to generalize these object detectors to the novel long-tailed object classes, which have only few labeled training samples. To this end, the Few-Shot Object Detection (FSOD) has been topical recently, as it mimics the humans' ability of learning to learn, and intelligently transfers the learned generic object knowledge from the common heavy-tailed, to the novel long-tailed object classes. Especially, the research in this emerging field has been flourishing in recent years with various benchmarks, backbones, and methodologies proposed. To review these FSOD works, there are several insightful FSOD survey articles [58, 59, 74, 78] that systematically study and compare them as the groups of fine-tuning/transfer learning, and meta-learning methods. In contrast, we review the existing FSOD algorithms from a new perspective under a new taxonomy based on their contributions, i.e., data-oriented, model-oriented, and algorithm-oriented. Thus, a comprehensive survey with performance comparison is conducted on recent achievements of FSOD. Furthermore, we also analyze the technical challenges, the merits and demerits of these methods, and envision the future directions of FSOD. Specifically, we give an overview of FSOD, including the problem definition, common datasets, and evaluation protocols. The taxonomy is then proposed that groups FSOD methods into three types. Following this taxonomy, we provide a systematic review of the advances in FSOD. Finally, further discussions on performance, challenges, and future directions are presented., Comment: 35 pages, 14 figures

Federated learning has seen increased adoption in recent years in response to the growing regulatory demand for data privacy. However, the opaque local training process of federated learning also sparks rising concerns about model faithfulness. For instance, studies have revealed that federated learning is vulnerable to backdoor attacks, whereby a compromised participant can stealthily modify the model's behavior in the presence of backdoor triggers. This paper proposes an effective defense against the attack by examining shared model updates. We begin with the observation that the embedding of backdoors influences the participants' local model weights in terms of the magnitude and orientation of their model gradients, which can manifest as distinguishable disparities. We enable a robust identification of backdoors by studying the statistical distribution of the models' subsets of gradients. Concretely, we first segment the model gradients into fragment vectors that represent small portions of model parameters. We then employ anomaly detection to locate the distributionally skewed fragments and prune the participants with the most outliers. We embody the findings in a novel defense method, ARIBA. We demonstrate through extensive analyses that our proposed methods effectively mitigate state-of-the-art backdoor attacks with minimal impact on task utility., Comment: APWeb-WAIM 2023

Most of the existing methods for anomaly detection use only positive data to learn the data distribution, thus they usually need a pre-defined threshold at the detection stage to determine whether a test instance is an outlier. Unfortunately, a good threshold is vital for the performance and it is really hard to find an optimal one. In this paper, we take the discriminative information implied in unlabeled data into consideration and propose a new method for anomaly detection that can learn the labels of unlabelled data directly. Our proposed method has an end-to-end architecture with one encoder and two decoders that are trained to model inliers and outliers' data distributions in a competitive way. This architecture works in a discriminative manner without suffering from overfitting, and the training algorithm of our model is adopted from SGD, thus it is efficient and scalable even for large-scale datasets. Empirical studies on 7 datasets including KDD99, MNIST, Caltech-256, and ImageNet etc. show that our model outperforms the state-of-the-art methods., Comment: 8 pages

In image recognition, there are many cases where training samples cannot cover all target classes. Zero-shot learning (ZSL) utilizes the class semantic information to classify samples of the unseen categories that have no corresponding samples contained in the training set. In this paper, we propose an end-to-end framework, called Global Semantic Consistency Network (GSC-Net for short), which makes complete use of the semantic information of both seen and unseen classes, to support effective zero-shot learning. We also adopt a soft label embedding loss to further exploit the semantic relationships among classes. To adapt GSC-Net to a more practical setting, Generalized Zero-shot Learning (GZSL), we introduce a parametric novelty detection mechanism. Our approach achieves the state-of-the-art performance on both ZSL and GZSL tasks over three visual attribute datasets, which validates the effectiveness and advantage of the proposed framework.

Community structure is pervasive in various real-world networks, portraying the strong local clustering of nodes. Unveiling the community structure of a network is deemed to a crucial step towards understanding the dynamics on the network. Actually, most of the real-world networks are dynamic and their community structures are evolutionary over time accordingly. How to revealing the dynamical communities has recently become a pressing issue. Here, we present an evolutionary method for accurately identifying dynamical communities in the networks. In this method, we first introduced a fitness function that is a compound of asymptotic surprise values on the current and previous snapshots of the network. Second, we developed ad hoc merging and splitting operators, which allows for large-scale searching while preserving low cost. Third, this large-scale searching coupled with local mutation and crossover enhanced revealing a better solution to each snapshot of the network. This method does not require specifying the number of communities advanced, and free from resolution limit while satisfying temporal smooth constraint. Experimental results on both model and real dynamic networks show that the method can find a better solution compared with state-of-art approaches., Comment: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. 13 pages, 11 figures

In financial markets, abnormal trading behaviors pose a serious challenge to market surveillance and risk management. What is worse, there is an increasing emergence of abnormal trading events that some experienced traders constitute a collusive clique and collaborate to manipulate some instruments, thus mislead other investors by applying similar trading behaviors for maximizing their personal benefits. In this paper, a method is proposed to detect the hidden collusive cliques involved in an instrument of future markets by first calculating the correlation coefficient between any two eligible unified aggregated time series of signed order volume, and then combining the connected components from multiple sparsified weighted graphs constructed by using the correlation matrices where each correlation coefficient is over a user-specified threshold. Experiments conducted on real order data from the Shanghai Futures Exchange show that the proposed method can effectively detect suspect collusive cliques. A tool based on the proposed method has been deployed in the exchange as a pilot application for futures market surveillance and risk management., Comment: 13 pages, 5 figures and 3 tables. submitted to Neurocomputing

Social network is a main tunnel of rumor spreading. Previous studies are concentrated on a static rumor spreading. The content of the rumor is invariable during the whole spreading process. Indeed, the rumor evolves constantly in its spreading process, which grows shorter, more concise, more easily grasped and told. In an early psychological experiment, researchers found about 70% of details in a rumor were lost in the first 6 mouth-to-mouth transmissions \cite{TPR}. Based on the facts, we investigate rumor spreading on social networks, where the content of the rumor is modified by the individuals with a certain probability. In the scenario, they have two choices, to forward or to modify. As a forwarder, an individual disseminates the rumor directly to its neighbors. As a modifier, conversely, an individual revises the rumor before spreading it out. When the rumor spreads on the social networks, for instance, scale-free networks and small-world networks, the majority of individuals actually are infected by the multi-revised version of the rumor, if the modifiers dominate the networks. Our observation indicates that the original rumor may lose its influence in the spreading process. Similarly, a true information may turn to be a rumor as well. Our result suggests the rumor evolution should not be a negligible question, which may provide a better understanding of the generation and destruction of a rumor., Comment: a regular paper with 6 pages, 3 figures

The studies based on $A+A \rightarrow \emptyset$ and $A+B\rightarrow \emptyset$ diffusion-annihilation processes have so far been studied on weighted uncorrelated scale-free networks and fractal scale-free networks. In the previous reports, it is widely accepted that the segregation of particles in the processes is introduced by the fractal structure. In this paper, we study these processes on a family of weighted scale-free networks with identical degree sequence. We find that the depletion zone and segregation are essentially caused by the disassortative mixing, namely, high-degree nodes tend to connect with low-degree nodes. Their influence on the processes is governed by the correlation between the weight and degree. Our finding suggests both the weight and degree distribution don't suffice to characterize the diffusion-annihilation processes on weighted scale-free networks., Comment: 15 pages, 10 figures

Futures trading is the core of futures business, and it is considered as one of the typical complex systems. To investigate the complexity of futures trading, we employ the analytical method of complex networks. First, we use real trading records from the Shanghai Futures Exchange to construct futures trading networks, in which nodes are trading participants, and two nodes have a common edge if the two corresponding investors appear simultaneously in at least one trading record as a purchaser and a seller respectively. Then, we conduct a comprehensive statistical analysis on the constructed futures trading networks. Empirical results show that the futures trading networks exhibit features such as scale-free behavior with interesting odd-even-degree divergence in low-degree regions, small-world effect, hierarchical organization, power-law betweenness distribution, disassortative mixing, and shrinkage of both the average path length and the diameter as network size increases. To the best of our knowledge, this is the first work that uses real data to study futures trading networks, and we argue that the research results can shed light on the nature of real futures business., Comment: 18 pages, 9 figures. Final version published in Physica A

The family of Vicsek fractals is one of the most important and frequently-studied regular fractal classes, and it is of considerable interest to understand the dynamical processes on this treelike fractal family. In this paper, we investigate discrete random walks on the Vicsek fractals, with the aim to obtain the exact solutions to the global mean first-passage time (GMFPT), defined as the average of first-passage time (FPT) between two nodes over the whole family of fractals. Based on the known connections between FPTs, effective resistance, and the eigenvalues of graph Laplacian, we determine implicitly the GMFPT of the Vicsek fractals, which is corroborated by numerical results. The obtained closed-form solution shows that the GMFPT approximately grows as a power-law function with system size (number of all nodes), with the exponent lies between 1 and 2. We then provide both the upper bound and lower bound for GMFPT of general trees, and show that leading behavior of the upper bound is the square of system size and the dominating scaling of the lower bound varies linearly with system size. We also show that the upper bound can be achieved in linear chains and the lower bound can be reached in star graphs. This study provides a comprehensive understanding of random walks on the Vicsek fractals and general treelike networks., Comment: Definitive version accepted for publication in Physical Review E

Various real-life networks of current interest are simultaneously scale-free and modular. Here we study analytically the average distance in a class of deterministically growing scale-free modular networks. By virtue of the recursive relations derived from the self-similar structure of the networks, we compute rigorously this important quantity, obtaining an explicit closed-form solution, which recovers the previous result and is corroborated by extensive numerical calculations. The obtained exact expression shows that the average distance scales logarithmically with the number of nodes in the networks, indicating an existence of small-world behavior. We present that this small-world phenomenon comes from the peculiar architecture of the network family., Comment: Submitted for publicaction

Clustering coefficient is an important topological feature of complex networks. It is, however, an open question to give out its analytic expression on weighted networks yet. Here we applied an extended mean-field approach to investigate clustering coefficients in the typical weighted networks proposed by Barrat, Barth\'elemy and Vespignani (BBV networks). We provide analytical solutions of this model and find that the local clustering in BBV networks depends on the node degree and strength. Our analysis is well in agreement with results of numerical simulations., Comment: A paper with 9 pages, 3 figures

Various real systems simultaneously exhibit scale-free and hierarchical structure. In this paper, we study analytically average distance in a deterministic scale-free network with hierarchical organization. Using a recursive method based on the network construction, we determine explicitly the average distance, obtaining an exact expression for it, which is confirmed by extensive numerical calculations. The obtained rigorous solution shows that the average distance grows logarithmically with the network order (number of nodes in the network). We exhibit the similarity and dissimilarity in average distance between the network under consideration and some previously studied networks, including random networks and other deterministic networks. On the basis of the comparison, we argue that the logarithmic scaling of average distance with network order could be a generic feature of deterministic scale-free networks., Comment: Definitive version published in Journal of Statistical Mechanics

We propose a deterministic weighted scale-free small-world model for considering pseudofractal web with the coevolution of topology and weight. In the model, we have the degree distribution exponent $\gamma$ restricted to a range between 2 and 3, simultaneously tunable with two parameters. At the same time, we provide a relatively complete view of topological structure and weight dynamics characteristics of the networks: weight and strength distribution; degree correlations; average clustering coefficient and degree-cluster correlations; as well as the diameter. We show that our model is particularly effective at mimicing weighted scale-free small-world networks with a high and relatively stable clustering coefficient, which rapidly decline with the network size in most previous models., Comment: a paper with 15 pages and 5 figures

A wide variety of real-life networks share two remarkable generic topological properties: scale-free behavior and modular organization, and it is natural and important to study how these two features affect the dynamical processes taking place on such networks. In this paper, we investigate a simple stochastic process--trapping problem, a random walk with a perfect trap fixed at a given location, performed on a family of hierarchical networks that exhibit simultaneously striking scale-free and modular structure. We focus on a particular case with the immobile trap positioned at the hub node having the largest degree. Using a method based on generating functions, we determine explicitly the mean first-passage time (MFPT) for the trapping problem, which is the mean of the node-to-trap first-passage time over the entire network. The exact expression for the MFPT is calculated through the recurrence relations derived from the special construction of the hierarchical networks. The obtained rigorous formula corroborated by extensive direct numerical calculations exhibits that the MFPT grows algebraically with the network order. Concretely, the MFPT increases as a power-law function of the number of nodes with the exponent much less than 1. We demonstrate that the hierarchical networks under consideration have more efficient structure for transport by diffusion in contrast with other analytically soluble media including some previously studied scale-free networks. We argue that the scale-free and modular topologies are responsible for the high efficiency of the trapping process on the hierarchical networks., Comment: Definitive version accepted for publication in Physical Review E

In general, the power-law degree distribution has profound influence on various dynamical processes defined on scale-free networks. In this paper, we will show that power-law degree distribution alone does not suffice to characterize the behavior of trapping problem on scale-free networks, which is an integral major theme of interest for random walks in the presence of an immobile perfect absorber. In order to achieve this goal, we study random walks on a family of one-parameter (denoted by $q$) scale-free networks with identical degree sequence for the full range of parameter $q$, in which a trap is located at a fixed site. We obtain analytically or numerically the mean first-passage time (MFPT) for the trapping issue. In the limit of large network order (number of nodes), for the whole class of networks, the MFPT increases asymptotically as a power-law function of network order with the exponent obviously different for different parameter $q$, which suggests that power-law degree distribution itself is not sufficient to characterize the scaling behavior of MFPT for random walks, at least trapping problem, performed on scale-free networks., Comment: 9 pages, 10 figures

For random walks on networks (graphs), it is a theoretical challenge to explicitly determine the mean first-passage time (MFPT) between two nodes averaged over all pairs. In this paper, we study the MFPT of random walks in the famous T-graph, linking this important quantity to the resistance distance in electronic networks. We obtain an exact formula for the MFPT that is confirmed by extensive numerical calculations. The interesting quantity is derived through the recurrence relations resulting from the self-similar structure of the T-graph. The obtained closed-form expression exhibits that the MFPT approximately increases as a power-law function of the number of nodes, with the exponent lying between 1 and 2. Our research may shed light on the deeper understanding of random walks on the T-graph., Comment: Definitive version accepted for publication in New Journal of Physics

The determination of mean first-passage time (MFPT) for random walks in networks is a theoretical challenge, and is a topic of considerable recent interest within the physics community. In this paper, according to the known connections between MFPT, effective resistance, and the eigenvalues of graph Laplacian, we first study analytically the MFPT between all node pairs of a class of growing treelike networks, which we term deterministic uniform recursive trees (DURTs), since one of its particular cases is a deterministic version of the famous uniform recursive tree. The interesting quantity is determined exactly through the recursive relation of the Laplacian spectra obtained from the special construction of DURTs. The analytical result shows that the MFPT between all couples of nodes in DURTs varies as $N \ln N$ for large networks with node number $N$. Second, we study trapping on a particular network of DURTs, focusing on a special case with the immobile trap positioned at a node having largest degree. We determine exactly the average trapping time (ATT) that is defined as the average of FPT from all nodes to the trap. In contrast to the scaling of the MFPT, the leading behavior of ATT is a linear function of $N$. Interestingly, we show that the behavior for ATT of the trapping problem is related to the trapping location, which is in comparison with the phenomenon of trapping on fractal T-graph although both networks exhibit treestructure. Finally, we believe that the methods could open the way to exactly calculate the MFPT and ATT in a wide range of deterministic media., Comment: 8 pages, 6 figures, definitive version published in Physical Review E

Spatially constrained planar networks are frequently encountered in real-life systems. In this paper, based on a space-filling disk packing we propose a minimal model for spatial maximal planar networks, which is similar to but different from the model for Apollonian networks [J. S. Andrade, Jr. et al., Phys. Rev. Lett. {\bf 94}, 018702 (2005)]. We present an exhaustive analysis of various properties of our model, and obtain the analytic solutions for most of the features, including degree distribution, clustering coefficient, average path length, and degree correlations. The model recovers some striking generic characteristics observed in most real networks. To address the robustness of the relevant network properties, we compare the structural features between the investigated network and the Apollonian networks. We show that topological properties of the two networks are encoded in the way of disk packing. We argue that spatial constrains of nodes are relevant to the structure of the networks., Comment: 12 pages, 7 figures. Definitive version accepted for publication in New Journal of Physics

It is known that the heterogeneity of scale-free networks helps enhancing the efficiency of trapping processes performed on them. In this paper, we show that transport efficiency is much lower in a fractal scale-free network than in non-fractal networks. To this end, we examine a simple random walk with a fixed trap at a given position on a fractal scale-free network. We calculate analytically the mean first-passage time (MFPT) as a measure of the efficiency for the trapping process, and obtain a closed-form expression for MFPT, which agrees with direct numerical calculations. We find that, in the limit of a large network order $V$, the MFPT $$ behaves superlinearly as $ \sim V^{{3/2}}$ with an exponent 3/2 much larger than 1, which is in sharp contrast to the scaling $ \sim V^{\theta}$ with $\theta \leq 1$, previously obtained for non-fractal scale-free networks. Our results indicate that the degree distribution of scale-free networks is not sufficient to characterize trapping processes taking place on them. Since various real-world networks are simultaneously scale-free and fractal, our results may shed light on the understanding of trapping processes running on real-life systems., Comment: 6 pages, 5 figures; Definitive version accepted for publication in EPL (Europhysics Letters)

In this paper, we propose an evolving Sierpinski gasket, based on which we establish a model of evolutionary Sierpinski networks (ESNs) that unifies deterministic Sierpinski network [Eur. Phys. J. B {\bf 60}, 259 (2007)] and random Sierpinski network [Eur. Phys. J. B {\bf 65}, 141 (2008)] to the same framework. We suggest an iterative algorithm generating the ESNs. On the basis of the algorithm, some relevant properties of presented networks are calculated or predicted analytically. Analytical solution shows that the networks under consideration follow a power-law degree distribution, with the distribution exponent continuously tuned in a wide range. The obtained accurate expression of clustering coefficient, together with the prediction of average path length reveals that the ESNs possess small-world effect. All our theoretical results are successfully contrasted by numerical simulations. Moreover, the evolutionary prisoner's dilemma game is also studied on some limitations of the ESNs, i.e., deterministic Sierpinski network and random Sierpinski network., Comment: final version accepted for publication in Physica A

Explicit determination of the mean first-passage time (MFPT) for trapping problem on complex media is a theoretical challenge. In this paper, we study random walks on the Apollonian network with a trap fixed at a given hub node (i.e. node with the highest degree), which are simultaneously scale-free and small-world. We obtain the precise analytic expression for the MFPT that is confirmed by direct numerical calculations. In the large system size limit, the MFPT approximately grows as a power-law function of the number of nodes, with the exponent much less than 1, which is significantly different from the scaling for some regular networks or fractals, such as regular lattices, Sierpinski fractals, T-graph, and complete graphs. The Apollonian network is the most efficient configuration for transport by diffusion among all previously studied structure., Comment: Definitive version accepted for publication in EPL (Europhysics Letters)

The complete knowledge of Laplacian eigenvalues and eigenvectors of complex networks plays an outstanding role in understanding various dynamical processes running on them; however, determining analytically Laplacian eigenvalues and eigenvectors is a theoretical challenge. In this paper, we study the Laplacian spectra and their corresponding eigenvectors of a class of deterministically growing treelike networks. The two interesting quantities are determined through the recurrence relations derived from the structure of the networks. Beginning from the rigorous relations one can obtain the complete eigenvalues and eigenvectors for the networks of arbitrary size. The analytical method opens the way to analytically compute the eigenvalues and eigenvectors of some other deterministic networks, making it possible to accurately calculate their spectral characteristics., Comment: Definitive version accepted for publication in Physical Reivew E

In this paper, we investigate the epidemic spreading for SIR model in weighted scale-free networks with nonlinear infectivity, where the transmission rate in our analytical model is weighted. Concretely, we introduce the infectivity exponent $\alpha$ and the weight exponent $\beta$ into the analytical SIR model, then examine the combination effects of $\alpha$ and $\beta$ on the epidemic threshold and phase transition. We show that one can adjust the values of $\alpha$ and $\beta$ to rebuild the epidemic threshold to a finite value, and it is observed that the steady epidemic prevalence $R$ grows in an exponential form in the early stage, then follows hierarchical dynamics. Furthermore, we find $\alpha$ is more sensitive than $\beta$ in the transformation of the epidemic threshold and epidemic prevalence, which might deliver some useful information or new insights in the epidemic spreading and the correlative immunization schemes., Comment: 17 pages, 12 figures

The explicit determinations of the mean first-passage time (MFPT) for trapping problem are limited to some simple structure, e.g., regular lattices and regular geometrical fractals, and determining MFPT for random walks on other media, especially complex real networks, is a theoretical challenge. In this paper, we investigate a simple random walk on the the pseudofractal scale-free web (PSFW) with a perfect trap located at a node with the highest degree, which simultaneously exhibits the remarkable scale-free and small-world properties observed in real networks. We obtain the exact solution for the MFPT that is calculated through the recurrence relations derived from the structure of PSFW. The rigorous solution exhibits that the MFPT approximately increases as a power-law function of the number of nodes, with the exponent less than 1. We confirm the closed-form solution by direct numerical calculations. We show that the structure of PSFW can improve the efficiency of transport by diffusion, compared with some other structure, such as regular lattices, Sierpinski fractals, and T-graph. The analytical method can be applied to other deterministic networks, making the accurate computation of MFPT possible., Comment: 6 pages, 1 figure; definitive version published in Physical Review E

Traffic fluctuation has so far been studied on unweighted networks. However many real traffic systems are better represented as weighted networks, where nodes and links are assigned a weight value representing their physical properties such as capacity and delay. Here we introduce a general random diffusion (GRD) model to investigate the traffic fluctuation in weighted networks, where a random walk's choice of route is affected not only by the number of links a node has, but also by the weight of individual links. We obtain analytical solutions that characterise the relation between the average traffic and the fluctuation through nodes and links. Our analysis is supported by the results of numerical simulations. We observe that the value ranges of the average traffic and the fluctuation, through nodes or links, increase dramatically with the level of heterogeneity in link weight. This highlights the key role that link weight plays in traffic fluctuation and the necessity to study traffic fluctuation on weighted networks., Comment: a paper with 11 pages, 6 figures, 40 references

As one of the most significant models, the uniform recursive tree (URT) has found many applications in a variety of fields. In this paper, we study rigorously the structural features and spectral properties of the adjacency matrix for a family of deterministic uniform recursive trees (DURTs) that are deterministic versions of URT. Firstly, from the perspective of complex networks, we investigate analytically the main structural characteristics of DURTs, and obtain the accurate solutions for these properties, which include degree distribution, average path length, distribution of node betweenness, and degree correlations. Then we determine the complete eigenvalues and their corresponding eigenvectors of the adjacency matrix for DURTs. Our research may shed light in better understanding of the features for URT. Also, the analytical methods used here is capable of extending to many other deterministic networks, making the precise computation of their properties (especially the full spectrum characteristics) possible., Comment: Definitive version published in Journal of Physics A: Mathematical and Theoretical

Generally, the threshold of percolation in complex networks depends on the underlying structural characterization. However, what topological property plays a predominant role is still unknown, despite the speculation of some authors that degree distribution is a key ingredient. The purpose of this paper is to show that power-law degree distribution itself is not sufficient to characterize the threshold of bond percolation in scale-free networks. To achieve this goal, we first propose a family of scale-free networks with the same degree sequence and obtain by analytical or numerical means several topological features of the networks. Then, by making use of the renormalization group technique we determine the threshold of bond percolation in our networks. We find an existence of non-zero thresholds and demonstrate that these thresholds can be quite different, which implies that power-law degree distribution does not suffice to characterize the percolation threshold in scale-free networks., Comment: Definitive version published in Physical Review E

The closed-form solution for the average distance of a deterministic network--Sierpinski network--is found. This important quantity is calculated exactly with the help of recursion relations, which are based on the self-similar network structure and enable one to derive the precise formula analytically. The obtained rigorous solution confirms our previous numerical result, which shows that the average distance grows logarithmically with the number of network nodes. The result is at variance with that derived from random networks., Comment: Definitive version (9 pages, 6 figures) published in J. Stat. Mech

The class of Koch fractals is one of the most interesting families of fractals, and the study of complex networks is a central issue in the scientific community. In this paper, inspired by the famous Koch fractals, we propose a mapping technique converting Koch fractals into a family of deterministic networks, called Koch networks. This novel class of networks incorporates some key properties characterizing a majority of real-life networked systems---a power-law distribution with exponent in the range between 2 and 3, a high clustering coefficient, small diameter and average path length, and degree correlations. Besides, we enumerate the exact numbers of spanning trees, spanning forests, and connected spanning subgraphs in the networks. All these features are obtained exactly according to the proposed generation algorithm of the networks considered. The network representation approach could be used to investigate the complexity of some real-world systems from the perspective of complex networks., Comment: Definitive version accepted for publication in Journal of Physics A

A vast variety of real-life networks display the ubiquitous presence of scale-free phenomenon and small-world effect, both of which play a significant role in the dynamical processes running on networks. Although various dynamical processes have been investigated in scale-free small-world networks, analytical research about random walks on such networks is much less. In this paper, we will study analytically the scaling of the mean first-passage time (MFPT) for random walks on scale-free small-world networks. To this end, we first map the classical Koch fractal to a network, called Koch network. According to this proposed mapping, we present an iterative algorithm for generating the Koch network, based on which we derive closed-form expressions for the relevant topological features, such as degree distribution, clustering coefficient, average path length, and degree correlations. The obtained solutions show that the Koch network exhibits scale-free behavior and small-world effect. Then, we investigate the standard random walks and trapping issue on the Koch network. Through the recurrence relations derived from the structure of the Koch network, we obtain the exact scaling for the MFPT. We show that in the infinite network order limit, the MFPT grows linearly with the number of all nodes in the network. The obtained analytical results are corroborated by direct extensive numerical calculations. In addition, we also determine the scaling efficiency exponents characterizing random walks on the Koch network., Comment: 12 pages, 8 figures. Definitive version published in Physical Review E

Various real-life networks exhibit degree correlations and heterogeneous structure, with the latter being characterized by power-law degree distribution $P(k)\sim k^{-\gamma}$, where the degree exponent $\gamma$ describes the extent of heterogeneity. In this paper, we study analytically the average path length (APL) of and random walks (RWs) on a family of deterministic networks, recursive scale-free trees (RSFTs), with negative degree correlations and various $\gamma \in (2,1+\frac{\ln 3}{\ln 2}]$, with an aim to explore the impacts of structure heterogeneity on APL and RWs. We show that the degree exponent $\gamma$ has no effect on APL $d$ of RSFTs: In the full range of $\gamma$, $d$ behaves as a logarithmic scaling with the number of network nodes $N$ (i.e. $d \sim \ln N$), which is in sharp contrast to the well-known double logarithmic scaling ($d \sim \ln \ln N$) previously obtained for uncorrelated scale-free networks with $2 \leq \gamma <3$. In addition, we present that some scaling efficiency exponents of random walks are reliant on degree exponent $\gamma$., Comment: The definitive verion published in Journal of Mathematical Physics

Real networks can be classified into two categories: fractal networks and non-fractal networks. Here we introduce a unifying model for the two types of networks. Our model network is governed by a parameter $q$. We obtain the topological properties of the network including the degree distribution, average path length, diameter, fractal dimensions, and betweenness centrality distribution, which are controlled by parameter $q$. Interestingly, we show that by adjusting $q$, the networks undergo a transition from fractal to non-fractal scalings, and exhibit a crossover from `large' to small worlds at the same time. Our research may shed some light on understanding the evolution and relationships of fractal and non-fractal networks., Comment: 7 pages, 3 figures, definitive version accepted for publication in EPJB

The Vicsek fractals are one of the most interesting classes of fractals and the study of their structural properties is important. In this paper, the exact formula for the mean geodesic distance of Vicsek fractals is found. The quantity is computed precisely through the recurrence relations derived from the self-similar structure of the fractals considered. The obtained exact solution exhibits that the mean geodesic distance approximately increases as an exponential function of the number of nodes, with the exponent equal to the reciprocal of the fractal dimension. The closed-form solution is confirmed by extensive numerical calculations., Comment: 4 pages, 3 figures

In this paper, we define a stochastic Sierpinski gasket, on the basis of which we construct a network called random Sierpinski network (RSN). We investigate analytically or numerically the statistical characteristics of RSN. The obtained results reveal that the properties of RSN is particularly rich, it is simultaneously scale-free, small-world, uncorrelated, modular, and maximal planar. All obtained analytical predictions are successfully contrasted with extensive numerical simulations. Our network representation method could be applied to study the complexity of some real systems in biological and information fields., Comment: 7 pages, 9 figures; final version accepted for publication in EPJB

It is generally accepted that scale-free networks is prone to epidemic spreading allowing the onset of large epidemics whatever the spreading rate of the infection. In the paper, we show that disease propagation may be suppressed in particular fractal scale-free networks. We first study analytically the topological characteristics of a network model and show that it is simultaneously scale-free, highly clustered, "large-world", fractal and disassortative. Any previous model does not have all the properties as the one under consideration. Then, by using the renormalization group technique we analyze the dynamic susceptible-infected-removed (SIR) model for spreading of infections. Interestingly, we find the existence of an epidemic threshold, as compared to the usual epidemic behavior without a finite threshold in uncorrelated scale-free networks. This phenomenon indicates that degree distribution of scale-free networks does not suffice to characterize the epidemic dynamics on top of them. Our results may shed light in the understanding of the epidemics and other spreading phenomena on real-life networks with similar structural features as the considered model., Comment: 9 pages, 3 figures