Huawei Ji, Yuanhao Sun, Yuan Jin, Cheng Deng, Jiaxin Ding, Luoyi Fu, Xinbing Wang. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Rapid development of web services has led to an explosion of multimodal content, making multimodal recommender systems (MRSs) vital tools for mitigating information overload. Current MRSs have achieved remarkable progress by incorporating advanced technologies such as Graph Neural Networks (GNNs) and Large Language Models (LLMs). However, these studies still suffer from the semantic shift problem. Generally, item's multimodal content usually contain multiple objects, including target object (core content of item) and auxiliary objects (decorations of item). Existing MRSs overlooked this distinction, failing to prevent auxiliary objects from dominating the representation, leading to biased item representation. To address this issue, we propose a model-agnostic framework ''TargetMR''. Concretely, TargetMR comprises two core modules, including Object Disentangler and Object Identifier. The Object Disentangler decouples item text and image into multiple objects via text syntactic parsing and image segmentation. The Object Identifier performs knowledge distillation based on LLMs to efficiently identify the target text object. It then identifies the target image object through cross-modal semantic evaluation. Moreover, this module refines the representation of image target object by optimizing the semantic correlation. Owing to the model-agnostic design of TargetMR, it can be integrated into various backbone MRSs. Extensive experiments on three benchmark datasets show that TargetMR consistently improves the performance of five backbone MRSs, with an average improvement of 12.26%. Our codes are available at https://github.com/gutang-97/TargetMR/.

Graph generation underlies many critical applications, from social network modeling to knowledge graph reasoning. Across these diverse domains, many graphs are rationale–dominated : a small, semantically meaningful subgraph determines the property of interest, while the remaining edges contribute largely noisy variation. Despite the significance of this inherent structure, existing generative methods often fail to preserve these task–critical substructures. We introduce RARD (Rationale-first blockwise AutoRegressive Diffusion), a topology-guided framework that learns to separate and prioritize the rationale. RARD employs a persistent-homology-based learning objective to discover an optimal graph filtration, an edge ordering that explicitly separates rationale from noise. Building upon this learned filtration, RARD generates graphs blockwise: it adds filtration-aligned blocks autoregressively and refines each new block with a shared local discrete diffusion module, ensuring the rationale appears early while peripheral structure is added later. We provide theoretical analysis showing that maximizing the topological gap yields rationale-first ordering and collapses to a two-level filtration. Comprehensive experiments across seven benchmarks demonstrate that RARD achieves state-of-the-art performance on widely used metrics.

Out-of-Distribution (OOD) generalization is a promising yet challenging goal that guarantees the test performance of Graph Neural Networks (GNNs) in open-world settings. However, due to the intricate internal topology of graph-structured data, redundant information from the spurious topologies severely confuses GNNs to deviate from the labels. Extracting concise and label-relevant subgraphs from the original graphs can alleviate this problem. Unfortunately, existing methods either overlook the global structural distribution or rely heavily on manually predefined assumptions. As a result, they fall short of well capturing the structural distribution changes between input graph and extracted subgraph, thus compromising adaptability of extracted invariant subgraphs to diverse OOD scenarios. This motivates us to propose a framework called S tructural- E ntropy-guided I nformation B ottleneck (OOD-SEIB) that aims to more traceably measure the inherent information changes for better and more flexible OOD generalization. The core of OOD-SEIB lies in concise topology extraction module, where we measure the mutual information flow between input graph and extracted subgraph based on structural entropy, termed Compression Index (CI). Specifically, the CI is a quantifiable metric that calculates the codeword length required to describe entire graph structure via a biased random walk. Under this guidance, OOD-SEIB then launches a structural information bottleneck compression module that jointly optimizes both CI and label-relevance of the subgraph topology by iteratively balancing between informativeness and compression. To further improve GNN’s invariant subgraph identification capability, OOD-SEIB generates multiple augmented environments and distill the invariant subgraphs into GNN as knowledge in an inside-out manner. When iteratively optimizing in above prescribed way, OOD-SEIB progressively reinforce the invariant subgraph extraction, thereby enhancing its generalization capability. Extensive experiments on synthetic and three real-world graph-level OOD benchmarks demonstrate that our proposed OOD-SEIB improves classification accuracy by 4.85%–38.03% on average compared to state-of-the-art baselines. Additionally, we extend OOD-SEIB to two node-level benchmarks, achieving average classification accuracy improvements of 14.52% and 13.15%.

With the development of data-centric AI, the focus has shifted from model-driven approaches to improving data quality. Academic literature, as one of the crucial types, is predominantly stored in PDF formats and needs to be parsed into texts before further processing. However, parsing diverse structured texts in academic literature remains challenging due to the lack of datasets that cover various text structures. In this paper, we introduce AceParse, the first comprehensive dataset designed to support the parsing of a wide range of structured texts, including formulas, tables, lists, algorithms, and sentences with embedded mathematical expressions. Based on AceParse, we fine-tuned a multimodal model, named AceParser, which accurately parses various structured texts within academic literature. This model outperforms the previous state-of-the-art by 4.1% in terms of F1 score and by 5% in Jaccard Similarity, demonstrating the potential of multimodal models in academic literature parsing. Our dataset is available at https://github.com/JHW5981/AceParse.

Reasoning over Knowledge Graphs (KGs) plays a pivotal role in knowledge graph completion or question answering systems, providing richer and more accurate triples and attributes. As numerical attributes become increasingly essential in characterizing entities and relations in KGs, the ability to reason over these attributes has gained significant importance. Existing graph-based methods such as Graph Neural Networks (GNNs) and Knowledge Graph Embeddings (KGEs), primarily focus on aggregating homogeneous local neighbors and implicitly embedding diverse triples. However, these approaches often fail to fully leverage the potential of logical paths within the graph, limiting their effectiveness in exploiting the reasoning process. To address these limitations, we propose ChainsFormer, a novel chain-based framework designed to support numerical reasoning. Chainsformer not only explicitly constructs logical chains but also expands the reasoning depth to multiple hops. Specially, we introduces Relation-Attribute Chains (RA-Chains), a specialized logic chain, to model sequential reasoning patterns. ChainsFormer captures the step-by-step nature of multi-hop reasoning along RA-Chains by employing sequential in-context learning. To mitigate the impact of noisy chains, we propose a hyperbolic affinity scoring mechanism that selects relevant logic chains in a variable-resolution space. Furthermore, ChainsFormer incorporates an attention-based numerical reasoner to identify critical reasoning paths, enhancing both reasoning accuracy and transparency. Experimental results demonstrate that ChainsFormer significantly outperforms state-of-the-art methods, achieving up to a 20.0% improvement in performance. The implementations are available at https://github.com/zhaodazhuang2333/ChainsFormer.

Evolving graphs are prevalent in real-world systems where nodes and edges continuously expand over time, resulting in persistent topological changes across temporal snapshots. As the graph expands, the increasing structural discrepancy between earlier and later timesteps often leads to poor generalization-a phenomenon widely recognized as Temporal out-of-distribution (TOOD) generalization. This issue has spurred growing research interest in generalized graph learning. Existing approaches often rely on modeling latent environments or incorporating structural causal reasoning, but they frequently face scalability limitations when applied to rapidly expanding graphs. In this work, we carry out a detailed analysis of temporal drift in evolving graphs and identify two complementary forms: structural role drift reflected by changes in degree proportions, and semantic drift measured by embedding divergence. To capture this graph evolution, we propose PromptEG, a scalable prompt-based framework that generates node-specific prompts using degree signals and KL-divergence between representations. These prompts are optimized via consistency and contrastive objectives, and injected into GNNs to enhance temporal generalization. Experiments on largescale evolving graphs-containing up to 500 K edges and tens of thousands of nodes-demonstrate that PromptEG achieves strong long-horizon generalization while maintaining high computational efficiency.

Constrained Reinforcement Learning (CRL) aims to maximize cumulative rewards while satisfying constraints. However, existing CRL algorithms often encounter significant constraint violations during training, limiting their applicability in safety-critical scenarios. In this paper, we identify the underestimation of the cost value function as a key factor contributing to these violations. To address this issue, we propose the Memory-driven Intrinsic Cost Estimation (MICE) method, which introduces intrinsic costs to mitigate underestimation and control bias to promote safer exploration. Inspired by flashbulb memory, where humans vividly recall dangerous experiences to avoid risks, MICE constructs a memory module that stores previously explored unsafe states to identify high-cost regions. The intrinsic cost is formulated as the pseudo-count of the current state visiting these risk regions. Furthermore, we propose an extrinsic-intrinsic cost value function that incorporates intrinsic costs and adopts a bias correction strategy. Using this function, we formulate an optimization objective within the trust region, along with corresponding optimization methods. Theoretically, we provide convergence guarantees for the proposed cost value function and establish the worst-case constraint violation for the MICE update. Extensive experiments demonstrate that MICE significantly reduces constraint violations while preserving policy performance comparable to baselines.

Ensuring safety is a critical challenge in applying Reinforcement Learning (RL) to real-world scenarios. Constrained Reinforcement Learning (CRL) addresses this by maximizing returns under predefined constraints, typically formulated as the expected cumulative cost. However, expectation-based constraints overlook rare but high-impact extreme value events in the tail distribution, such as black swan incidents, which can lead to severe constraint violations. To address this issue, we propose the Extreme Value policy Optimization (EVO) algorithm, leveraging Extreme Value Theory (EVT) to model and exploit extreme reward and cost samples, reducing constraint violations. EVO introduces an extreme quantile optimization objective to explicitly capture extreme samples in the cost tail distribution. Additionally, we propose an extreme prioritization mechanism during replay, amplifying the learning signal from rare but high-impact extreme samples. Theoretically, we establish upper bounds on expected constraint violations during policy updates, guaranteeing strict constraint satisfaction at a zero-violation quantile level. Further, we demonstrate that EVO achieves a lower probability of constraint violations than expectation-based methods and exhibits lower variance than quantile regression methods. Extensive experiments show that EVO significantly reduces constraint violations during training while maintaining competitive policy performance compared to baselines.

With the explosive growth of online multimodal content, multimodal recommender systems(MRSs) have brought significant benefits to multimedia platforms. As MRSs evolve, many studies incorporate advanced technologies like graph neural networks(GNNs) and self-supervised learning(SSL), achieving remarkable results. However, these efforts still suffer from the quality disparity problem. It refers to the mixture of high and low quality across items' multiple modalities, owing to disparities in construction costs or design levels. These low-quality modalities often lack crucial details or introduce noise to the depiction of item, leading to insufficient or polluted item representation. Therefore, we propose a novel framework R2MR: Review and Rewrite Modality for Recommendation to tackle this issue. Specifically, R2MR is composed of two key components: Modality Reviewer and Modality Rewriter. The Modality Reviewer introduces a Consensus Review Mechanism. It performs perspective decomposition based on user representations and learns the consensus quality scores for modalities from diverse perspectives of multiple users. The Modality Rewriter proposes a Latent Mapping Model, which improves the quality of inferior modalities by learning various mapping patterns from high-quality modalities. Comprehensive experiments across three benchmark datasets reveal that R2MR substantially outperforms state-of-the-art methods, achieving an average improvement of 9.20%. The implementations are available at https://github.com/gutang-97/R2MR.

Nowadays, the explosive growth of academic literature has been going far beyond scientists' limited capability to read through, making it increasingly difficult for them to absorb disciplinary insights and extract intellectual essences critical for generating novel research ideas in interdisciplinary studies. To address this, we develop DeepReport, an AI-assisted scientific idea generation system to alleviate the research burden. Technically, DeepReport maintains evolving concept co-occurrence graphs to extract core insights from over 260 million publications across all disciplines. These concepts are periodically collected and updated, enabling the automatic extraction of hidden cross-domain connections. Combining temporal link prediction and analysis techniques with large language models, DeepReport is able to further transform these patterns of insights into actionable ideas. With the function of integrating up-to-date academic databases, visualizing dynamic relationships of concepts, and automatically generating new ideas, DeepReport empowers researchers to navigate complex knowledge landscapes, reduce cognitive burdens, and accelerate the generation of groundbreaking concepts. This work provides an in-depth exploration of DeepReport's architecture, functionalities, and applications, highlighting its transformative potential for advancing interdisciplinary research and fostering innovation. DeepReport is available at https://idea.acemap.cn/.

This paper investigates the problem of maintaining the connectivity between two vertices, a source and a destination, in an uncertain network under adversarial attack, where a defender preserves crucial links to prevent the source–destination vertex pair from being disconnected by an attacker. In contrast with prior art that mostly focuses on the overall network connectivity, in this work connectivity maintenance is restricted to a pair of selected vertices, which may provide insights into reliable point-to-point connection. We model the network as a random graph where each link carries both an existence probability and a probing cost, and seek to design a defensive strategy that ensures source–destination connectivity under minimum probing expenditure, regardless of adversarial behavior. To this end, we first delve into the computational complexity of the problem by establishing its NP-hardness, and put forth an optimal defensive strategy leveraging dynamic programming. Due to the prohibitive price of attaining optimality, we further design two approximate defensive strategies aimed at pursuing effective defensive performance within polynomial time, in which the first one is a path-based heuristic strategy that iteratively extends a preserved path by probing links with high utility regarding source–destination connectivity, and the second one is a cut-based minimax strategy that prioritizes the links in the minimum potential source–destination cut in order to minimize the possible worst-case loss suffered by the defender with a constant approximation ratio. Extensive experiments conducted on synthetic and real-world network datasets under diverse attacking strategies validate the superiority of the proposed strategies in both effectiveness and robustness over baselines.

This paper delves into the challenge of maintaining connectivity in adversarial networks, focusing on the preservation of essential links to prevent the disintegration of network components under attack. Unlike previous approaches that assume a stable and homogeneous network topology, this study introduces a more realistic model that incorporates both link uncertainty and heterogeneity. Link uncertainty necessitates additional probing to confirm link existence, while heterogeneity reflects the varying resilience of links against attacks. We model the network as a random graph where each link is defined by its existence probability, probing cost, and resilience. The primary objective is to devise a defensive strategy that maximizes the expected size of the largest connected component at the end of an adversarial process while minimizing the probing cost, irrespective of the attack patterns employed. We begin by establishing the NP-hardness of the problem and then introduce an optimal defensive strategy based on dynamic programming. Due to the high computational cost of achieving optimality, we also develop two approximate strategies that offer efficient solutions within polynomial time. The first is a heuristic method that assesses link importance across three heterogeneous subnetworks, and the second is an adaptive minimax policy designed to minimize the defender’s potential worst-case loss, with guaranteed performance. Through extensive testing on both synthetic and real-world datasets across various attack scenarios, our strategies demonstrate significant advantages over existing methods.

The best arm identification problem in multi-armed bandit model has been widely applied into many practical applications, such as spectrum sensing, online advertising, and cloud computing. Although lots of works have been devoted into this area, most of them do not consider the cost of pulling actions, i.e., a player has to pay some cost when she pulls an arm. Motivated by this, we study a ratio-based best arm identification problem, where each arm is associated with a random reward as well as a random cost. For any \(\delta\in(0,1)\) , with probability at least \(1-\delta\) , the player aims to find the arm with the largest ratio of expected reward to expected cost using as few samplings as possible. Specifically, we consider two settings: (1) the precise setting, i.e., identifying the precise optimal one; (2) the Probably Approximate Correct (PAC) setting, which identifies the \(\epsilon\) -optimal one. For the precise setting, we design the elimination-type algorithms and provide a fundamental lower bound which asymptotically matches the upper bound, while in the PAC setting, an UCB-type algorithm which amed \(\epsilon\) -RCB algorithm is proposed. We show that for all algorithms, the sample complexities, i.e., the pulling times for all arms, grow logarithmically as \(\frac{1}{\delta}\) increases. Moreover, compared to existing works, the running of our algorithms is independent of the arm-related parameters, which is more practical. Finally, we validate our theoretical results through numerical experiments.

Shuqian Sheng, Yi Xu, Tianhang Zhang, Zanwei Shen, Luoyi Fu, Jiaxin Ding, Lei Zhou, Xiaoying Gan, Xinbing Wang, Chenghu Zhou. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.

Human trajectories, representing sequences of location points over time, are extensively collected and analyzed for various real-world applications such as urban planning, transportation management, and personalized location-based services. Trajectory embedding transforms raw trajectories into vector representations, capturing the underlying patterns and structures in the data. However, the abstraction provided by vector representations introduces significant security and privacy risks. These embeddings, often shared between entities or organizations, can be exploited by adversaries to reconstruct original trajectories, thereby compromising individual privacy. In this paper, we investigate the privacy issues of trajectory embeddings from an adversary's perspective. We propose two types of attacks to reconstruct original trajectories using road network information, addressing scenarios where the adversary has varying degrees of access to the black-box representation model. The first attack assumes unrestricted access to the model, allowing the adversary to construct a large-scale dataset and train a neural network to predict the road sequence of the trajectories. The second attack considers limited access, where the adversary computes distance coordinates between selected trajectory landmarks and road segments to infer different parts of the trajectory. Our experiments on a real-world dataset demonstrate that the reconstructed trajectories outperform baseline methods, achieving substantially lower reconstruction errors and more accurate alignment with the original trajectories, highlighting the significant vulnerability of trajectory embeddings to privacy breaches. These findings underscore the need for robust privacy-preserving mechanisms in spatio-temporal data analysis.

Accurately reconstructing the global ocean deoxygenation over a century is crucial for assessing and protecting marine ecosystem. Existing expert-dominated numerical simulations fail to catch up with the dynamic variation caused by global warming and human activities. Besides, due to the high-cost data collection, the historical observations are severely sparse, leading to big challenge for precise reconstruction. In this work, we propose OxyGenerator, the first deep learning based model, to reconstruct the global ocean deoxygenation from 1920 to 2023. Specifically, to address the heterogeneity across large temporal and spatial scales, we propose zoning-varying graph message-passing to capture the complex oceanographic correlations between missing values and sparse observations. Additionally, to further calibrate the uncertainty, we incorporate inductive bias from dissolved oxygen (DO) variations and chemical effects. Compared with in-situ DO observations, OxyGenerator significantly outperforms CMIP6 numerical simulations, reducing MAPE by 38.77%, demonstrating a promising potential to understand the “breathless ocean” in data-driven manner.

Shuqian Sheng, Yi Xu, Luoyi Fu, Jiaxin Ding, Lei Zhou, Xinbing Wang, Chenghu Zhou. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

With the enrichment of user-item interactions, Graph Neural Networks (GNNs) are widely used in recommender systems to alleviate information overload. Nevertheless, they still suffer from the cold-start issue. Knowledge Graphs (KGs), providing external information, have been extensively applied in GNN-based methods to mitigate this issue. However, current KG-aware recommendation methods suffer from the knowledge imbalance problem caused by incompleteness of existing KGs. This imbalance is reflected by the long-tail phenomenon of item attributes, i.e., unpopular items usually lack more attributes compared to popular items. To tackle this problem, we propose a novel framework called EditKG: Editing Knowledge Graph for Recommendation, to balance attribute distribution of items via editing KGs. EditKG consists of two key designs: Knowledge Generator and Knowledge Deleter. Knowledge Generator generates attributes for items by exploring their mutual information correlations and semantic correlations. Knowledge Deleter removes the task-irrelevant item attributes according to the parameterized task relevance score, while dropping the spurious item attributes through aligning the attribute scores. Extensive experiments on three benchmark datasets demonstrate that EditKG significantly outperforms state-of-the-art methods, and achieves 8.98% average improvement. The implementations are available at https://github.com/gutang-97/2024SIGIR-EditKG.

Large language models (LLMs) have achieved great success in general domains of natural language processing. In this paper, we bring LLMs to the realm of geoscience with the objective of advancing research and applications in this field. To this end, we present the first-ever LLM in geoscience, K2, alongside a suite of resources developed to further promote LLM research within geoscience. For instance, we have curated the first geoscience instruction tuning dataset, GeoSignal, which aims to align LLM responses to geoscience-related user queries. Additionally, we have established the first geoscience benchmark, GeoBench, to evaluate LLMs in the context of geoscience. In this work, we experiment with a complete recipe to adapt a pre-trained general-domain LLM to the geoscience domain. Specifically, we further train the LLaMA-7B model on 5.5B tokens of geoscience text corpus, including over 1 million pieces of geoscience literature, and utilize GeoSignal's supervised data to fine-tune the model. Moreover, we share a protocol that can efficiently gather domain-specific data and construct domain-supervised data, even in situations where manpower is scarce. Meanwhile, we equip K2 with the abilities of using tools to be a naive geoscience aide. Experiments conducted on the GeoBench demonstrate the effectiveness of our approach and datasets on geoscience knowledge understanding and utilization.We open-source all the training data and K2 model checkpoints at https://github.com/davendw49/k2

Many complex networks in the real world have community structures. Typical examples include online social networks and ecology networks. While the identification of communities bears numerous practical applications, with the increasing awareness of data security and privacy concerns, the need to protect the community affiliations of individuals from disclosing by attackers emerges. This raises the community deception (CD) problem, that is, the opposite of community detection, which asks for ways to minimally perturb the network structures by rewiring nodes so that the target communities maximally hide themself from community detection algorithms. To this end, we investigate the CD problem through a Laplacian spectrum lens and propose a method named$\mathtt {ComDeceptor}$to hide a flexible target set of communities, which is more universal than most existing methods that either focus on hiding the entire communities or a single community. The key idea of$\mathtt {ComDeceptor}$is to first allocate the resources of perturbations fairly and effectively. By proving that hiding communities through intercommunity edge addition and intracommunity edge deletion correspond to maximizing the second smallest eigenvalue$\lambda _{2}$and minimizing the largest eigenvalue$\lambda _{n}$of the graph Laplacian, respectively,$\mathtt {ComDeceptor}$then incorporates efficient heuristics for approximately solving the problems, thus selecting the appropriate edge to perturb. Experimental results over nine real-world networks and six community detection algorithms not only demonstrate the efficiency of$\mathtt {ComDeceptor}$, but also the superior performance on obfuscating community structures over the baselines.

Graph pooling refers to the operation that maps a set of node representations into a compact form for graph-level representation learning. However, existing graph pooling methods are limited by the power of the Weisfeiler–Lehman (WL) test in the performance of graph discrimination. In addition, these methods often suffer from hard adaptability to hyper-parameters and training instability. To address these issues, we propose Hi-PART, a simple yet effective graph neural network (GNN) framework with Hi erarchical Par tition T ree (HPT). In HPT, each layer is a partition of the graph with different levels of granularities that are going toward a finer grain from top to bottom. Such an exquisite structure allows us to quantify the graph structure information contained in HPT with the aid of structural information theory. Algorithmically, by employing GNNs to summarize node features into the graph feature based on HPT’s hierarchical structure, Hi-PART is able to adequately leverage the graph structure information and provably goes beyond the power of the WL test. Due to the separation of HPT optimization from graph representation learning, Hi-PART involves the height of HPT as the only extra hyper-parameter and enjoys higher training stability. Empirical results on graph classification benchmarks validate the superior expressive power and generalization ability of Hi-PART compared with state-of-the-art graph pooling approaches.

Network alignment, pairing corresponding nodes across the source and target networks, plays an important role in many data mining tasks. Extensive studies focus on learning node embeddings across different networks in a unified space. However, these methods have not taken the large structural discrepancy between aligned nodes into account and, thus, are largely confined by the deterministic representations of nodes. In this work, we propose a novel network alignment framework highlighted by distributional learning and globally optimal alignment. By modeling the uncertainty of each node by Gaussian distribution, our framework builds similarity matrices on the Wasserstein distance between distributions and applies Sinkhorn operation, which learns the globally optimal mapping in an end-to-end fashion. We show that each integrated part of the framework contributes to the overall performance. Under a variety of experimental settings, our alignment framework shows superior accuracy and efficiency to the state-of-the-art.

Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. However, due to the selection bias of training and testing data (e.g., training on small graphs and testing on large graphs, or training on dense graphs and testing on sparse graphs), distribution deviation is widespread. More importantly, we often observehybrid structure distribution shiftof both scale and density, despite of one-sided biased data partition. The spurious correlations over hybrid distribution deviation degrade the performance of previous GNN methods and show large instability among different datasets. To alleviate this problem, we proposeOOD-GMixupto jointly manipulate the training distribution withcontrollable data augmentationin metric space. Specifically, we first extract the graph rationales to eliminate the spurious correlations due to irrelevant information. Secondly, we generate virtual samples with perturbation on graph rationale representation domain to obtain potential OOD training samples. Finally, we propose OOD calibration to measure the distribution deviation of virtual samples by leveraging Extreme Value Theory, and further actively control the training distribution by emphasizing the impact of virtual OOD samples. Extensive studies on several real-world datasets on graph classification demonstrate the superiority of our proposed method over state-of-the-art baselines.

Graph Contrastive Learning (GCL) with Graph Neural Networks (GNN) has emerged as a promising method for learning latent node representations in a self-supervised manner. Most of existing GCL methods employ random sampling for graph view augmentation and maximize the agreement of the node representations between the views. However, the random augmentation manner, which is likely to produce very similar graph view samplings, may easily result in incomplete nodal contextual information, thus weakening the discrimination of node representations. To this end, this paper proposes a novel trainable scheme from the perspective of node augmentation, which is theoretically proved to be injective and utilizes the subgraphs consisting of each node with its neighbors to enhance the distinguishability of nodal view. Notably, our proposed scheme tries to enrich node representations via a multi-scale contrastive training that integrates three different levels of training granularity, i.e., subgraph level, graph- and node-level contextual information. In particular, the subgraph-level objective between augmented and original node views is constructed to enhance the discrimination of node representations while graph- and node-level objectives with global and local information from the original graph are developed to improve the generalization ability of representations. Experiment results demonstrate that our framework outperforms existing state-of-the-art baselines and even surpasses several supervised counterparts on four real-world datasets for node classification.

Information cascading, referred as the phenomenon of an individual following the behavior of the preceding individual after observing its actions, is prevalent in real social networks and triggers intense research interests for the purpose of monitoring and controlling network epidemics. One of the typical lines of information cascading study belongs to the Influence Maximization Problem, which aims to algorithmically find the optimal seeds that can spread the information to the maximum number of nodes. Regardless of the tremendous efforts made in various algorithm design of finding such optimal seeds, it has not yet been well understood how the absolute influence power of the “optimal” source set affects the ultimate cascading, i.e., under which conditions the seeds are able or unable to influence an substantial fraction of the entire network. Most existing works have investigated the conditions of network scale influence under linear threshold model, where the activation of a node requires a large number of infected neighbors. Instead, in this paper we focus on the case of single source cascading, which is only possible to occur under the independent cascading model. We launch information cascading analysis from two aspects, i.e., the influence scale and network-scale cascading probability. Firstly, percolation analysis of the cascading outcome shows that estimating influence scale is equivalent to solving fixed point equations. Then, we investigate the speed and stability of information cascading based on fixed point analysis, which shows that the information cascading process almost surely terminates within logarithmic time complexity. Furthermore, the results are generalized to the stochastic block model, where we find that network-scale cascading is determined by the spectral radius of the community matrix. The analysis presented in this paper could help us better understand the conditions for different information cascading outcomes.

This paper studies connectivity maintenance in uncertain networks under adversarial attack, where a defender conceals crucial links to prevent the largest connected component from being decomposed by an attacker. In contrast with its static counterpart, connectivity maintenance in uncertain networks involves additional probing on links to determine their existence. Therefore, by modeling an uncertain network as a random graph with each link associated with an existence probability and a probing cost, our goal is to design a defensive strategy for link selection that maximizes the expected size of the largest remaining connected component with the minimum expected probing cost, and moreover, the strategy should be independent of the attacking patterns. To this end, we first unravel the computational complexity of the problem by proving its NP-hardness, and then propose optimal defensive strategies based on dynamic programming and multi-objective optimization. Due to the prohibitive computational cost of optimality, two approximate defensive strategies are further designed to pursue decent performance with quasilinear complexity, in which the first one is a heuristic approach that quantifies the link vulnerability through an analogy from the degree centrality of a vertex in static networks to the connectivity weight of a link in uncertain networks, and the second one is an adaptive greedy policy incorporating the minimax rule from game theory, which minimizes the possible loss suffered by the defender in a worst-case scenario and has a constant approximation ratio. Extensive experiments on both synthetic and real-world network datasets under diverse attacking patterns demonstrate the superiority of the proposed strategies over baselines.

This article studies time-sensitive multicast in wireless sensor networks (WSNs) with link uncertainty, where information from the source needs to be delivered to multiple receivers within an imposed delay constraint. Prior art on static WSNs minimizes the multicast delay via the construction of a multicast tree that approximates the Steiner tree in length, which, however, may be invalidated by the time-varying network topology of WSNs with uncertain link states. Moreover, for multicast in WSNs with link uncertainty, the possible link failure necessitates a suitable measurement of the uncertain communication distance and calls for the performance guarantee in both delay and delivery ratio. In this work, by modeling a WSN as a random graph with each link associated with a transmission probability, we propose FlowerCast, an efficient multicast scheme, to jointly minimize the expected multicast delay and to maximize the expected delivery ratio of multicast under delay constraint. The core of FlowerCast is to quantify the uncertain communication distance by the expected transmission delay of a time-varying path, based on which a delay-optimal multicast tree is constructed in accordance with the directionality of delay. Candidate paths with a high expected delivery ratio and low expected delay are then selected in a distributed manner to conditionally connect adjacent multicast members and thus transform the multicast tree into a multicast flower. Despite the NP-hardness of optimal candidate paths’ addition, the transformation with the highest expected delivery ratio of multicast under delay constraint can be guaranteed through a pseudo-polynomial time derandomization-based greedy approach. We further demonstrate the time and energy efficiency of FlowerCast through asymptotic analysis. To make full use of the possible overlapping links in a multicast flower, a hybrid routing strategy is presented to wisely switch between sequential routing and synchronous routing for extra enhancement of the multicast performance. Extensive experiments on various datasets verify the superiority of FlowerCast and hybrid routing over baselines and indicate their wide applicability to practical scenarios.

Temporal knowledge graph, serving as an effective way to store and model dynamic relations, shows promising prospects in event forecasting. However, most temporal knowledge graph reasoning methods are highly dependent on the recurrence or periodicity of events, which brings challenges to inferring future events related to entities that lack historical interaction. In fact, the current moment is often the combined effect of a small part of historical information and those unobserved underlying factors. To this end, we propose a new event forecasting model called Contrastive Event Network (CENET), based on a novel training framework of historical contrastive learning. CENET learns both the historical and non-historical dependency to distinguish the most potential entities that can best match the given query. Simultaneously, it trains representations of queries to investigate whether the current moment depends more on historical or non-historical events by launching contrastive learning. The representations further help train a binary classifier whose output is a boolean mask to indicate related entities in the search space. During the inference process, CENET employs a mask-based strategy to generate the final results. We evaluate our proposed model on five benchmark graphs. The results demonstrate that CENET significantly outperforms all existing methods in most metrics, achieving at least 8.3% relative improvement of Hits@1 over previous state-of-the-art baselines on event-based datasets.

Yi Xu, Shuqian Sheng, Jiexing Qi, Luoyi Fu, Zhouhan Lin, Xinbing Wang, Chenghu Zhou. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2023.

Researchers usually come up with new ideas only after thoroughly comprehending vast quantities of literature.The difficulty of this procedure is exacerbated by the fact that the number of academic publications is growing exponentially.In this study, we devise a framework based on concept co-occurrence for academic idea inspiration, which has been integrated into a research assistant system.From our perspective, the fusion of two concepts that co-occur in an academic paper can be regarded as an important way of the emergence of a new idea.We construct evolving concept graphs according to the co-occurrence relationship of concepts from 20 disciplines or topics.Then we design a temporal link prediction method based on masked language model to explore potential connections between different concepts.To verbalize the newly discovered connections, we also utilize the pretrained language model to generate a description of an idea based on a new data structure called co-occurrence citation quintuple.We evaluate our proposed system using both automatic metrics and human assessment.The results demonstrate that our system has broad prospects and can assist researchers in expediting the process of discovering new ideas.1 * Luoyi Fu is the corresponding author. 1 The project is publicly available for research purpose https://github.com/xyjigsaw/Kiscovery.

Tianhang Zhang, Lin Qiu, Qipeng Guo, Cheng Deng, Yue Zhang, Zheng Zhang, Chenghu Zhou, Xinbing Wang, Luoyi Fu. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

User review data is considered as auxiliary information to alleviate the data sparsity problem and improve the quality of learned user/item or interaction representations in review-based recommender systems. However, existing methods usually model user-item interactions in a holistic manner and neglect the entanglement of the latent intents behind them, e.g., price, quality, or appearance, resulting in suboptimal representations and reducing interpretability. In this paper, we propose a Self-supervised Graph Disentangled Networks for review-based recommendation (SGDN), to separately model the user-item interactions based on the latent factors through the textual review data. To this end, we first model the distributions of interactions over latent factors from both semantic information in review data and structural information in user-item graph data, forming several factor graphs. Then a factorized message passing mechanism is designed to learn disentangled user/item and interaction representations on the factor graphs. Finally, we set an intent-aware contrastive learning task to alleviate the sparsity issue and encourage disentanglement through dynamically identifying positive and negative samples based on the learned intent distributions. Empirical results over five benchmark datasets validate the superiority of SGDN over the state-of-the-art methods and the interpretability of learned intent factors.

Given an aftermath of an information spreading, i.e., an infected network GNafter the propagation of malicious rumors, malware or viruses, how can we identify the sources of the cascade? Answering this problem, which is known as the multiple source detection (MSD) problem, is critical whether for forensic use or insights to prevent future epidemics.Despite the recent considerable effort, most of them are built on a preset propagation model, which limits their application range. Some attempts aim to break this limitation via a label propagation scheme where the nodes surrounded by a large proportion of infected nodes are highlighted. Nonetheless, the detection accuracy may suffer since the node labels are simply integers with all infected or uninfected nodes sharing the same initialization setting respectively, which fall short of sufficiently distinguishing their structural properties. To this end, we propose a community based label propagation (CLP) framework that locates multiple sources through exploiting the community structures formed by infected subgraphs of different sources. Besides, CLP tries to enhance the detection accuracy by incorporating node prominence and exoneration effects, namely the nodes surrounded by larger proportions of infected nodes are more likely to be sources, and the uninfected nodes or infected ones in neighboring community hold the key in exonerating an infected node from being the source. As such, CLP is applicable in more propagation models, and is provably convergent. Experiments on both synthetic and real-world networks further validate the superiority of CLP to the state-of-the-art, boosting the F-score from few percents to approximately 68× in large-scale networks.

Bundle recommendation aims to recommend a bundle of items to users as a whole with user-bundle (U-B) interaction information, and auxiliary user-item (U-I) interaction and bundle-item affiliation information. Recent methods usually use two graph neural networks (GNNs) to model user's bundle preferences separately from the U-B graph (bundle view) and U-I graph (item view). However, by conducting statistical analysis, we find that the auxiliary U-I information is far underexplored due to the following reasons: 1) Loosely combining the predicted results cannot well synthesize the knowledge from both views. 2) The local U-B and U-I collaborative relations might not be consistent, leading to GNN's inaccurate modeling of user's bundle preference from the U-I graph. 3) The U-I interactions are usually modeled equally while the significant ones corresponding to user's bundle preference are less emphasized.

Social network de-anonymization, which refers to re-identifying users by mapping an anonymized network to a correlated real-name network, is an important problem in network science that has received intensive study. Although different de-anonymization algorithms have been proposed, the performance limit of any algorithm on a de-anonymization problem remains less explored. In this paper, we investigate the Optimal De-Anonymization Yield (ODAY), i.e., the maximum extent to which the network can be de-anonymized, of a given de-anonymization problem. Specifically, due to the uncertainty of the true mapping, we define ODAY as the maximum expected number of correctly mapped nodes, and propose general approaches for its quantification in general networks. Therefore, ODAY can be viewed as a quantitative and non-asymptotic concretization of the concept of network de-anonymizability, which is mostly investigated in an asymptotic manner in prior art. Inspired by the effect of network symmetry on the de-anonymizability, we show that for a graph pair with arbitrary topologies, ODAY equals the maximum diagonal sum of a matching probability matrix generated from graph homomorphisms. Due to the exponential complexity of enumerating all the possible homomorphisms, we further obtain an upper bound of ODAY by counting the orbits of each of the two graphs, which significantly reduces the computational cost. Two case studies apply our general findings on symmetry and ODAY to specific network models, and a sampling-based algorithm framework is proposed for ODAY calculation in practice. Extensive experiments are performed to validate our findings. To the best of our knowledge, this work is the first effort that quantifies the de-anonymizability of general networks in a non-asymptotic manner from the perspective of network symmetry, and thus sheds light on privacy enhancement for social network design.

Self-supervised graph-level representation learning has recently received considerable attention. Given varied input distributions, jointly learning graphs’ unique and common features is vital to downstream tasks. Inspired by graph contrastive learning (GCL), which targets maximizing the agreement between graph representations from different views, we propose an Ada ptive self-supervised framework, Ada-MIP, considering both M utual I nformation between views (unique features) and inter-graph P roximity (common features). Specifically, Ada-MIP learns graphs’ unique information through a learnable and probably injective augmenter, which can acquire more adaptive views compared to the augmentation strategies applied by existing GCL methods; to learn graphs’ common information, we employ graph kernels to calculate graphs’ proximity and learn graph representations among which the precomputed proximity is preserved. By sharing a global encoder, graphs’ unique and common information can be well integrated into the graph representations learned by Ada-MIP. Ada-MIP is also extendable to semi-supervised scenarios, with our experiments confirming its superior performance in both unsupervised and semi-supervised tasks.

Influence maximization through social networks has aroused tremendous interests nowadays. However, people’s various expressions or feelings about a same idea often cause ambiguity via word of mouth. Consequently, the problem of how to maximize the spread of “effective information” still remains largely open. In this paper, we consider a practical setting where ideas can deviate from their original version to invalid forms during message passing, and make the first attempt to seek a union of users that maximizes the spread of effective influence, which is formulated as an Influence Maximization with Information Variation (IMIV) problem. To this end, we model the information as a vector, and quantify the difference of two arbitrary vectors as a distance by a matching function. We further establish a process where such distance increases with the propagation and ensure the recipient whose vector distance is less than a threshold can be effectively influenced. Due to the NP-hardness of IMIV, we greedily select users that can approximately maximize the estimation of effective propagation. Especially, for networks of small scales, we derive a condition under which all the users can be effectively influenced. Our models and theoretical findings are further consolidated through extensive experiments on real-world datasets.

A crucial privacy-driven issue nowadays is re-identifying anonymized social networks by mapping them to correlated cross-domain auxiliary networks. Prior works are typically based on modeling social networks as random graphs representing users and their relations, and subsequently quantify the quality of mappings through varied cost functions. However, many cost functions are empirically proposed without sufficient theoretical support. For some other works probing the theoretical bound, it remains unknown how to algorithmically meet the demand of such quantifications, i.e., to minimize the cost functions. Besides, only few prior works have discussed the de-anonymization of social networks with communities. We address those concerns in a social network modeling parameterized by community structures that can be leveraged as side information for de-anonymization. Based on the Maximum A Posteriori (MAP) estimation, our first contribution is a series of MAP-based cost functions, which, when minimized, enjoy superiority to previous ones in finding the correct mapping with the highest probability. The feasibility of the cost functions is then for the first time algorithmically characterized. We prove the general multiplicative inapproximability and thus propose two heuristics, which, respectively, enjoy an$\epsilon$-additive approximation and a conditional optimality in carrying out successful user re-identification. Our theoretical findings are also empirically validated under classical synthetic and real-wrold social networks. Both theoretical and empirical observations manifest the importance of community in enhancing privacy inferencing.

The controller provisioning, which adjusts the number, locations, and members of satellite controllers adaptive to the dynamic network load and topology, fundamentally impacts the performance of software-defined satellite networks (SDSNs). An ideal provisioning strategy should achieve a low total control overhead throughout the entire satellite operation period, which is extremely challenging since the network loadcan only be predicted in a short time scale. Existing methods can hardly achieve this goal for they greedily configure controllers in each time slot, where switches have to frequently migrate from one controller to another. In this paper, we focus on achievingglobally optimized strategieswith onlycurrent network load information. We first propose a comprehensive control overhead model and formulate theControllerProvisioningProblem (CPP)in SDSNs as a non-convex integer programming problem. To solve the problem, we propose an approximate algorithm named AROA by introducing a regularization framework and based on randomized rounding. We theoretically derive its competitive ratio. To produce strategies in time for future large satellite constellations, we further propose a more efficient heuristic algorithm HROA. Evaluations on our built simulation system show that our proposed methods significantly outperform related schemes in control overhead, latency, and scalability.

With the increasing popularity of mobile devices, each user is able to conveniently acquire messages from others, and share diverse forms of information, like texts, images, or videos through online mobile apps. The full freedom of speech makes a great amount of truth (i.e., true information) and rumor (i.e., false information) propagate rapidly in a hybrid way through mobile platforms. As a huge variety of information floods pouring over us each day, identifying the authenticity of massive events becomes a necessary task to maintain the stability of Mobile Social Networks (MSNs). An important way to realize it is to trace their diffusions and make judgements according to the reliability of sources. With this regard, this paper proposes a diffusion model that characterizes the simultaneous diffusion of both truth and rumor in realistic MSNs, and makes the first attempt to figure out their respective sources. The problem of interest can be stated as: Given an outcome of cascade of both truth and rumor in MSNs, i.e., a set of nodes that might be the ignorant, the spreader of truth or rumor, or simply the silent receiver, how can we infer both truth sources and rumor sources? Different from previous sources detection works considering single type of nodes, the interplay between truth diffusions and rumor diffusions makes the conventional methods not work. To answer this question, we aim to maximize thesimilarity index, i.e., the number of nodes possessing the same states between the resulting network triggered by our estimated sources with the proposed diffusion model and the given observation network. Compared with existing techniques to trace diffusions of truth or rumor, it is much harder to find two kinds of sets at the same time, including truth sources and rumor sources, due to two primary reasons: (i) our biset optimization makes the submodularity techniques fail; (ii) our objective function is proven to be non-bisubmodular. To overcome above limitations, we first convert the objectivesimilarity indexinto a bisubmodular function by virtue of set covering. Based on this, we propose an approximation algorithm called Truth and Rumor Sources Detection (TRSD) algorithm via multiple reverse samplings with a provable$\frac{1}{4(1+\epsilon)^2}$approximation ratio. Further, a novel “time reversal” sources optimization strategy is proposed to converge the number of output sources from TRSD to a steady state. The effectiveness of our models and algorithms are empirical validated in two various datasets, from which we observe an up to 15% ofsimilarity indexgain as well as a narrowed down gap 0.6% to the ground truth.

The omnipresence of information cascading process in mobile social networking applications makes the identification of a small set$S$of influential users, which is widely believed to trigger the information outbreak, always an crucial issue in various applications such as the mobile advertising and viral marketing. Formulated as Influence maximization (IM) in 2003, this NP-hard problem has received a multitude of studies with diverse angles. However, these works often unable to provide reliable solutions, due to the loss of an exact metric for evaluating users’ contributions on information cascading in the state-of-the-art sampling based IM schemes. In this paper, we evaluate users in IM based on the collective influence (CI), a metric on the structural features of the users in network graph that reflects the contributions of the users’ neighborhoods on shaping collective dynamics of the users over the whole network. For conducting the influencer identification under probabilistic diffusion model based on the CI, we specify a quantified structural feature of the most influential users from the scope of diffusion over the whole network, and reveal that the structural influence power (CI value) of each user is a weighted cumulation of the diffusion probabilities from neighbors within certain hops. Utilizing CI, we design a novel algorithm which identifies the influencers via iteratively choosing the users with top CI values. Moreover, we point out that directly computing CI values requires to traverse the network which is originally represented by a high-dimensional matrix, and leads to huge complexity of influencer identification. To improve scalability, we further trade precision for efficiency by incorporating network embedding, a dimensionality reduction technology for networks, into algorithm design, and propose a minor variant, where CI is jointly recapitulated by low-dimensional user representations and user degrees. The superiority of our algorithms is empirically validated over 8 datasets, with an increment in influence size up to 50 percent and a comparable or even less running time comparing with existing baselines.

The popularity of intelligent devices provides straightforward access to the Internet and online social networks. However, the quick and easy data updates from networks also benefit the risk spreading, such as rumor, malware, or computer viruses. To this end, this article studies the problem of source detection, which is to infer the source node out of an aftermath of a cascade, that is, the observed infected graph G N of the network at some time. Prior arts have adopted various statistical quantities such as degree, distance, or infection size to reflect the structural centrality of the source. In this article, we propose a new metric that we call the infected tree entropy (ITE), to utilize richer underlying structural features for source detection. Our idea of ITE is inspired by the conception of structural entropy [ 21 ], which demonstrated that the minimization of average bits to encode the network structures with different partitions is the principle for detecting the natural or true structures in real-world networks. Accordingly, our proposed ITE based estimator for the source tries to minimize the coding of network partitions brought by the infected tree rooted at all the potential sources, thus minimizing the structural deviation between the cascades from the potential sources and the actual infection process included in G N . On polynomially growing geometric trees, with increasing tree heterogeneity, the ITE estimator remarkably yields more reliable detection under only moderate infection sizes, and returns an asymptotically complete detection. In contrast, for regular expanding trees, we still observe guaranteed detection probability of ITE estimator even with an infinite infection size, thanks to the degree regularity property. We also algorithmically realize the ITE based detection that enjoys linear time complexity via a message-passing scheme, and further extend it to general graphs. Extensive experiments on synthetic and real datasets confirm the superiority of ITE to the baselines. For example, ITE returns an accuracy of 85%, ranking the source among the top 10%, far exceeding 55% of the classic algorithm on scale-free networks.

Relation extraction is a fundamental task to construct a knowledge graph, which aims to find the relation categories between two entities from a string of text input sequences. Considering the fact that high-quality labeled data is rare, a recent trend is low-resource setting. Existing works either utilize prompt-based learning method to achieve encouraging results for few-shot tasks by determining an appropriate prompt template, or leverage unlabeled data by generating pseudo labels. However, the manual design of the prompt template requires not only labor-intensive but also expert knowledge. Roughly utilizing a semi-supervised method to assign pseudo-label to unlabeled data will suffer from noise accumulation. To tackle these problems, we propose a novel semi-supervised prompt learning framework with relation-aware gradient denoising for low-resource relation extraction(PromptRGD). Firstly, using learnable template words and virtual labels for prompt learning, we introduce entity type and relation prior knowledge into prompt template construction. Secondly, given the relation-aware gradient similarity between labeled and unlabeled data, PromptRGD generates a pseudo label and then improves the quality of pseudo labels on unlabeled samples in a self-training fashion. The main experimental results and a series of analyses prove the effectiveness of PromptRGD.

Named entity recognition and relation extraction are two important tasks in information extraction. Many recent works model two tasks jointly and achieve great success. However, these methods still suffer from the relation semantic insufficiency, head entity dependency and nested entity detection problem. To address the challenges, we propose a relation-aware span-level transformer network (RSTN), which contains a span-level encoder for entity recognition and a non-autoregressive decoder for relation extraction. Specifically, we generate explicit represen-tations for possible spans to extract overlapping entities in our span-level encoder. In addition, we encode relation semantics in our non-autoregressive decoder, and exploit copy mechanism to extract head entities and tail entities simultaneously by modifying the casual attention mask. Through span-level multi-head attention mechanism, we enhance the interaction between entity recognition and relation extraction in our model. We evaluate our model on three public datasets: ACE05, ADE and SciERC. Experiment results show that the proposed model outperforms previous strong baseline methods.

This paper studies the problem of connectivity maintenance in adversarial uncertain networks, where a defender prevents the largest connected component from being decomposed by an attacker. In contrast with its deterministic counterpart, connectivity maintenance in an uncertain network involves additional testing on edges to determine their existence. To this end, by modeling a general uncertain network as a random graph with each edge associated with an existence probability and a testing cost, our goal is to design a general adaptive defensive strategy to maximize the expected size of the largest remaining connected component with minimum expected testing cost and, moreover, the strategy should be independent of the attacking patterns. The computational complexity of the connectivity maintenance problem is unraveled by proving its NP-hardness. To accurately tackle the problem, based on dynamic programming we first propose an optimal defensive strategy for a specific class of uncertain networks with uniform testing costs. Thereafter multi-objective optimization is adopted to generalize the optimal strategy for general uncertain networks through weighted sum of normalized size and cost. Due to the prohibitive price of an optimal strategy, two approximate defensive strategies are further designed to pursue decent performance with quasilinear complexity. We first derive a heuristic approach by quantifying the edge vulnerability through an analogy from the degree centrality in deterministic networks to the probability degree and connectivity weight in uncertain networks. For performance guarantee, we then devise an adaptive greedy policy incorporating the minimax rule from game theory, which minimizes the possible loss suffered by the defender in a worst-case scenario caused by the attacker and has an approximation ratio of (1 − 1/e). Extensive experiments on both synthetic and real-world network datasets under diverse attacking patterns demonstrate the superiority of the proposed strategies over baselines.

This paper studies the problem of 6D pose estimation, which is practically important in various application scenarios such as robotic-based object grasping, obstacle avoidance in autonomous driving scene, and object integration in mixed reality. However, existing methods suffer from at least one of the five major limitations: dependence on object identification, complex deployment, difficulty in data collection, low accuracy, and incomplete estimation. To overcome the above limitations, this paper proposes an RC6D system, which is the first to estimate 6D poses by fusing RFID and Computer Vision (CV) data with multi-modal deep learning techniques. In RC6D, we first detect 2D keypoints through a deep learning approach. We then propose a novel RFID-CV fusion neural network to predict the depth of the scene, and use the estimated depth information to expand the 2D keypoints to 3D keypoints. Finally, we model the coordinate correspondences between the detected 2D-3D keypoints, which is applied to estimate the 6D pose of the target object. When implementing RC6D, we mainly address the following three technical challenges. (i) To predict 6D poses without using the CAD model, we propose a network architecture for monocular depth estimation. (ii) To train the neural network for 6D pose estimation without time-consuming 6D labeling, we use an unsupervised learning algorithm based on 2D-3D point pair matching. (iii) To detect the subject of the object without identification, we leverage optical flow to restrict the object and RFID to directly obtain its information. The experimental results show that the localization error of RC6D is less than 10 cm with a probability higher than 90.64% and its orientation estimation error is less than 10° with a probability higher than 79.63%. Hence, the proposed RC6D system performs much better than the state-of-the-art related solutions.

Spatio-temporal graph learning is a key method for urban computing tasks, such as traffic flow, taxi demand and air quality forecasting. Due to the high cost of data collection, some developing cities have few available data, which makes it infeasible to train a well-performed model. To address this challenge, cross-city knowledge transfer has shown its promise, where the model learned from data-sufficient cities is leveraged to benefit the learning process of data-scarce cities. However, the spatio-temporal graphs among different cities show irregular structures and varied features, which limits the feasibility of existing Few-Shot Learning (FSL) methods. Therefore, we propose a model-agnostic few-shot learning framework for spatio-temporal graph called ST-GFSL. Specifically, to enhance feature extraction by transferring cross-city knowledge, ST-GFSL proposes to generate non-shared parameters based on node-level meta knowledge. The nodes in target city transfer the knowledge via parameter matching, retrieving from similar spatio-temporal characteristics. Furthermore, we propose to reconstruct the graph structure during meta-learning. The graph reconstruction loss is defined to guide structure-aware learning, avoiding structure deviation among different datasets. We conduct comprehensive experiments on four traffic speed prediction benchmarks and the results demonstrate the effectiveness of ST-GFSL compared with state-of-the-art methods.

With the tremendous expansion of graphs data, node classification shows its great importance in many real-world applications. Existing graph neural network based methods mainly focus on classifying unlabeled nodes within fixed classes with abundant labeling. However, in many practical scenarios, graph evolves with emergence of new nodes and edges. Novel classes appear incrementally along with few labeling due to its newly emergence or lack of exploration. In this paper, we focus on this challenging but practical graph few-shot class-incremental learning (GFSCIL) problem and propose a novel method called Geometer. Instead of replacing and retraining the fully connected neural network classifier, Geometer predicts the label of a node by finding the nearest class prototype. Prototype is a vector representing a class in the metric space. With the pop-up of novel classes, Geometer learns and adjusts the attention-based prototypes by observing the geometric proximity, uniformity and separability. Teacher-student knowledge distillation and biased sampling are further introduced to mitigate catastrophic forgetting and unbalanced labeling problem respectively. Experimental results on four public datasets demonstrate that Geometer achieves a substantial improvement of 9.46% to 27.60% over state-of-the-art methods.

Emerging crowdsensing paradigm enables a large number of sensing applications, where much attention is drawn to the fundamental problems of data collection and truth inference. Existing works have devised manifold techniques to discover truth from collected noisy data, but they frequently ignore various expertise of workers and dynamic information of crowdsensing system, thus leading to error-prone estimated truth and unqualified sensing data. In this paper, we design an online location-aware crowdsensing system to accurately estimate truth and efficiently assign tasks. Specifically, we unify diverse types of numerical and categorical tasks based on probabilistic graphical model, and then propose unsupervised learning methods which can dynamically infer ground truth and various worker expertise at the same time. Furthermore, we develop online task allocation schemes to gradually gather high quality data considering location awareness and inferred worker expertise. In particular, we convert the complicated task allocation into the additive form of probability improvement and entropy reduction, thereby solving the allocation problem via linearly selecting worker-task pair with low computation complexity. We finally carry out extensive evaluations using two datasets collected by our smartphones, where results demonstrate the superiority of our algorithms over the state-of-the-art approaches.

Urban traffic flow forecasting is a critical issue in intelligent transportation systems. Due to the complexity and uncertainty of urban road conditions, how to capture the dynamic spatiotemporal correlation and make accurate predictions is very challenging. In most of existing works, urban road network is often modeled as a fixed graph based on local proximity. However, such modeling is not sufficient to describe the dynamics of the road network and capture the global contextual information. In this paper, we consider constructing the road network as a dynamic weighted graph through attention mechanism. Furthermore, we propose to seek both spatial neighbors and semantic neighbors to make more connections between road nodes. We propose a novel Spatiotemporal Adaptive Gated Graph Convolution Network ( STAG-GCN ) to predict traffic conditions for several time steps ahead. STAG-GCN mainly consists of two major components: (1) multivariate self-attention Temporal Convolution Network ( TCN ) is utilized to capture local and long-range temporal dependencies across recent, daily-periodic and weekly-periodic observations; (2) mix-hop AG-GCN extracts selective spatial and semantic dependencies within multi-layer stacking through adaptive graph gating mechanism and mix-hop propagation mechanism. The output of different components are weighted fused to generate the final prediction results. Extensive experiments on two real-world large scale urban traffic dataset have verified the effectiveness, and the multi-step forecasting performance of our proposed models outperforms the state-of-the-art baselines.

The von Neumann graph entropy is a measure of graph complexity based on the Laplacian spectrum. It has recently found applications in various learning tasks driven by the networked data. However, it is computationally demanding and hard to interpret using simple structural patterns. Due to the close relation between the Laplacian spectrum and the degree sequence, we conjecture that the structural information, defined as the Shannon entropy of the normalized degree sequence, might be a good approximation of the von Neumann graph entropy that is both scalable and interpretable. In this work, we thereby study the difference between the structural information and the von Neumann graph entropy named asentropy gap. Based on the knowledge that the degree sequence is majorized by the Laplacian spectrum, we for the first time prove that the entropy gap is between 0 and$\log _{2} e$in any undirected unweighted graphs. Consequently we certify that the structural information is a good approximation of the von Neumann graph entropy that achieves provable accuracy, scalability, and interpretability simultaneously. This approximation is further applied to two entropy-related tasks: network design and graph similarity measure, where a novel graph similarity measure and the corresponding fast algorithms are proposed. Meanwhile, we show empirically and theoretically that maximizing the von Neumann graph entropy can effectively hide the community structure, and then propose an alternative metric calledspectral polarizationto guide the community obfuscation. Our experimental results on graphs of various scales and types show that the very small entropy gap readily applies to a wide range of simple/weighted graphs. As an approximation of the von Neumann graph entropy, the structural information is the only one that achieves both high efficiency and high accuracy among the prominent methods. It is at least two orders of magnitude faster than SLaQ (Tsitsulinet al., 2020) with comparable accuracy. Our structural information based methods also exhibit superior performance in downstream tasks such as entropy-driven network design, graph comparison, and community obfuscation.

Influence maximization (IM) aims at maximizing the spread of influence by offering discounts to influential users (called seeding). In many applications, due to user’s privacy concern, overwhelming network scale etc., it is hard to target any user in the network as one wishes. Instead, only a small subset of users is initially accessible. Such access limitation would significantly impair the influence spread, since IM often relies on seeding high degree users, which are particularly rare in such a small subset due to the power-law structure of social networks. In this paper, we attempt to solve the limited IM in real-world scenarios by the adaptive approach with seeding and diffusion uncertainty considered. Specifically, we consider fine-grained discounts and assume users accept the discount probabilistically. The diffusion process is depicted by the independent cascade model. To overcome the access limitation, we prove the set-wise friendship paradox (FP) phenomenon that neighbors have higher degree in expectation, and propose a two-stage seeding model with the FP embedded, where neighbors are seeded. On this basis, for comparison we formulate the non-adaptive case and adaptive case, both proven to be NP-hard. In the non-adaptive case, discounts are allocated to users all at once. We show the monotonicity of influence spread w.r.t. discount allocation and design a two-stage coordinate descent framework to decide the discount allocation. In the adaptive case, users are sequentially seeded based on observations of existing seeding and diffusion results. We prove the adaptive submodularity and submodularity of the influence spread function in two stages. Then, a series of adaptive greedy algorithms are proposed with constant approximation ratio. Extensive experiments on real-world datasets show that our adaptive algorithms achieve larger influence spread than non-adaptive and other adaptive algorithms (up to a maximum of 116 percent).

Mobile edge computing enables resource-limited edge clouds (ECs) in federation to help each other with resource-hungry yet delay-sensitive service requests. Contrary to common practice, we acknowledge that mobile services are heterogeneous and the limited storage resources of ECs allow only a subset of services to be placed at the same time. This paper presents a jointly optimized design of cooperative placement and scheduling framework, named JCPS, that pursuessocial cost minimizationover time while ensuring diverse user demands. Our main contribution is a novel perspective on cost reduction by exploiting thespatial-temporal diversitiesinworkload and resource costamong federated ECs. To build a practical edge cloud federation system, we have to consider two major challenges:user deadline preferenceandECs’ strategic behaviors. We first formulate and solve the problem of spatially strategic optimization without deadline awareness, which is proved$\mathcal {NP}$-hard. By leveraging user deadline tolerance, we develop a Lyapunov-baseddeadline-drivenjoint cooperative mechanism under the scenario where the workload and resource information of ECs are known for one-shot global cost minimization. Theservice priorityimposed by deadline urgency drives time-critical placement and scheduling, which, combined with cooperative control, enables workloads migrated across different times and ECs. Given selfishness of individual ECs, we further design an auction-based cooperative mechanism to elicittruthful bidson workload and resource cost. Rigorous theoretical analysis and extensive simulations are performed, validating the efficiency of JCPS in realizing cost reduction and user satisfaction.

Many realistic mobile social networks can be characterized by evolving bipartite graphs, in which dynamically added elements are divided into two entities and connected by links between these two entities, such as users and items in recommendation networks, authors and scientific topics in scholarly networks, male and female in dating social networks, etc. However, given the fact that connections between two entities are often weighted, how to mathematically model such weighted evolving bipartite relationships, along with quantitative characterizations, remains unexplored. Motivated by this, we develop a novel evolving bipartite model (EBM), which, based on empirically validated power-law distribution on multiple realistic mobile social networks, discloses that the distribution of total weights of incoming and outgoing edges in networks is determined by the weighting scale and bounded by certain ceilings and floors. Based on these theoretical results, for evolving bipartite networks whose degree follows power-law distribution, their overall weights of vertices can be predicted by EBM. To illustrate, in recommendation networks, the evaluation of items, i.e., total rating scores, can be estimated through the given bounds; in scholarly networks, the total numbers of publications under specific topics can be anticipated within a certain range; in dating social networks, the favorability of male/female can be roughly measured. Finally, we perform extensive experiments on 10 realistic datasets and a synthetic network with varying weights, i.e., rating scales, to further evaluate the performance of EBM, and experimental results demonstrate that given weighting scales, both the upper bound and the lower bound of total weights of vertices in mobile social networks can be properly predicted by the EBM.

As Internet users interacting with their different friends in different social networks, the de-anonymization problem has been raising improving concern. Since the assailants may de-anonymize a social network by matching it with a correlated sanitized network and identifying anonymized user identities, multifarious arts study on the theoretical conditions or practical algorithms for correctly de-anonymizing a social network. Except for the structural information of these social networks, there has also been bounteous works taking advantage of some pre-identified seed nodes for reference in the anonymized network. In this paper, we systematically probe the theoretical conditions and algorithmic approaches for correctly matching two different-sized social networks by leveraging the multi-hop neighborhood relationships. A limited number of seeds are also taken into consideration as auxiliary information. To this end, we introduce the de-anonymization problem with the aid of the collectiveness and the collective adjacency disagreements, which are the collection of disagreements of different multi-hop adjacency matrices. We theoretically demonstrate that minimizing the collective adjacency disagreements can help match two social networks even in a very sparse circumstance, as it significantly enlarges the difference between the mismatched node pairs and the correctly matched pairs. Besides, the seeds is proved to bring positive influence in improving the de-anonymization accuracy. Algorithmically, we relax the domain of the matching function to continuum and adopt the conditional gradient descending method on the collective-form objective, to efficiently minimize the collective adjacency disagreements of two networks. We conduct tremendous experiments on different networks with or without seeds, the results of which return desirable de-anonymization accuracies and reveal the advantages of the collectiveness: the collectiveness manifests rich structural information, thereby most nodes can be correctly matched with their correspondences even in some sparse networks, where merely utilizing the 1-hop adjacency relationships might fail to work.

Anonymization techniques have tranquilized current social network users in terms of privacy leakage, however, it does not radically prevent adversaries from de-anonymizing users, as they may map the users to an un-anonymized network. Till now, researchers share a common thread in such de-anonymization attack: unveiling conditions leading to successful de-anonymization under the chosen network model. However, it has not yet been well understand how the structural property in different network models intrinsically determines de-anonymizability. We address the above issue in this paper by making the two contributions: (i) We discover that the automorphic degree and homomorphic degree of social networks determine their de-anonymizability universally. The automorphic degree characterizes the distinguishability of the users in a network, while the homomorphic degree models the similarities of users between two networks. We conclude that a smaller automorphic degree and a larger homomorphic degree conduce to a higher de-anonymizability. Such model-independent phenomenon refreshes us with a latitudinal study as it generalizes the essential commonness of de-anonymization in different network models. (ii) We derive explicit parametric bounds of the de-anonymizability for three classic network models, showing that such bounds correspond well to our conclusion about morphism property. We then algorithmically and experimentally show that such theoretical results literally make sense to adversaries. Such longitudinal study, including welding theory, algorithm and validation, promises applicability of our results on morphism property in real cases.

Existing Space-Terrestrial Integrated Network (STIN) applications collect all data from multiple satellites and terrestrial nodes to the specific analyze center on the earth for processing, which wastes lots of network resources. To save these resources, we propose a novelprocessing-while-transmittingpattern in the SDN-based STIN architecture. Through a logically centralized control plane, it cooperatively processes a complex task on appropriate nodes during data transmission. Here, the key point is to jointly determine the transmission path and place subtasks adaptive to data distributions, heterogeneous link costs, task characteristics, the dynamic topology, and network resources. In this paper, we firstly formulate theTransmission-cost-minimized joint Routing and Tasks placement Problem (TRTP)in time-varying STINs. We prove it is NP-hard and has no Polynomial-Time Approximation Scheme (PTAS). To solve the problem, we propose theJoint Routing and Task Placement (JRTP)algorithm. It first converts the time-varying STIN to a stable graph to cope with the network dynamics, according to the topology and resources during task processing. Then, it jointly decides the routing and task placement through atask-topology graph model, which converts the TRTP problem on the stable graph to the classic shortest path problem. We prove that the performance of JRTP is bounded in cases when transmission resources are sufficient and further improve it through the idea of reinforcement. The experimental results show that our processing pattern can significantly decrease the transmission cost and delay, and our algorithms outperform most related ones.

The research of geoscience plays a strong role in helping people gain a better understanding of the Earth. To effectively represent the knowledge (KG) from enormous geoscience research papers, knowledge graphs can be a powerful means. In the face of enormous geoscience research papers, knowledge graphs can be a powerful means to manage the relationships of data and integrate knowledge extracted from them. However, the existing geoscience KGs mainly focus on the external connection between concepts, whereas the potential abundant information contained in the internal multimodal data of the paper is largely overlooked for more fine-grained knowledge mining. To this end, we propose GAKG, a large-scale multimodal academic KG based on 1.12 million papers published in various geoscience-related journals. In addition to the bibliometrics elements, we also extracted the internal illustrations, tables, and text information of the articles, and dig out the knowledge entities of the papers and the era and spatial attributes of the articles, coupling multimodal academic data and features. Specifically, GAKG realizes knowledge entity extraction under our proposed Human-In-the-Loop framework, the novelty of which is to combine the techniques of machine reading and information retrieval with manual annotation of geoscientists in the loop. Considering the fact that literature of geoscience often contains more abundant illustrations and time scale information compared with that of other disciplines, we extract all the geographical information and era from the geoscience papers' text and illustrations, mapping papers to the atlas and chronology. Based on GAKG, we build several knowledge discovery benchmarks for finding geoscience communities and predicting potential links. GAKG and its services have been made publicly available and user-friendly.

Source identification has a wide range of applications in daily life, including locating the rumor source in online social networks and finding origins of a rolling blackout in smart grids. Despite great success over the past decade, most prior arts are proposed based an assumption that the underlying propagation model is known in advance. However, this assumption may be impracticable on real scenarios, since it is usually difficult to acquire the actual underlying propagation model. To avoid this limitation, in this paper, we propose the Infected Graph Convolutional Network (IGCN) layer by combining infection network with GCN (Graph Convolutional Network) layers to locate the rumor source without prior knowledge of underlying propagation model. For the first time, we define the problem of source identification as a special graph classification problem with source node as the label. By introducing the feature update method of GCN layer with the idea of attention, we build an IGCN model to adapt the infection networks such that the prediction accuracy on the source is improved under model independent scenarios. We conduct experiments on several real datasets and the results show the superiority of IGCN model to baseline algorlthms.

As a critical part of the intelligent transportation system, traffic prediction is challenging due to the time-evolving cascading behavior, i.e., the fluctuation of traffic conditions on one road will affect neighboring roads in the future. To address this issue, we propose a novel learning framework, which is able to extract the most relevant historical information for prediction by capturing the underlying cascading behavior. An encoder-decoder architecture is adopted, where the historical contextual information of each road is encoded into a sequence of historical embeddings. A spatiotemporal attention mechanism is devised to model the cascading behavior in the embedding space so that the most relevant information for prediction is concentrated. Extensive experiments on a real-world large-scale highway dataset verify the effectiveness of our proposed approach, observing 3% ~ 5% improvement over state-of-the-art methods.

Named entity recognition (NER) is an important and challenging task in natural language processing. In this paper, we investigate thoroughly about the advances of Chinese NER in recent years. We explore the validity of a wide range of approaches in the literature of NLP that may benefit NER. We further employ the effective ones, such as data augmentation, adversarial learning, cross-sentence context and cost-sensitive learning to improve the performance of our BERT-based backbone model. Empirical results show that our model with this bag of tricks outperforms previous state-of-the-art on Weibo and achieves competitive performance on MSRA. Our code is publicly available11https://github.com/ccoay/bag-ner.

While community detection has been one of the cornerstones in network analysis and data science, its opposite, community obfuscation, has received little attention in recent years. With the increasing awareness of data security and privacy protection, the need to understand the impact of such attacks on traditional community detection algorithms emerges. To this end, we investigate the community obfuscation problem which aims to hide a target set of communities from being detected by perturbing the network structure. We identify and analyze the Matthew effect incurred by the classical quality function based methods, which essentially results in the imbalanced allocation of perturbation resources. To mitigate such effect, we propose a probabilistic framework named as ProHiCo to hide communities. The key idea of ProHiCo is to first allocate the resource of perturbations randomly and fairly and then choose the appropriate edges to perturb via likelihood minimization. Our ProHiCo framework provides the additional freedom to choose the generative graph model with community structure. By incorporating the stochastic block model and its degree-corrected variant into the ProHiCo framework, we develop two scalable and effective algorithms called SBM and DCSBM. Via extensive experiments on 8 real-world networks and 5 community detection algorithms, we show that both SBM and DCSBM are about 30x faster than the prominent baselines in the literature when there are around 500 target communities, while their performance is comparable to the baselines.

Ranking has significant applications in real life. It aims to evaluate the importance (or popularity) of two categories of objects, i.e., individuals and communities. Numerous efforts have been dedicated to these two types of rankings respectively. Instead, in this paper, we for the first time explore the co-ranking of both individuals and communities. Our insight lies in that co-ranking may enhance the mutual evaluation on both sides. To this end, we first establish an Evolving Coupled Graph that contains a series of smoothly weighted snapshots, each of which characterizes and couples the intricate interactions of both individuals and communities till a certain evolution time into a single graph. Then we propose an algorithm, called MIERank to implement the co-ranking of individuals and communities in the proposed evolving graph. The core idea of MIERank lies in a novel unbiased random walk, which, when sampling the interplay among nodes over different generation times, incorporates the preference knowledge of ranking by utilizing nodes' future actions. MIERank returns the co-ranking of both individuals and communities by iteratively alternating between their corresponding stationary probabilities of the unbiased random walk in a mutually-reinforcing manner. We prove the efficiency of MIERank in terms of its convergence, optimality and extensiblity. Our experiments on a big scholarly dataset of 606862 papers and 1215 fields further validate the superiority of MIERank with fast convergence and an up to 26% ranking accuracy gain compared with the separate counterparts.

This paper studies social network de-anonymization problem, which aims to identify users of an anonymized network by matching its user set with that of another auxiliary sanitized network. Prior arts primarily assume that both networks share exactly the same set of users, as opposed to many real situations of partially shared users in between. Different from the full matching case that only needs to take care of increasing the number of correctly matched pairs, the case of partial overlapping imposes additional demand on avoiding the wrong matches of those who do not have accounts across networks.To this end, we establish a new cost function, which we call the structural F-score to incorporate both the structural commonness and difference across networks. Intrinsically, the structural F-score computes the ratio of link agreements and disagreements, thus serving as the harmonic mean of precision and recall for any given matching function. Theoretically, we show that for networks parameterized by node overlap t2and link overlap s2, as long as the mean degree of networks grows as Ω(t-2s-3log n), maximizing the structural F-score provably ensures the perfect matching, where the nodal precision and recall are both maximized to 1. Algorithmically, for small-scale networks, we propose a two-step heuristic of F-score based de-anonymization, which firstly finds the optimal full matching between networks and then removes those pairs hindering structural F-score maximization. Due to the universal adaptability of the structural F-score, we further extend the algorithm to large-scale networks via a progressive matching process. Empirical results also validate the effectiveness of our methods in terms of improving the nodal F-score.

This paper studies the problem of source detection, which is to infer the source node out of an aftermath of a cascade, i.e., the observed infected graph GN of the network at some time. Prior arts have adopted various statistical quantities such as degree, distance or infection size to reflect the structural centrality of the source. In this paper, we propose a new metric which we call the infected tree entropy (ITE), to utilize richer underlying structural features for source detection. Our idea of ITE is inspired by the conception of structural entropy [1], which demonstrated that the minimization of average bits to encode the network structures with different partitions is the principle for detecting the natural or true structures in real-world networks. Accordingly, our proposed ITE based estimator for the source tries to minimize the coding of network partitions brought by the infected tree rooted at all the potential sources, thus minimizing the structural deviation between the cascades from the potential sources and the actual infection process included in GN. On polynomially growing geometric trees, with increasing tree heterogeneity, the ITE estimator remarkably yields more reliable detection under only moderate infection sizes. In contrast, for regular expanding trees, we still observe guaranteed detection probability of ITE estimator even with an infinite infection size, thanks to the degree regularity property. We also algorithmically realize the ITE based detection that enjoys linear time complexity via a message-passing scheme, and further extend it to general graphs. Experiments on various network topologies confirm the superiority of ITE to the baselines. For example, ITE returns an accuracy of 75% ranking the source among top 5%, far exceeding 45% of the classic algorithms on scale-free networks.

Knowledge diffusion is capable of narrowing the knowledge gap between individuals and is conducive to transforming knowledge into economically and socially valuable outcomes. Although knowledge diffusion is of particular importance, efficient modeling and analysis of knowledge diffusion may not be achieved easily. In this paper, we apply the concept of evolving knowledge graph (EKG) in modeling and analyzing knowledge diffusion and propose an EKG-based knowledge diffusion model. To characterize the relationships between researchers and papers in the proposed network model, we define three subnetworks, i.e., relationship subnetwork, citation subnetwork and author-paper subnetwork, and analyze the evolution process of the subnetworks. The knowledge diffusion process in the proposed network model is then examined. We analyze respectively the impacts of interpersonal contact and paper citation in knowledge diffusion, and propose a modified susceptible-infective-recovered-susceptible (SIRS) epidemic model-based knowledge diffusion process. Theoretical analysis is conducted to examine the expected values of the weighted degree of network entities, and the transmission threshold of knowledge diffusion process. Extensive simulations are performed to evaluate the performance of the proposed network model.

The von Neumann graph entropy (VNGE) is a measure of graph complexity based on the Laplacian spectrum. It has recently found applications in various learning tasks driven by networked data. However, it is computationally demanding and hard to interpret using simple structural patterns. Due to the close relation between Lapalcian spectrum and degree sequence, we conjecture that the structural information, defined as the Shannon entropy of the normalized degree sequence, might approximate VNGE well.

The cascading of sensitive information such as private contents and rumors is a severe issue in online social networks. One approach for limiting the cascading of sensitive information is constraining the diffusion among social network users. However, the diffusion constraining measures limit the diffusion of non-sensitive information diffusion as well, resulting in the bad user experiences. To tackle this issue, in this paper, we study the problem of how to minimize the sensitive information diffusion while preserve the diffusion of non-sensitive information, and formulate it as a constrained minimization problem where we characterize the intention of preserving non-sensitive information diffusion as the constraint. We study the problem of interest over the fully-known network with known diffusion abilities of all users and the semi-known network where diffusion abilities of partial users remain unknown in advance. By modeling the sensitive information diffusion size as the reward of a bandit, we utilize the bandit framework to jointly design the solutions with polynomial complexity in the both scenarios. Moreover, the unknown diffusion abilities over the semi-known network induce it difficult to quantify the information diffusion size in algorithm design. For this issue, we propose to learn the unknown diffusion abilities from the diffusion process in real time and then adaptively conduct the diffusion constraining measures based on the learned diffusion abilities, relying on the bandit framework. Extensive experiments on real and synthetic datasets demonstrate that our solutions can effectively constrain the sensitive information diffusion, and enjoy a 40 percent less diffusion loss of non-sensitive information comparing with four baseline algorithms.

Recent years have witnessed the rising popularity of urban vehicular crowd sensing (UVCS) systems that leverage drivers' mobile devices equipped with on-board sensors for various urban sensing tasks. Because of the importance of ensuring satisfactory spatio-temporal sensing coverage in such UVCS systems, most existing work has focus on designing efficient scheduling mechanisms to maximize the task completion rate under drivers' traveling constraints. Different from prior work, we propose Hector, a joint trajectory scheduling and incentive mechanism for spatio-temporal UVCS systems, which concentrates on capturing the interactive effects between scheduling and incentive mechanisms. Technically, we first reduce the dimensions of the original scheduling problem by mapping it into an augmented set cover problem with spatio-temporal constraints. Then, based on reverse combinatorial auctions, we design Hector, whose incentive mechanism with the presence of uncertain future trajectory information makes scheduling and compensation decisions in real-time. Specifically, Hector is truthful, individual rational and computationally efficient. Furthermore, the social cost yielded by Hector is close-to-optimal, and the approximation ratio is Hm. The advantageous properties of Hector are verified by both rigorous theoretical analysis and extensive simulations based on the real world datasets in the Chinese city Shenzhen which consists of 726,000 taxi trajectories.

In networks where massive sources make observations of same entities, we intend to seek thetruth– the most trustworthy value of each entity from conflicting information claimed by multiple sources. Various methods are proposed for accurately inferring both source reliability and truths, yet relying heavily on centralized settings that incur tremendous overhead to source side. In this paper, we offer adecentralizeddesign of truth discovery task that can fit favorably to the environments with limited resources. Considering that sources forming the connected network and making individual observations, we undertake the joint maximum likelihood estimation (MLE) of truth and source reliability. Our decentralization framework simply allows each source to maintain local information exchange at a time, and computes very basic functions of data observations. To this end, we facilitate the decentralization by simplifying the MLE problem into optimizing an objective function. Upon the proof of NP-hardness, two proposed decentralized algorithms (exact and approximation) are decentralized and randomized via a combination of algorithms from their centralized counterparts that ensure performance guarantee. The derived time complexity features explicit data/network dependent terms, which leads to further acceleration in truth finding. Remarkably, in two well connected networks like random geometric and preferential attachment graphs, the accelerated approximation method enjoys logarithmic time complexity while preserving comparable accuracy to the centralized counterparts. The effectiveness of the proposed decentralizations are further empirically confirmed.

Urban traffic flow forecasting is a critical issue in intelligent transportation systems. It is quite challenging due to the complicated spatiotemporal dependency and essential uncertainty brought about by the dynamic urban traffic conditions. In most of existing methods, the spatial correlation is captured by utilizing graph neural networks (GNNs) throughout a fixed graph based on local spatial proximity. However, urban road conditions are complex and changeable, which leads to the interactions between roads should also be dynamic over time. In addition, the global contextual information of roads are also crucial for accurate forecasting. In this paper, we exploit spatiotemporal correlation of urban traffic flow and construct a dynamic weighted graph by seeking both spatial neighbors and semantic neighbors of road nodes. Multi-head self-attention temporal convolution network is utilized to capture local and long-range temporal dependencies across historical observations. Besides, we propose an adaptive graph gating mechanism to extract selective spatial dependencies within multi-layer stacking and correct information deviations caused by artificially defined spatial correlation. Extensive experiments on real world urban traffic dataset from Didi Chuxing GAIA Initiative have verified the effectiveness, and the multi-step forecasting performance of our proposed models outperforms the state-of-the-art baselines. The source code of our model is publicly available at https://github.com/RobinLu1209/STAG-GCN.

Distributed computing is known for its high efficiency of processing large amounts of data in parallel, at the expense of communication load between different servers. Coding was introduced to minimize the communication load by exploiting the repetitive computing, thus drawing great attention within the academia. Most existing works assume that all servers are identical in computational capability, which is inconsistent with practical scenarios. In this paper, we investigate a distributed computing system that consists of two types of servers, i.e., fast servers and slow servers. Due to the heterogeneous computational capabilities within the system, the overall computation time will be delayed by the slow servers, which is called the straggling effect. To this end, we develop a novel framework of coding-based distributed computing to alleviate the straggling effect. Specifically, for a given number of fast servers and slow servers with their corresponding computational capabilities, we aim to minimize the overall computation time by assigning different amounts of workloads to different servers. Further, we derive the information-theoretic lower bound of the communication load of the system, which is shown to be within a constant multiplicative gap to the achievable communication load by our scheme.

The best arm identification problem in multi-armed bandit model has been widely applied into many practical applications, such as spectrum sensing, online advertising, and cloud computing. Although lots of works have been devoted into this area, most of them do not consider the cost of pulling actions, i.e., a player has to pay some cost when she pulls an arm. Motivated by this, we study a ratio-based best arm identification problem, where each arm is associated with a random reward as well as a random cost. For any δ ∈ (0, 1), with probability at least 1-δ, the player aims to find the optimal arm with the largest ratio of expected reward to expected cost using as few samplings as possible. To solve this problem, we propose three algorithms: 1) a genie-aided algorithm GA; 2) the successive elimination algorithm with unknown gaps SEUG; 3) the successive elimination algorithm with unknown gaps and variance information SEUG-V, where gaps denote the differences between the optimal arm and the suboptimal arms. We show that for all three algorithms, the sample complexities, i.e., the pulling times for all arms, grow logarithmically as 1/δ increases. Moreover, compared to existing works, the running of our elimination-type algorithms is independent of the arm-related parameters, which is more practical. In addition, we also provide a fundamental lower bound for sample complexities of any algorithms under Bernoulli distributions, and show that the sample complexities of the proposed three algorithms match that of the lower bound in the sense of log 1/δ. Finally, we validate our theoretical results through numerical experiments.

In the contemporary era of information explosion, we are often faced with the mixture of massive truth (true information) and rumor (false information) flooded over social networks. Under such circumstances, it is very essential to infer whether each claim (e.g., news, messages) is a truth or a rumor, and identify their sources, i.e., the users who initially spread those claims. While most prior arts have been dedicated to the two tasks respectively, this paper aims to offer the joint inference on truth/rumor and their sources. Our insight is that a joint inference can enhance the mutual performance on both sides.To this end, we propose a framework named SourceCR, which alternates between two modules, i.e., credibility-reliability training for truth/rumor inference and division-querying for source detection, in an iterative manner. To elaborate, the former module performs a simultaneous estimation of claim credibility and user reliability by virtue of an Expectation Maximization algorithm, which takes the source reliability outputted from the latter module as the initial input. Meanwhile, the latter module divides the network into two different subnetworks labeled via the claim credibility, and in each subnetwork launches source detection by applying querying of theoretical budget guarantee to the users selected via the estimated reliability from the former module. The proposed SourceCR is provably convergent, and algorithmic implementable with reasonable computational complexity. We empirically validate the effectiveness of the proposed framework in both synthetic and real datasets, where the joint inference leads to an up to 35% accuracy of credibility gain and 29% source detection rate gain compared with the separate counterparts.

The interaction among users in different social networks raises deep concern on user privacy, as it may facilitate the assailants to identify user identities by matching the anonymized networks with a correlated sanitized one. Prior arts regarding such de-anonymization problem can be primarily divided into a seeded case or a seedless one, depending on whether or not there are a subset of pre-identified nodes. The seedless case is much more complicated since the adjacency matrix representation of one-hop user relations delivers limited structural information. To address this issue, we, for the first time, integrate the multi-hop neighborhood relationships, which exhibit more structural commonness between the anonymized and the sanitized networks, into seedless de-anonymization process. Our aim is to sufficiently leverage these multi-hop neighbors of all nodes and minimize the total disagreements of these multi-hop adjacency matrices, which we call collective adjacency disagreements (CADs), between two networks of different sizes. Theoretically, we demonstrate that CAD enlarges the difference between wrongly matched node pairs and correctly matched pairs, whereby two networks can be correctly matched with high probability even when the network density is below logn. Algorithmically, we adopt the conditional gradient descending method on a collective-form objective, which can efficiently find the minimal CADs for networks with broad degree distributions. Experiments on both synthetic and realworld networks return desirable de-anonymization accuracies thanks to the rich structural information manifested by such collectiveness, since most nodes can be correctly matched with their correspondences, especially in sparse networks where merely utilizing adjacency relations might fail to work.

Social network de-anonymization, which refers to re-identifying users by mapping their anonymized network to a correlated network, is an important problem that has received intensive study in network science. However, it remains less understood how network structural features intrinsically affect whether or not the network can be successfully de-anonymized. To find the answer, this paper offers the first general study on the relation between de-anonymizability and network symmetry. To this end, we propose to capture the symmetry of a graph by the concept of graph bijective homomorphism. By defining the matching probability matrix, we are able to characterize the de-anonymizability, i.e., the expected number of correctly matched nodes. Specifically, we show that for a graph pair with arbitrary topology, the de-anonymizability is equal to the maximal diagonal sum of the matching probability matrix generated from homomorphisms. Due to the prohibitive cost of enumerating all possible homomorphisms, we further obtain an upper bound of such de-anonymizability by counting the orbits of each of the two graphs, which significantly reduces the computational cost. Such a general result allows us to theoretically obtain the de-anonymizability of any networks with more specific topology structure. For example, for any classic Erdős-Rènyi graph with designated n and p, we can represent its de-anonymizability numerically by calculating the local symmetric structure that it contains. Extensive experiments are performed to validated our findings.

In camera sensor networks (CSNs), full view coverage, meaning that any direction of any point in the operational region is covered by at least one camera sensor, plays a significant role in object identification. While prior work is dedicated to static CSNs for the sake of critical condition to achieve full view coverage, such performance still remains unknown in mobile CSNs. In this paper, we take the initiative to address this issue, where a centralized parameter, i.e., equivalent sensing radius (ESR), is defined to unravel the critical requirement for asymptotic full view coverage in mobile heterogeneous CSNs in the sense that camera sensors of different sensing capabilities are moving around in target area. Specifically, we derive ESR under three different mobilities, i.e., 1-dimensional and 2-dimensional random walks and random rotating model, and then explore respectively the corresponding critical conditions to achieve almost surely coverage.1 The static network is introduced as a baseline in order to gain a clear understanding of how mobility affects coverage performance differently. Interestingly, we find that both 1-dimensional and 2-dimensional random walks exhibit a smaller ESR than static one whereas ESR is even larger in random rotating mobility than that in static CSNs. Moreover, the almost surely coverage is found to be around 1.225 times of the critical condition to achieve coverage with high probability,2 and therefore turns out to be a stronger result compared to the traditional coverage with high probability. We then turn to the impact of various mobility patterns on sensing energy consumption, a metric that is closely related to ESR, and show that it can be decreased by random walks under certain delay tolerance. The relationship between ESR and percentage of full view coverage is also discussed and the results unify those under homogeneous CSNs.

Cooperative offloading in mobile edge computing enables resource-constrained edge clouds to help each other with computation-intensive tasks. However, the power of such offloading could not be fully unleashed, unless trust risks in collaboration are properly managed. As tasks are outsourced and processed at the network edge, completion latency usually presents high variability that can harm the offered service levels. By jointly considering these two challenges, we propose OLCD, an Online Learning-aided Cooperative offloaDing mechanism under the scenario where computation offloading is organized based on accumulated social trust. Under co-provisioning of computation, transmission, and trust services, trust propagation is performed along the multi-hop offloading path such that tasks are allowed to be fulfilled by powerful edge clouds. We harness Lyapunov optimization to exploit the spatial-temporal optimality of long-term system cost minimization problem. By gap-preserving transformation, we decouple the series of bidirectional offloading problems so that it suffices to solve a separate decision problem for each edge cloud. The optimal offloading control can not materialize without complete latency knowledge. To adapt to latency variability, we resort to the delayed online learning technique to facilitate completion latency prediction under long-duration processing, which is fed as input to queued-based offloading control policy. Such predictive control is specially designed to minimize the loss due to prediction errors over time. We theoretically prove that OLCD guarantees close-to-optimal system performance even with inaccurate prediction, but its robustness is achieved at the expense of decreased stability. Trace-driven simulations demonstrate the efficiency of OLCD as well as its superiorities over prior related work.

With the rapid spread of mobile devices, many traditional online social network services, like academic applications, start to develop mobile apps and improve their service quality through mobile sensing. A rich friendship among users can provide support for such applications, e.g., help to delegate sensing tasks in mobile crowd sensing. Therefore, studying friend recommendation that offers users' suggestions on who to connect to, so as to enrich the user's friendship, is necessary to Mobile Social Networks (MSNs). Most existing strategies utilize user's relationship, or similarity, to make the recommendation, which overlooks the existence of multi-type connections among users, e.g., common paper based and common topic based connections among authors in academic networks. To overcome such limitation, we characterize each type of connections by a corresponding network layer and then propose a novel algorithm for joint recommendations in multilayer MSNs. Particularly, two types of results are presented in the paper. (i) Our proposed algorithm, named as Cross-layer 2-hop Path (C2P) algorithm, implements the joint recommendation by suggesting a user establish connections to his cross-layer two-hop neighbors, i.e., those who link to the user by two-hop paths with the two hops belonging to two different layers, respectively. In doing so, each produced recommendation item is a combination of user relationships in both two layers and therefore can better meet user demands. (ii) By analytical derivations, along with further empirical validation on real datasets, we give the performance evaluation on our proposed algorithm. First, we prove that the algorithm is efficiently implementable with a constant complexity of each recommendation in most cases. Then, we evaluate its recommendation performance by two metrics, i.e., accuracy and diversity, where the former metric measures recommendation accuracy and the latter one measures an algorithm's capability to provide diverse recommendation items. Our results show that C2P algorithm is optimal in terms of accuracy and for diversity, its performance is no less than the algorithm that is applied in single layers. And finally, the effectiveness of the proposed algorithm is validated on both synthetic and large-scale real datasets, where it outperforms the baseline algorithms with an up to 32 percent accuracy gain and obtains an approximately 0.5 ratio of the algorithm's diversity to the theoretical upperbound.

Crowdsensing paradigm facilitates a wide range of data collection, where great efforts have been made to address its fundamental issues of matching workers to their assigned tasks and processing the collected data. In this paper, we reexamine these issues by considering the spatio-temporal worker mobility and task arrivals, which more fit the actual situation. Specifically, we study the location-aware and location diversity based dynamic crowdsensing system, where workers move over time and tasks arrive stochastically. We first exploit offline crowdsensing by proposing a combinatorial algorithm, for efficiently distributing tasks to workers. After that, we mainly study the online crowdsensing, and further consider an indispensable aspect of worker's fair allocation. Apart from the stochastic characteristics and discontinuous coverage, the non-linear expectation is incurred as a new challenge concerning fairness issue. Based on Lyapunov optimization with perturbation parameters, we propose online control policy to overcome those challenges. Hereby, we can maintain system stability and achieve a time average sensing utility arbitrarily close to the optimum. Finally, we propose an optimization framework to aggregate the sensing data which can estimate worker expertise and task truth simultaneously. Performance evaluations on real and synthetic data set validate the proposed algorithm, where 80 percent gain of fairness is achieved at the expense of 12 percent loss of sensing value on average.

Influence Maximization (IM) aims to maximize the number of people that become aware of a product by finding the “best” set of “seed” users to initiate the product advertisement. Unlike most prior arts on the static networks containing fixed number of users, we study the evolving IM in more realistic evolving networks with temporally growing topology. The task of evolving IM, however, is far more challenging over static cases in the sense that the seed selection should consider its impact on future users who will join network during influence diffusion and the probabilities that users influence one another also evolve over time. We address the challenges brought by network evolution through EIM, a newly proposed bandit-based framework that alternates between seed nodes selection and knowledge (i.e., nodes’ growing speed and evolving activation probabilities) learning during network evolution. Remarkably, the EIM framework involves three novel components to handle the uncertainties brought by evolution: (1) A fully adaptive particle learning of nodes’ growing speed for accurately estimating future influenced size, with real growing behaviors delineated by a set of weighted particles. (2) A bandit-based refining method with growing arms to cope with the evolving activation probabilities via growing edges from previous influence diffusion feedbacks. (3) Evo-IMM , an evolving seed selection algorithm, which leverages the Influence Maximization via Martingale (IMM) framework, with the objective to maximize the influence spread to highly attractive users during evolution. Theoretically, the EIM framework returns a regret bound that provably maintains its sublinearity with respect to the growing network size. Empirically, the effectiveness of the EIM framework is also validated with three notable million-scale evolving network datasets possessing complete social relationships and nodes’ joining time. The results confirm the superiority of the EIM framework in terms of an up to 50% larger influenced size over four static baselines.

The advent of social networks poses severe threats on user privacy as adversaries can de-anonymize users' identities by mapping them to correlated cross-domain networks. Without ground-truth mapping, prior literature proposes various cost functions in hope of measuring the quality of mappings. However, their cost functions, whose minimizers may remain algorithmically unknown, usually bring imponderable mapping errors when the true mapping cannot minimize these cost functions. We jointly tackle above concerns under a more practical social network model parameterized by overlapping communities, which, neglected by prior art, can serve as side information for de-anonymization. Regarding the unavailability of ground-truth mapping to adversaries, by virtue of the Minimum Mean Square Error (MMSE), our first contribution is a well-justified cost function minimizing the expected number of mismatched users over all possible true mappings. While proving the NP-hardness of minimizing MMSE, we validly transform it into the weighted-edge matching problem (WEMP), which, as disclosed theoretically, resolves the tension between optimality and complexity: 1) WEMP asymptotically returns a negligible mapping error in large network size under mild conditions facilitated by higher overlapping strength; 2) WEMP can be algorithmically characterized via the convex-concave based de-anonymization algorithm (CBDA), effectively finding the optimum of WEMP. Extensive experiments further confirm the effectiveness of CBDA under overlapping communities: 90% users are re-identified averagely in a series of networks when communities overlap densely, and the re-identification ratio is enhanced about 70% compared to non-overlapping cases.

With the popularization of smart devices and social platforms (Facebook, Instagram and etc.), content transmission is becoming an increasingly prevalent form of human interaction with transmission time being a critical issue in miscellaneous applications. Extensive works have been devoted to this problem with the typical assumption that the network is non-evolving. In contrast, real-world networks which the transmission runs through are widely observed to be evolving over time and thus display distinctive properties. In this paper, we make the first study of content transmission in evolving networks. Particularly, we focus on the specific transmission time of the content, which is an important performance metric. For a comprehensive analysis, we consider both static and mobile cases. The network evolves in the following sense: each new user randomly chooses a geographic location while establishing social relations with existing users according to the evolving model, called Affiliation Networks. The transmission scheme running on the network exploits both social relationships and geographic information. While revealing the microscopic property of evolving social networks as the basis, in both static and mobile cases we manage to bound the transmission time in evolving networks which departs from results in non-evolving networks. In both cases, we find that the transmission time in evolving networks is smaller than the non-evolving counterpart under our scheme, and the gap is constantly increasing over time. Especially, the mobile case obtains such gain with less geographic knowledge. The theoretical findings are confirmed by experiments on both synthetic and real networks under different settings. We find that transmission time in evolving networks is smaller than non-evolving counterparts under the tested settings, and our proposed algorithms outperform the baselines.

Many practical applications have observed knowledge evolution, i.e., continuous born of new knowledge, with its formation influenced by the structure of historical knowledge. This observation gives rise to evolving knowledge graphs whose structure temporally grows over time. However, both the modal characterization and the algorithmic implementation of evolving knowledge graphs remain unexplored. To this end, we propose EvolveKG, a framework that reveals cross-time knowledge interaction with desirable performance of storage and computation. The novelty of EvolveKG lies in Derivative Graph - a static weighted snapshot of evolution at a certain time. Particularly, each weight quantifies knowledge effectiveness with a temporarily decaying function of consistency and attenuation, two proposed factors depicting whether or not the effectiveness of a fact fades away with time. Thanks to the cross-time interaction, EvolveKG allows future knowledge prediction by virtue of the influence from the historical ones. Empirically tested under two real datasets, the superiority of EvolveKG is confirmed via its prediction accuracy.

We study the source detection problem using limited timestamps on a given network. Due to the NP-completeness of the maximum likelihood estimator (MLE), we propose an approximation solution called infection-path-based estimator (INF), the essence of which is to identify the most likely infection path that is consistent with observed timestamps. The source node associated with that infection path is viewed as the estimated source û. For the tree network, we transform the INF into integer linear programming and find a reduced search region using BFS, within which the estimated source is provably always on a path termed as candidate path. This notion enables us to analyze the accuracy of the INF in terms of error distance on arbitrary tree. Specifically, on the infinite g-regular tree with uniform sampled timestamps, we get a refined performance guarantee in the sense of a constant bounded d(u*, û). By virtue of time labeled BFS tree, the estimator still performs fairly well when extended to more general graphs. Simulations on both trees and general networks further demonstrate the superior performance of the INF.

The omnipresence of cascading process in complex phenomena makes the identification of a small set of influential units, which is widely believed to trigger the outbreak, always an crucial issue in network science. Formulated as Influence maximization (IM) in 2003, this NP-hard problem has received a multitude of heuristic solutions with diverse angles. However, these methods are often unable to provide reliable solutions, due to the lack of an exact metric for evaluating units' contributions on cascading.

Crowdsourcing is an effective paradigm in human centric computing for addressing problems by utilizing human computation power, especially in booming social Internet of Things (IoT). By leveraging mutual friendship between computing entities (i.e., workers), collaborative tasks can thus be routed and finally fulfilled by multihop friends with high expertise. However, crowdsourcing in social IoT may reveal the privacy of task requesters which results in a large dilemma. In this paper, we focus on designing a multihop routing incentive mechanism which can also preserve task requester's privacy. Specifically, a utility maximization problem under privacy and budget feasibility constraints is formulated. Defining the conditions for privacy insurance, we give guidelines on how many subtasks should an entire task be divided into, and analyze the tradeoff between privacy and task accuracy. To enable efficient crowdsourcing task routing in social IoT, we first consider 1-hop myopic routing case and propose a near-optimal task assignment algorithm with 1/2 approximation ratio for an arbitrary prior knowledge. We further design multihop payment policy to establish an equilibrium where workers are motivated to forward subtasks to their friends with the best expertise. The extensive simulations validate that our mechanism achieves a high level of average information gain with modest privacy guarantee.

Energy-efficient and secure wireless communications have recently earned tremendous interests due to economic, environmental, and military concerns. This paper investigates the tradeoff between the secrecy throughput and the energy efficiency in cognitive radio networks (CRNs), where primary and secondary users with different priorities of spectrum access can either interfere or cooperate with each other. To gain an understanding of the intricate effects that system parameters have on underlay network's performance, we exclusively focus on characterizing several key aspects that may have potential impacts on secure underlay CRNs, including the transmission power, the number of interfering users, and the designed interference resistance coefficient. Based on the obtained analytical results, we further propose a cooperative spectrum sharing paradigm to improve both the secrecy throughput and the energy efficiency of primary users. The main idea is that primary users allow secondary users to simultaneously access the licensed spectrum and in return, the secondary transmitter acts as both a relay for primary transmissions and a friendly jammer against eavesdropping, in case the primary transmission fails. Both theoretical and numerical results reveal that: (i) When the interference from secondary transmitters is small, there is an optimal transmission power that maximizes the secrecy throughput for primary users compared to CRNs without the security issue. (ii) When the interference from secondary transmitters is large, the secrecy throughput increases with the transmission power for primary users. (iii) The transmission power that maximizes the energy efficiency is smaller than that maximizes the secrecy throughput for primary users. (iv) The number of interfering users has a slight impact on the secrecy throughput and the energy efficiency of primary users due to the secondary power control. (v) The proposed cooperative paradigm is an efficient approach to boost both the secrecy throughput and the energy efficiency of primary users compared with the traditional non-cooperative spectrum sharing, and provides an alternative method to compensate for the interference caused by secondary users.

In most existing routing algorithms for mobile ad hoc cognitive networks (MACNets), nodes are configured with a fixed even maximal transmission power. Links set up by such the algorithms often suffer from excessive co-channel interference, which significantly downgrades performance of MACNets because the link stability highly depends on not only node mobility but also co-channel interference. In this paper, we investigate how to improve route stability through jointly considering routing with adaptive power adjustment and mobility control. We first propose a set of power adjustment policies which dynamically sets up transmission power of cognitive nodes to enable the duration of links potentially interfered as long as possible. We, then, design a routing metric called integrated link stability (ILS) to quantitatively measure the link stability. This novel metric ILS considers both node mobility and channel interference. Finally, we propose a Joint Stable Routing and Adaptive Power Adjustment (J-SRAPA) algorithm for multi-flow and multi-hop MACNets, with the objective of maximizing network throughput. J-SRAPA dynamically adjusts the transmission power in a distributed way to mitigate co-channel interference and to improve channel utilization ratio accordingly, during both route setup and data transmission. NS2-based simulation results demonstrate that our J-SRAPA significantly outperforms related routing algorithms in terms of network throughput, end-to-end transmission delay, and packet loss ratio; and the higher channel interference degree MACNets experience, the more improvement our J-SRAPA will bring to the networks.

Self-calibrating wireless indoor localization systems construct the radio map even the indoor floor plan automatically, which avoids the labor-intensive site survey process; however, existing systems utilizing the feature of Wi-Fi signals can only provide coarse-grained indoor maps, which hinders improvement of localization accuracy. In this paper, we present FineLoc, a fine-grained self-calibrating localization system based on the freely-deployed Bluetooth low energy (BLE) nodes and crowd-sourced data, which can profile more detailed layout information of the indoor space. We first reveal that existing systems can only generate inaccurate floor plans owning to the coarse-grained Wi-Fi reference information. Then, we utilize the increasingly popular BLE beacon nodes as the source of reference information, with which a series of dead-reckoning optimization and new schemes particularly for finer-grained indoor map construction are presented. We implement a prototype FineLoc system, which is deployed in around 11,000 m2areas. Our experimental results with the prototype show that FineLoc can achieve 80 percent localization errors within 1.6 m, 1.4 m, and 1.1 m in the library, classroom building, and office building, respectively, with an average density of deployed BLE nodes less than 2.6/100 m2.

In many real-world networks, entities of different types usually form an evolving network with hybrid interactions. However, how to theoretically model such networks, along with quantitive characterizations, remains unexplored. Motivated by this, we develop a novel evolving model, which, as validated by our empirical results, can well capture some basic properties such as power-law degree distribution, densification, shrinking diameter, and community structure embodied in most real datasets. Particularly, two types of results are presented in this paper. First, our proposed model, namely, evolving K-Graph, consists of K-node sets representing K different types of entities. The hybrid interactions among entities, based on whether they belong to the same type, are classified into inter-type and intra-type ones that are, respectively, characterized by two joint graphs evolving over time. Following our newly proposed mechanism called interactive-evolution, potential connections can be established among nodes with common features and further form a positive feedback. The superiorities of our model are three folded: good capture of realistic networks, mathematical tractability and efficient implementation. Second, by analytical derivations, along with empirical validation on real datasets, we disclose two aspects of network properties: basic ones as power-law degree distribution, densification, shrinking diameter and community structure, as well as a distinctive one, that is, positive correlation observed in real networks, implying that a hub in one inter-type relationship network also has many neighbors in another one. An additional interesting finding is that through further comparison of models with or without interactive-evolution, the former one leads to an even earlier occurrence of network connectivity.

Due to the random and dynamic energy-harvesting process, it is challenging to conduct optimal rate control in Energy-Harvesting Communication Systems (EHCSs). Existing works mainly focus on two cases: (1) the traffic load is infinite (as long as there is energy, there is data to transmit), in which the objective is to optimize the rate control policy subject to the dynamic energy arrivals, thus maximizing the average system throughput; and (2) the traffic load is finite, in which the objective is to optimize the rate control policy, thus minimizing the time by which all packets are delivered. In this work, we focus on the optimal rate control of EHCSs from another important and practical perspective, where the data and energy arrivals are both random. Given any deadline of T , our goal is to maximize the total throughput in [0, T ]. Specifically, two scenarios are considered: (1) energy is ready before the transmission; and (2) energy arrives randomly during the transmission. In both scenarios, we assume that the data arrive randomly during the transmission. For the first scenario, we develop a novel Stepwise Searching Algorithm (SSA) based on the cumulative curve methodology, which is shown to achieve the optimal solution and the complexity grows only linearly with the problem size. In addition, the SSA can provide a simple and appealing graphical visualization of approximating the optimal solution. For the second scenario, we provide a simplified case study that can be solved by the SSA with low computation overhead and demonstrate the difficulties in solving the general setting, which initiates a first step toward the full understanding of the scenario when energy arrives randomly during the transmission.

Motivated by the requirement of heterogeneity in the Internet of Things, we initiate the joint study of capacity and energy efficiency scaling laws in heterogeneous wireless sensor networks, and so on. The whole network is composed of n nodes scattered in a square region with side length L = n α , and there are m = n ν home points { c j } j=1 m , where a generic home point c j generates q j nodes independently according to a stationary and rotationally invariant kernel k ( c j , ⋅). Among the n nodes, we schedule n s independent multicast sessions each consisting of k − 1 destination nodes and one source node. According to the heterogeneity of nodes’ distribution, we classify the network into two regimes: a cluster-dense regime and a cluster-sparse regime. For the cluster-dense regime, we construct single layer highway system using percolation theory and then build the multicast spanning tree for each multicast session. This scheme yields the Ω( n ½+(α − ½)γ / n s √ k ) per-session multicast capacity. For the cluster-sparse regime, we partition the whole network plane into several layers and construct nested highway systems. The similar multicast spanning tree yields the Ω( n ½−(1− ν)γ/2 / n s √ k ) per-session multicast capacity, where γ is the power attenuation factor. Interestingly, we find that the bottleneck of multicast capacity attributes to the network region with largest node density, which provides a guideline for the deployment of sensor nodes in large-scale sensor networks. We further analyze the upper bound of multicast capacity and the per-session multicast energy efficiency. Using both synthetic networks and real-world networks (i.e., Greenorbs), we evaluate the asymptotic capacity and energy efficiency and find that the theoretical scaling laws are gracefully supported by the simulation results. To our best knowledge, this is the first work verifying the scaling laws using real-world large-scale sensor network data.

In this paper, we propose a novel community detection model, which explores the dynamic community evolutions in temporal social networks by modeling temporal affiliation strength between users and communities. Instead of transforming dynamic networks into static networks, our model utilizes normal distribution to estimate the change of affiliation strength more concisely and comprehensively. Extensive quantitative and qualitative evaluation on large social network datasets shows that our model achieves improvements in terms of prediction accuracy and reveals distinctive insight about evolutions of temporal social networks.

Social recommendation has been widely applied to offer users suggestions on who to connect to, where most existing strategies overlook the existence of multi-type connections among users. To overcome such limitation, we characterize each type of connections by a corresponding network layer and then propose a novel algorithm for joint recommendations in cross-layer social networks. Particularly, two types of results are presented in the paper. (i) Our proposed algorithm, named as Cross-layer 2-hop Path (C2P) algorithm, implements the joint recommendation by suggesting a user establish connections to his cross-layer two-hop neighbors, i.e., those who link to the user by two-hop paths with the two hops belonging to two different layers, respectively. In doing so, each produced recommendation item is a combination of user relationships in both two layers and thus can better meet user demands. (ii) By analytical derivations, along with further empirical validation on real datasets, we give the performance evaluation on our proposed algorithm. Firstly, we prove that the algorithm is efficiently implementable with a constant complexity in each recommendation. Then, we evaluate its recommendation performance by two metrics, i.e., acceptance and diversity, where the former metric measures recommendation accuracy and the latter one measures an algorithm's capability to provide diverse recommendation items. Our results show that C2P algorithm is optimal in terms of acceptance and for diversity, its performance is in the same order of the theoretical upperbound. And finally, the effectiveness of the proposed algorithm is validated by our simulations on three real datasets, where it outperforms baseline algorithms with an up to 38% acceptance gain and obtains an around 0.5 diversity ratio to the theoretical upperbound.

The advent of social networks poses severe threats on user privacy as adversaries can de-anonymize users' identities by mapping them to correlated cross-domain networks. Without ground-truth mapping, prior literature proposes various cost functions in hope of measuring the quality of mappings. However, there is generally a lacking of rationale behind the cost functions, whose minimizer also remains algorithmically unknown. We jointly tackle above concerns under a more practical social network model parameterized by overlapping communities, which, neglected by prior art, can serve as side information for de-anonymization. Regarding the unavailability of ground-truth mapping to adversaries, by virtue of the Minimum Mean Square Error (MMSE), our first contribution is a well-justified cost function minimizing the expected number of mismatched users over all possible true mappings. While proving the NP-hardness of minimizing MMSE, we validly transform it into the weighted-edge matching problem (WEMP), which, as disclosed theoretically, resolves the tension between optimality and complexity: (i) WEMP asymptotically returns a negligible mapping error in large network size under mild conditions facilitated by higher overlapping strength; (ii) WEMP can be algorithmically characterized via the convex-concave based de-anonymization algorithm (CBDA), finding the optimum of WEMP. Extensive experiments further confirm the effectiveness of CBDA under overlapping communities, in terms of averagely 90% re-identified users in the rare true cross-domain co-author networks when communities overlap densely, and roughly 70% enhanced reidentification ratio compared to non-overlapping cases.

This paper studies the problem of optimizing multicast energy consumption in delay-constrained mobile wireless networks, where information from the source needs to be delivered to all the k destinations within an imposed delay constraint. Most existing works simply focus on deriving transmission schemes with the minimum transmitting energy, overlooking the energy consumption at the receiver side. Therefore, in this paper, we propose ConMap, a novel and general framework for efficient transmission scheme design that jointly optimizes both the transmitting and receiving energy. In doing so, we formulate our problem of designing minimum energy transmission scheme, called DeMEM, as a combinatorial optimization one, and prove that the approximation ratio of any polynomial time algorithm for DeMEM cannot be better than (1/4) lnk. Aiming to provide more efficient approximation schemes, the proposed ConMap first converts DeMEM into an equivalent directed Steiner tree problem through creating auxiliary graph gadgets to capture energy consumption, then maps the computed tree back into a transmission scheme. The advantages of ConMap are threefolded: 1) Generality- ConMap exhibits strong applicability to a wide range of energy models; 2) Flexibility- Any algorithm designed for the problem of directed Steiner tree can be embedded into our ConMap framework to achieve different performance guarantees and complexities; 3) Efficiency- ConMap preserves the approximation ratio of the embedded Steiner tree algorithm, to which only slight overhead will be incurred. The three features are then empirically validated, with ConMap also yielding near-optimal transmission schemes compared to a brute-force exact algorithm. To our best knowledge, this is the first work that jointly considers both the transmitting and receiving energy in the design of multicast transmission schemes in mobile wireless networks.

Location-aware viral marketing is crucial in modern commercial applications for attracting customers to certain points of interests. Prior works are mainly based on formulating it into a location-aware influence maximization problem in Geo-social Networks (GSNs), where $K$ initial seed individuals are selected in hope of maximizing the number of final influenced users. In this paper, we present the first look into the group-level location promotion, which can potentially enhance its performance, with the phenomenon that users belonging to the same geo-community share similar moving preferences. We propose GLP, a new and novel framework of group-level location promotion by virtue of geo-communities, each of which is treated as a group in GSNs. Aiming to attract more users to designated locations, GLP firstly carries out user grouping through an iterative learning approach based on information extraction from massive check-ins records. The advantage of GLP is three-folded: i) by aggregating movements of group members, GLP significantly avoids the sparsity and sporadicity of individual check-ins, and thus obtains more reliable mobility models; ii) by generalizing a new group-level social graph, GLP can exponentially reduce the computational complexity of seed nodes selection that is algorithmically executed by a greedy algorithm; iii) in comparison with prior individual-level cases, GLP is theoretically demonstrated to drastically increase influence spread under the same given budget. Extensive experiments on real datasets demonstrate that the GLP outperforms four baselines, with notably up to 10 times larger influence spread and 100 times faster seed selection over two individual-level cases, meanwhile verifying the impact of group numbers in final influence spread.

Many realistic wireless social networks are evolving over time. While network evolution has its important influence on network performances, it is nevertheless overlooked in most existing studies on information diffusion. Motivated by this, in this paper, we investigate the delivery accuracy of interest-aware information diffusion in evolving social networks. In doing so, we adopt a model, named affiliation networks, to characterize network evolution from three aspects, i.e., the arrival of new users, the generation of new interests, and the creation of new links between them. Based on that, we consider a publishing based information diffusion mechanism that widely exists in wireless networking services such as Facebook, Twitter, and Sina Weibo, where a user receives data items from his friends and then republishes the ones he is interested in to all his friends. Under the above network model, we study how the performance metric such as delivery accuracy is affected by the network evolution. The publishing based information diffusion mechanism is a blind targeting one that may suffer a low delivery accuracy. However, our analytical results demonstrate a contrary finding that the delivery accuracy is improved over time, and even more surprisingly, we disclose that with a sufficiently long evolving time, the delivery accuracy can achieve a perfect state where those who receive the data are exactly the ones that are interested in it. In addition, our theoretical findings are verified by experimental measurements through a social network dataset from Facebook.

Cache-enabled wireless networks have gained increasing popularity in recent years for facilitating the delivery of content. Most existing works assumed that the network is static without the change of users and content, which is not the case in the real world. In this paper, we study the content delivery in cache-enabled wireless networks, where the network evolves in terms of users and content. We adopt the affiliation network model to reveal the network evolution process, where new users and content are added into the network randomly and connected with existing nodes via the preferential attachment. Users with strong social relations tend to request the same content objects, thus content popularity is sharply concentrated. Therefore, caching technique is more effective. To maximize the content delivery rate, we formulate the optimization problem of caching replication jointly with routing strategy. We show that network evolution can greatly improve the content delivery rate. In particular, when per-user cache capacity is in the order of Θ(1), per-user delivery rate can achieve constant, i.e., the network can scale. Finally, theoretical results are validated based on a real-world data set from Facebook.

Autonomous vehicle industry is developing by leaps and bounds. We envisage a situation where autonomous vehicles act as taxis to transport clients. During the transportation, vehicle sharing is enabled and encouraged. We propose fair allocation in payment for passengers of a shared vehicle. The allocation is endowed with the characteristics of envy freeness and maximin utilities. Furthermore, we devise working mechanisms for autonomous vehicles, including (i) planning routes with minimum detour; (ii) choosing clients to recommend vehicle sharing; (iii) carrying passengers continuously. Our work may serve as a good preparation for the marketization of autonomous taxis.

A crucial privacy-driven issue nowadays is re- identifying ano-nymized social networks by mapping them to correlated cross-domain auxiliary networks. Prior works are typically based on modeling social networks as random graphs representing users and their relations, and subsequently quantify the quality of mappings through cost functions that are proposed without sufficient rationale. Also, it remains unknown how to algorithmically meet the demand of such quantifications, i.e., to find the minimizer of the cost functions. We address those concerns in a more realistic social network modeling parameterized by community structures that can be leveraged as side information for de- anonymization. By Maximum A Posteriori (MAP) estimation, our first contribution is new and well justified cost functions, which, when minimized, enjoy superiority to previous ones in finding the correct mapping with the highest probability. The feasibility of the cost functions is then for the first time algorithmically characterized. While proving the general multiplicative inapproximability, we are able to propose two heuristics, which, respectively, enjoy an ε-additive approximation and a conditional optimality in carrying out successful user re- identification. Our theoretical findings are empirically validated,with a notable dataset extracted from rare true cross-domain networks that reproduce genuine social network de-anonymization.

Determination of source-destination connectivity in networks has long been a fundamental problem, where most existing works are based on deterministic graphs that overlook the inherent uncertainty in network links. To overcome such limitation, this paper models the network as an uncertain graph where each edge e exists independently with some probability p(e). The problem examined is that of determining whether a given pair of nodes, a source s and a destination t, are connected by a path or separated by a cut. Assuming that during each determining process we are associated with an underlying graph, the existence of each edge can be unraveled through edge testing at a cost of c(e). Our goal is to find an optimal strategy incurring the minimum expected testing cost with the expectation taken over all possible underlying graphs that form a product distribution. Formulating it into a combinatorial optimization problem, we first characterize the computational complexity of optimally determining source-destination connectivity in uncertain graphs. Specifically, through proving the NP-hardness of two closely related problems, we show that, contrary to its counterpart in deterministic graphs, this problem cannot be solved in polynomial time unless P=NP. Driven by the necessity of designing an exact algorithm, we then apply the Markov Decision Process framework to give a dynamic programming algorithm that derives the optimal strategies. As the exact algorithm may have prohibitive time complexity in practical situations, we further propose two more efficient approximation schemes compromising the optimality. The first one is a simple greedy approach with linear approximation ratio. Interestingly, we show that naive as it is, it has comparable performance than some other seemingly more sophisticated algorithms. Second, by harnessing the sub-modularity of the problem, we further design a more elaborate algorithm with better approximation ratio. The effectiveness of the proposed algorithms are justified through extensive simulations on three real network datasets, from which we demonstrate that the proposed algorithms yield strategies with smaller expected cost than conventional heuristics.

This paper studies the problem of optimizing multicast energy consumption in delay-constrained mobile wireless networks, where information from the source needs to be delivered to all the k destinations within an imposed delay constraint. Most existing works simply focus on deriving transmission schemes with the minimum transmitting energy, overlooking the energy consumption at the receiver side. Therefore, in this paper, we propose ConMap, a novel and general framework for efficient transmission scheme design that jointly optimizes both the transmitting and receiving energy. In doing so, we formulate our problem of designing minimum energy transmission scheme, called DeMEM, as a combinatorial optimization one, and prove that the approximation ratio of any polynomial time algorithm for DeMEM cannot be better than ¼ ln k. Aiming to provide more efficient approximation schemes, the proposed ConMap first converts DeMEM into an equivalent directed Steiner tree problem through creating auxiliary graph gadgets to capture energy consumption, then maps the computed tree back into a transmission scheme. The advantages of ConMap are threefolded: i) Generality-- ConMap exhibits strong applicability to a wide range of energy models; ii) Flexibility-- Any algorithm designed for the problem of directed Steiner tree can be embedded into our ConMap framework to achieve different performance guarantees and complexities; iii) Efficiency-- ConMap preserves the approximation ratio of the embedded Steiner tree algorithm, to which only slight overhead will be incurred. The three features are then empirically validated, with ConMap also yielding near-optimal transmission schemes compared to a brute-force exact algorithm. To our best knowledge, this is the first work that jointly considers both the transmitting and receiving energy in the design of multicast transmission schemes in mobile wireless networks.

In many realistic networks, entities of different types usually form an evolving network with hybrid interactions. However, how to mathematically model such networks remains unexplored. Motivated by this, we develop a novel evolving model, which, as validated by our empirical results, can well capture some basic features such as power-law distribution, densification and shrinking diameter. Particularly, in our proposed model, named Evolving K-Graph, the hybrid interactions among entities are classified into inter-type and intra-type connections that are respectively characterized by two joint graphs evolving over time. By empirical validation, we disclose two new network properties: a positive correlation of any two layers of the network, and an earlier occurrence of network connectivity resulted by our model.

Core percolation is crucial in network controllability and robustness. Prior works are mainly based on single, non-interacting network where core nodes are obtained by a classic Greedy Leaf Removal (GLR) procedure that takes of leaf nodes along with their neighbors iteratively. We take a first look into core percolation in coupled networks with two fully-interdependent networks. To obtain core nodes in both networks, we propose a new algorithm, called Alternating GLR procedure, that recursively switches between networks in carrying out GLR for node removal. We prove that the proposed algorithm can guarantee the uniqueness in the sense that the final remaining nodes and edges in either of the coupled networks remain the same, and then present analytical solutions for the fraction of core nodes that will be ultimately left when the algorithm terminates. Our simulation demonstrates that the presence of core exhibits a jump at the critical point as a first order transition in coupled networks.

In this paper, we propose a novel game-based incentive mechanism for multi-resource sharing, where users are motivated to share their idle resources in view of conditional voluntary. Through social networking service platforms, such a crowdsourcing service fully explores the significant influence and computing potential of mobile social networks. Specifically, a combination of task allocation process, profit transfer process, and reputation updating process are involved in this sharing incentive mechanism, satisfying truthfulness, individual rationality, and robustness. To maintain the social fairness-efficiency tradeoff, we further develop a resource sharing algorithm on the basis of dominant resource fairness, revealing that the sacrifice of fairness properties is necessary for the improvement of efficiency. Real-world traces from Facebook are numerically studied, validating social fairness and efficiency of our social crowdsourcing mechanism.

The widespread of smart phones has brought new social-aware features to wireless networks. Users prefer to forward traffic to their social contacts in social-aware networks, which is highly different from the traditional uniform traffic pattern. To this end, we analyze a social-aware wireless network, which is modeled by the social contacts between nodes, and explore its impact on network throughput capacity. We present that it can refine social contacts, thus improving the network capacity. Moreover, directional antennas are applied to further enhance the capacity performance, which can reduce the interference brought by other simultaneous communications. We derive the throughput capacity for social-aware networks with single-beam and multi-beam directional antenna, respectively. For single-beam directional antenna, we prove that when wireless networks are dominated by traffics of short-distance social contact, the throughput capacity can be promoted from order of (θ(1/θ2n log n)1/2) to Θ(1/θ2log n). In addition, when the beamwidth θ is at order of Ω(1/(log n)1/2), the throughput capacity is a constant. Thus, the wireless network is scalable. For multi-beam antennas, we prove that when sidelobe gain Gsis at order of o(Gm), where Gmis main lobe gain, compared with the single-beam case, the network capacity can achieve the order of θ(1/θ2log n).

Multicast tree is a key structure for data dissemination from one source to multiple receivers in wireless networks. Minimum length multica modeled as the Steiner tree problem, and is proven to be NP-hard. In this paper, we explore how to efficiently generate minimum length multi wireless sensor networks (WSNs), where only limited knowledge of network topology is available at each node. We design and analyze a simple algorithm, which we call toward source tree (TST), to build multicast trees in WSNs. We show three metrics of TST algorithm, i.e., running and energy efficiency. We prove that its running time is O(√(n log n)), the best among all existing solutions to our best knowledge. We prove that TST tree length is in the same order as Steiner tree, which give a theoretical upper bound and use simulations to show the ratio be only 1.114 when nodes are uniformly distributed. We evaluate energy efficiency in terms of message complexity and the number of forwarding prove that they are both order-optimal. We give an efficient way to construct multicast tree in support of transmission of voluminous data.

With the soaring development of large scale online social networks, online information sharing is becoming ubiquitous everyday. Various information is propagating through online social networks including both the positive and negative. In this paper, we focus on the negative information problems such as the online rumors. Rumor blocking is a serious problem in large-scale social networks. Malicious rumors could cause chaos in society and hence need to be blocked as soon as possible after being detected. In this paper, we propose a model of dynamic rumor influence minimization with user experience (DRIMUX). Our goal is to minimize the influence of the rumor (i.e., the number of users that have accepted and sent the rumor) by blocking a certain subset of nodes. A dynamic Ising propagation model considering both the global popularity and individual attraction of the rumor is presented based on a realistic scenario. In addition, different from existing problems of influence minimization, we take into account the constraint of user experience utility. Specifically, each node is assigned a tolerance time threshold. If the blocking time of each user exceeds that threshold, the utility of the network will decrease. Under this constraint, we then formulate the problem as a network inference problem with survival theory, and propose solutions based on maximum likelihood principle. Experiments are implemented based on large-scale real world networks and validate the effectiveness of our method.

Determination of source-destination connectivity in networks has long been a fundamental problem, where most existing works are based on deterministic graphs that overlook the inherent uncertainty in network links. To overcome such limitation, this paper models the network as an uncertain graph, where each edge e exists independently with some probability p(e). The problem examined is that of determining whether a given pair of nodes, a source s and a destination t, are connected by a path or separated by a cut. Assuming that during each determining process we are associated with an underlying graph, the existence of each edge can be unraveled through edge testing at a cost of c(e). Our goal is to find an optimal strategy incurring the minimum expected testing cost with the expectation taken over all possible underlying graphs that form a product distribution. Formulating it into a combinatorial optimization problem, we first characterize the computational complexity of optimally determining source-destination connectivity in uncertain graphs. Specifically, through proving the NP-hardness of two closely related problems, we show that, contrary to its counterpart in deterministic graphs, this problem cannot be solved in polynomial time unless P = NP. Driven by the necessity of designing an exact algorithm, we then apply the Markov decision process framework to give a dynamic programming algorithm that derives the optimal strategies. As the exact algorithm may have prohibitive time complexity in practical situations, we further propose two more efficient approximation schemes compromising the optimality. The first one is a simple greedy approach with linear approximation ratio. Interestingly, we show that naive as it is, and it enjoys significantly better performance guarantee than some other seemingly more sophisticated algorithms. Second, by harnessing the submodularity of the problem, we further design a more elaborate algorithm with better approximation ratio. The effectiveness of the proposed algorithms is justified through extensive simulations on three real network data sets, from which we demonstrate that the proposed algorithms yield strategies with smaller expected cost than conventional heuristics.

This paper investigates the problem of optimally determining source-destination connectivity in random networks. Viewing the network as a random graph, we start by investigating the Erdos-Renyi (ER) graph, as well as a structured graph where, interesting, the problem appears to be open. The problem examined is that of determining whether a given pair of nodes, a source S, and a destination D are connected by a path. Assuming that at each step one edge can be tested to see if it exists or not, we determine an optimal policy that minimizes the total expected number of steps. The optimal policy has several interesting features. In order to establish the connectivity of S and D, a policy needs to check all edges on some path to see if they all exist, but to establish the disconnectivity it has to check all edges on some cut to see if none of them exists. The optimal policy has the following form. At each step, it examines the condensation multigraph formed by contracting each known connected component to a single node, and then checks an edge that is simultaneously on a shortest S-D path as well as in a minimum S-D cut. Among such edges, it chooses that which lead to the most opportunities for connection. Interestingly, for an ER graph with n nodes, where there is an edge between two nodes with probability p, the optimal strategy does not depend on p or n, even though the entire graph itself undergoes a sharp transition from disconnectivity to connectivity around p = ln n/n. The policy is efficiently implementable, requiring no more than 30log2n operations to determine which edge to test next. The result also extends to some more general graphs and, meanwhile, provide useful insights into the connectivity determination in random networks.

Since it was found that real mobility processes exhibit significant degree of correlation (correlated mobility) and nodes are often heterogeneously distributed in clustered networks (cluster scalability), there has been a great interest in studying their impact on network performance, such as throughput and delay. However, limited works have been done to investigate their impact jointly, which may due to the challenges in capturing both features under a unified network model. In this paper, we focus on their impact on asymptotic connectivity and propose correlated mobile k-hop clustered network model. Two connectivity metrics are considered. One is network connectivity with probability (w.p.). The other is connectivity almost surely (a.s.), which requires a stronger condition than connectivity with probability. With mobility correlation and cluster scalability vary, we show that there are three distinct states for network connectivity, i.e., cluster-sparse, cluster-dense state, and cluster-inferior dense state, respectively. We first prove the exact value of the critical transmission range for each state, respectively, and then further generalize the three states into a unified one, which we call it cluster mixed state. The critical transmission range for connectivity almost surely is √2 times the range for connectivity with probability. Our main contribution lies in how to group correlated nodes into independent ones in various settings, and reveals the interrelated relationship between correlated mobility and cluster scalability through state transitions.

Social characteristics have been observed to significantly affect the communications in wireless social networks, especially that within a group following the multicast manner. To model the multicast group in wireless social networks, we should incorporate two important social characteristics, i.e., social relationship and group size. In most existing works, the modeling of social relationship only considers geographic factor. However, such models fail to well characterize wireless social networks, since unlike that in traditional wireless networks, geographic distance is no longer the major factor that affects people's communications and some non-geographic factors, such as user popularity, become more and more important. Moreover, group size is always assumed to be known a priori in previous works, which cannot fully meet the realistic condition. Therefore, in this paper, we model the multicast group from a combination of geographic and non-geographic (GN) perspectives. Specifically, we propose the GN Model to characterize social relationship and the independently-selected model to characterize group size. In addition to the geographic distance considered in the modeling of social relationship, we also introduce user popularity which reflects the influence of each user on others. Then, we assume that the source transmits the data packet to all his friends following the multicast manner. Based on the proposed model, we calculate transmission distance and network traffic load, and then discuss how they are influenced by both geographic and GN factors. Moreover, our proposed models are verified through experimental measurements based on real datasets.

Rumor blocking is a serious problem in large-scale social networks. Malicious rumors could cause chaos in society and hence need to be blocked as soon as possible after being detected. In this paper, we propose a model of dynamic rumor influence minimization with user experience (DRIMUX). Our goal is to minimize the influence of the rumor (i.e., the number of users that have accepted and sent the rumor) by blocking a certain subset of nodes. A dynamic Ising propagation model considering both the global popularity and individual attraction of the rumor is presented based on realistic scenario. In addition, different from existing problems of influence minimization, we take into account the constraint of user experience utility. Specifically, each node is assigned a tolerance time threshold. If the blocking time of each user exceeds that threshold, the utility of the network will decrease. Under this constraint, we then formulate the problem as a network inference problem with survival theory, and propose solutions based on maximum likelihood principle. Experiments are implemented based on large-scale real world networks and validate the effectiveness of our method.

In social networks, most information is stored, displayed and propagated in the form of text which is characterized by latent topics. With the discovery of latent topics, we can make more accurate prediction, inference and therefore, better applications, in social networks. Considering the dynamics and noise in social networks, we analyze data evolution from different perspectives including both common and discriminative topics. We adopt a basic model to factorize data matrix into components with an order representing latent topic and apply non-negative matrix factorization to two datasets as contrast to each other simultaneously. Time is taken into consideration as one order of the data matrix. Our basic model converts the decomposition problem into an optimization problem solved by block coordinate gradient descent, based on which the penalized model separates common part and discriminative part by adding penalty items. Next, a Bayesian generative model is established to avoid parameter tuning and overfitting, with the model parameters estimated via Gibbs sampling. Finally, we apply the models to both synthesized data and contrastive corpora of papers accepted by different conferences, as well as provide analysis of topic variation along with time.

In this paper, we investigate the impact of information-theoretic secrecy constraint on the capacity and delay of mobile ad hoc networks (MANETs) with mobile legitimate nodes and static eavesdroppers whose location and channel state information (CSI) are both unknown. We assume n legitimate nodes move according to the fast i.i.d. mobility pattern and each desires to communicate with one randomly selected destination node. There are also nνstatic eavesdroppers located uniformly in the network and we assume the number of eavesdroppers is much larger than that of legitimate nodes, i.e., ν > 1. We propose a novel simple secure communication model, i.e., the secure protocol model, and prove its equivalence to the widely accepted secure physical model under a few technical assumptions. Based on the proposed model, a framework of analyzing the secrecy capacity and delay in MANETs is established. Given a delay constraint D, we find that the optimal secrecy throughput capacity is ~Θ(W((D/n))(2/3)), where W is the data rate of each link. We observe that: 1) the capacity-delay tradeoff is independent of the number of eavesdroppers, which indicates that adding more eavesdroppers will not degenerate the performance of the legitimate network as long as ν > 1; 2) the capacity-delay tradeoff of our paper outperforms the previous result Θ((1/nψe)) in , where ψe=nν-1=ω(1) is the density of the eavesdroppers. Throughout this paper, for functions f(n) and g(n), we denote f(n)=o(g(n)) if limn→∞(f(n)/g(n))=0; f(n)=ω(g(n)) if g(n)=o(f(n)); f(n)=O(g(n)) if there is a positive constant c such that f(n) ≤ cg(n) for sufficiently large n; f(n)=Ω(g(n)) if g(n)=O(f(n)); f(n)=Θ(g(n)) if both f(n)=O(g(n)) and f(n)=Ω(g(n)) hold. Besides, the order notation ~Θ omits the polylogarithmic factors for better readability.

This paper studies the throughput capacity of wireless networks with social characteristics. We propose a simple model to reflect both the social relations between nodes and power-law node degree distribution, and then examine their impact on capacity. We show the fact that two features above lead to traffic locality and improve capacity. Moreover, multicasting may be employed to further enhance performance when information is desired to be published from the source to all its contacts, of which the number follows power-law distribution. In addition, we propose the corresponding capacity-achieving communication schemes, which optimally exploit the underlying structure. Our study is an attempt to understand how social relations may impact on network capacity from a theoretical perspective, and provides fundamental insight on the design and analysis of real wireless networks.

Delayed traffic offloading is a promising paradigm to alleviate the cellular network congestion caused by explosive traffic demands. As we all know, in mobile networks, the delay profile for traffic is remarkable due to users’ mobility. How to exploit user delay tolerance to improve the profit of operator as well as mobile users becomes a big challenge. In this paper, we model this delayed offloading process as a monopoly market based on contract theory, where operator acts as the monopolist setting up the optimal contract by statistical information on user satisfaction. We propose an incentive mechanism to motivate users to leverage their delay and price sensitivity in exchange for service cost. To capture the heterogeneity of user satisfaction, we classify users into different types. Each user chooses a proper quality–price contract item according to its type. More specifically, we investigate this delayed offloading scheme under strongly incomplete information scenario, where user type is private information. We derive an optimal contract, which maximizes operator’s profit for both the continuous-user-type model and the discrete-user-type model. Numerical results validate the effectiveness of our incentive mechanism for delayed traffic offloading in cellular networks.

Vehicular Ad Hoc Network (VANET) has been a hot topic in the past few years. Compared with vehicular networks where vehicles are densely distributed, sparse VANET have more realistic significance. The first challenge of a sparse VANET system is that the network suffers from frequent disconnections. The second challenge is to adapt the transmission route to the dynamic mobility pattern of the vehicles. Also, some infrastructural requirements are hard to meet when deploying a VANET widely. Facing these challenges, we devise an infrastructure-less unmanned aerial vehicle (UAV) assisted VANET system called Vehicle-Drone hybrid vehicular ad hoc Network (VDNet), which utilizes UAVs, particularly quadrotor drones, to boost vehicle-to-vehicle data message transmission under instructions conducted by our distributed vehicle location prediction algorithm. VDNet takes the geographic information into consideration. Vehicles in VDNet observe the location information of other vehicles to construct a transmission route and predict the location of a destination vehicle. Some vehicles in VDNet equips an on-board UAV, which can deliver data message directly to destination, relay messages in a multi-hop route, and collect location information while flying above the traffic. The performance evaluation shows that VDNet achieves high efficiency and low end-to-end delay with controlled communication overhead. Copyright © 2016 John Wiley & Sons, Ltd.

This paper investigates random walk mobility models with location heterogeneity, where different locations may have different neighboring regions. We consider$n$locations in a one-dimension network and investigate two cases, i.e.,full-range locationswhere nodes situated have the capability to shuffle throughout the network andlong-range locationswhere nodes are allowed to move to positions nearby within a certain range. In the former situation, with the exact expressions derived, we find location heterogeneity has a critical impact on the first hitting time of random walk, varying from$\Theta (n)$to$\Theta \left(n^3\right)$according to different extent of heterogeneity. The result covers, as two special cases, both the classic independent and identically distributed (i.i.d) mobility and traditional random walk when varying the number of full-range locations. In the latter one, our asymptotic results on both the first crossing time and cover time suggest that they are inversely proportional to the range of neighboring region$r$($\propto r^{-2}$and$\propto r^{-1}$, respectively). Furthermore, with multiple concurrent random walks introduced, the first hitting time can be drastically decreased and the effect is strengthened if combined with location heterogeneity. In addition, our investigation into the stationary distribution of nodes indicates that the uniformity no longer holds due to different transition probabilities, as a result of location heterogeneity. We also conduct extensive simulation results to verify our observations and enhance the understanding on the impact of network parameters. Based on the insights obtained, we move forward to investigate the impact of location heterogeneity in two-dimension networks.

This paper investigates the problem of optimally determining source-destination connectivity in random graphs. We consider the classic Erdos-Renyi (ER) random graph with $n$ nodes, where an edge independently exists between any two nodes with probability p. The problem examined is that of determining whether a given pair of nodes, a source S and a destination D, are connected by a path. Assuming that at each step one edge can be tested to see if it exists or not, we determine an optimal policy that minimizes the total expected number of steps. The optimal policy has several interesting features. In order to establish connectivity of S and D, a policy needs to check all edges on some path to see if they all exist, but to establish disconnectivity it has to check all edges on some cut to see if none of them exists. The optimal policy has the following form. At each step it examines the condensation multigraph formed by contracting each known connected component to a single node, and then checks an edge that is simultaneously on a shortest S-D path as well as in a minimum S-D cut. Among such edges, it chooses that which leads to the most opportunities for connection. Interestingly, the optimal strategy does not depend on p or n, even though the entire graph itself undergoes a sharp transition from disconnectivity to connectivity around p = ln n/n. The policy is efficiently implementable, requiring no more than 30 log2n operations to determine which edge to test next. The result also extends to some more general graphs.

In this paper, we study the throughput and delay in wireless cognitive social networks. Specifically, we consider a common scenario for cognitive radio networks (CRNs) where the primary and secondary networks operate at the same time and space and share the spectrum. On this basis, we integrate a social relationship into the CRN where each source node selects its destination upon a rank-based model, which captures the social characteristic well. By applying a cellular time-division multiple-access scheduling scheme, we first characterize the distinct traffic pattern caused by the social relationships between nodes. Then, we derive the achievable throughput and delay for both primary and secondary networks under the new network setting. In addition, we also study the cognitive social networks with infrastructure where I = o1(n) base stations are regularly deployed within the primary network. Given a probabilistic routing strategy, throughput of the proposed network is recalculated. Particularly, due to the social relationships between nodes, we reveal that a larger I is required if we expect a significant capacity gain within the primary network compared with previous works.

Since wireless channel is vulnerable to eavesdroppers, the secrecy during message delivery is a major concern in many applications such as commercial, governmental, and military networks. This paper investigates information-theoretic secrecy in large-scale networks and studies how capacity is affected by the secrecy constraint where the locations and channel state information (CSI) of eavesdroppers are both unknown. We consider two scenarios: 1) noncolluding case where eavesdroppers can only decode messages individually; and 2) colluding case where eavesdroppers can collude to decode a message. For the noncolluding case, we show that the network secrecy capacity is not affected in order-sense by the presence of eavesdroppers. For the colluding case, the per-node secrecy capacity of Θ([1/(√n)]) can be achieved when the eavesdropper density ψe(n) is O(n-β), for any constant β > 0 and decreases monotonously as the density of eavesdroppers increases. The upper bounds on network secrecy capacity are derived for both cases and shown to be achievable by our scheme when ψe(n)=O(n-β) or ψe(n)=Ω(log[(α-2)/(α)]n), where α is the path-loss gain. We show that there is a clear tradeoff between the security constraints and the achievable capacity. Furthermore, we also investigate the impact of secrecy constraint on the capacity of dense network, the impact of active attacks and other traffic patterns, as well as mobility models in the context.

This paper characterizes an evolving network with growing number of nodes, which are associated with each other through social relations but employ transmission via wireless communications. The network exhibits social relations between nodes by attaching a new arriving node to a sample node already existing as well as some nodes the sample directly links to. We study capacity in this evolving network in terms of both geographic distribution of nodes and traffic patterns. Our results show that in heterogeneous geographic distribution where nodes having strong social relations tend to locate more closer, the corresponding capacity is significantly impacted by both social relations and network evolution. In particular, with appropriate control on the initial number of nodes as well as links between them, it is even possible to achieve almost constant per-node capacity except for a poly-logarithmic factor. For homogeneous geographic topology where nodes' positions exhibit uniform distribution, social relations among nodes is useless for improving capacity, which is mainly affected by network evolution and therefore degrades sharply with time. To our best knowledge, this is the first work studying capacity from the perspective of social evolving network.

This paper investigates random walk mobility models with location heterogeneity, where different locations may have different neighboring regions.With the assumption of totally n locations, we consider two cases, i.e., full-range locations where nodes situated have the capability to shuffle throughout the network and long-range locations where nodes are allowed for moving to positions nearby within a certain range. In the former situation, with the exact expressions derived, we find location heterogeneity has a critical impact on the first hitting time of random walk, varying from Θ(n) to Θ(n3) according to different extent of heterogeneity. The result covers, as two special cases, both the classic independent and identically distributed (i.i.d) mobility and traditional random walk as we vary the number of full-range locations. In the latter one, our asymptotic results on both the first crossing time and cover time suggest that they are inversely proportional to the range of neighboring region r (∝ r−2and ∝ r−1, respectively). Furthermore, extensive simulation is conducted to verify our observations and enhance the understanding on the effect of network parameters.

This paper addresses the issue of multicast scaling performance in multichannel multiradio (MC-MR) networks. Under the assumption of both limited bandwidth and node tunability, a total fixed bandwidth $(W)$ is equally split into $(c)$ channels with $(0<m\le c)$ interfaces equipped on each node for channel switching. The network contains totally $(n)$ nodes, each serving as a source with $(k)$ randomly and uniformly selected destinations. We try to give a comprehensive picture of multicast scalings by investigating both the static and mobile networks, with the metrics being capacity and delay. Previous literature has indicated that unicast capacity is solely determined by the ratio of channels to interfaces $(c/m)$ in MC-MR networks. However, in multicast our problem is made more complicated by the interplay among $(k)$, $(c/m)$ and node mobility (if considered in mobile scenario). We characterize their impact on multicast scaling and obtain three remarkable findings from our results. First, we find capacity loss exists in static networks even if the ratio $(c/m=O(\log n))$ (We use the following notation throughout our paper: $(f(n)=O(g(n))\Leftrightarrow \limsup _{n\rightarrow \infty }{f(n)\over g(n)} <\infty)$, $(f(n)=\Omega (g(n))\Leftrightarrow \liminf _{n\rightarrow \infty }{f(n)\over g(n)} <\infty)$, $(f(n)=\Theta (g(n))\Leftrightarrow f(n)=O(g(n)))$ and $(g(n)=O(f(n)))$, $(f(n)=\widetilde{\Theta }(\cdot ))$: The corresponding order $(\Theta (\cdot ))$ which contains a logarithmic order.) when $(k)$ is close to $(\Theta (n))$. This differs from unicast that is free of capacity loss as long as $(c/m=O(\log n))$. Second, mobility is manifested to improve multicast capacity in MC-MR networks, where two major capacity bottlenecks, i.e., connectivity and interference constraints, in static networks can be effectively broken. Third, a largely reduced delay is possible by simply seeking for multichannel reuse in 2-hop algorithm without redundancy. This even outperforms the delay scaling in single channel framework , where a delay smaller than $(\Theta (\sqrt{n\log k}))$ is not achievable even with more than $(\Theta (\sqrt{n\log k}))$ relay nodes involved in 2-hop mode. As a high-level summary of our results, our work discloses analytically where the performance improvement and degradation exhibit in MC-MR networks, meanwhile unifying the previous bounds on unicast (setting $(k=1)$) in .

In this paper, we consider a general scenario where tphe wireless network is modeled as a rectangle with side lengths √n and n1/2−β, where 0 ≤ β ≤ 1/2 is a variance independent of n. n source-destination pairs are randomly located in the network, with their communication subject to the short-distance SNR, the long-distance SNR and the path loss. Based on these conditions, we identify the scaling laws of capacity for the network. The upper bound of the capacity is derived for the network, with the adoption of Multiple Input Multiple Output (MIMO) technology. Furthermore, we propose three different schemes, i.e., multihop, MIMO and hybrid schemes to achieve the upper bound. The capacity performance exhibits distinctive intriguing results as the side length of the network varies. Moreover, our results capture the impact of network shape on capacity and can unify the previous capacity results obtained in square networks.

The fc-connectivity of cognitive radio networks is discussed in this paper. By combining asymptotic k-connectivity and percolation, we define that the cognitive radio networks are k-connected if there exists an infinite k-connected component in the secondary network. Utilizing continuum percolation theory, we prove that the secondary network is k-disconnected if secondary users' density λ2, where l → ∞ is the side length of a square-shaped network, r is the transmission range of the secondary network, and θ = Ω(1). And the network is k-connected when λs≥ log l + (k − 1 − + ξ) log, log l/πr2, where ξ = Ω(1). Finally, we provide the necessary condition and sufficient condition of k-connectivity on primary user density λp.

In this paper, we explore methods to generate optimal network topologies for wireless sensor networks (WSNs) with and without obstacles. Specifically, we investigate a dense network with n sensor nodes and m = nb(0 < b < 1) helping nodes, and evaluate the impact of topology on its throughput capacity. For networks without obstacles, we find that uniformly distributed sensor nodes and regularly distributed helping nodes have some advantages in improving the throughput capacity. We also explore properties of networks composed of some isomorphic sub-networks. For networks with obstacles, we assume there are M = Θ(nv) (0 < v ≤ 1) arbitrarily or randomly distributed obstacles, which block cells they are located in, i.e., sensor nodes cannot be placed in these cells and nodes' communication cannot cross them directly. We find that the overall throughput capacity is bounded by the transmission burden in areas around these blocked cells and introduce a novel algorithm of complexity O(M) to generate optimal sensor nodes' topologies for any given obstacles' distributions.

Since wireless channel is vulnerable to eavesdroppers, the secrecy during message delivery is a major concern in many applications such as commercial, governmental and military networks. This paper investigates information-theoretic secrecy in large-scale networks and studies how capacity is affected by the secrecy constraint where the locations and channel state information (CSI) of eavesdroppers are both unknown. We consider two scenarios: 1) non-colluding case where eavesdroppers can only decode messages individually; and 2) colluding case where eavesdroppers can collude to decode a message. For the non-colluding case, we show that the network secrecy capacity is not affected in order-sense by the presence of eavesdroppers. For the colluding case, the per-node secrecy capacity of Θ(1/√n) can be achieved when the eavesdropper density ψe(n) is O(n-β), for any constant β >; 0 and decreases monotonously as the density of eavesdroppers increases. The upper bounds on network secrecy capacity are derived for both cases and shown to be achievable by our scheme when ψe(n) = O(n-β) or ψe(n) = Ω(log α-2/α n), where α is the path loss gain. We show that there is a clear tradeoff between the security constraints and the achievable capacity.

A cognitive network refers to the one where two overlaid structures, called primary and secondary networks coexist. The primary network consists of primary nodes who are licensed spectrum users while the secondary network comprises unauthorized users that have to access the licensed spectrum opportunistically. In this paper, we study the percolation degree of the secondary network to achieve k-percolation in large scale cognitive radio networks. The percolation degree is defined as the number of nearest neighbors for each secondary user when there are at least k vertex-disjoint paths existing between any two secondary relays in the percolated cluster. The percolated cluster is formed when there are an infinite number of mutually connected secondary users spanning the whole network. Each user in the cluster is possibly connected to several neighbors, inducing more communication links between any two of them. Since nodes located near the boundary have fewer neighbors, the boundary effect becomes a bottleneck in determining the percolation degree. For cognitive networks, when the primary node density becomes considerably large, the boundary effect spreads inside the network. The transmission area of most secondary users who are located near the primary nodes decreases due to the restriction of the primary network. Therefore, to ensure k-connectivity in the percolated cluster, each secondary user must be connected to more neighbors, and the percolation degree of the secondary network yields a function of the primary node density. We specify the relationship into three regimes regarding the topology variation of the cognitive network. A closed-form expression of the percolation degree under different primary node densities is presented. The expression characterizes the connectivity strength in the secondary percolated cluster, therefore providing analytical insight on fault tolerance improvement in cognitive networks.

In this paper, we define an ad hoc network where multiple sources transmit packets to one destination as Converge-Cast network. We will study the capacity delay tradeoffs assuming that n wireless nodes are deployed in a unit square. For each session (the session is a dataflow from k different source nodes to 1 destination node), k nodes are randomly selected as active sources and each transmits one packet to a particular destination node, which is also randomly selected. We first consider the stationary case, where capacity is mainly discussed and delay is entirely dependent on the average number of hops. We find that the per-node capacity is Θ (1/√(n log n)) (given nonnegative functions f(n) and g(n): f(n) = O(g(n)) means there exist positive constants c and m such that f(n) ≤ cg(n) for all n ≥ m; f(n)= Ω (g(n)) means there exist positive constants c and m such that f(n) ≥ cg(n) for all n ≥ m; f(n) = Θ (g(n)) means that both f(n) = Ω (g(n)) and f(n) = O(g(n)) hold), which is the same as that of unicast, presented in (Gupta and Kumar, 2000). Then, node mobility is introduced to increase network capacity, for which our study is performed in two steps. The first step is to establish the delay in single-session transmission. We find that the delay is Θ (n log k) under 1-hop strategy, and Θ (n log k/m) under 2-hop redundant strategy, where m denotes the number of replicas for each packet. The second step is to find delay and capacity in multisession transmission. We reveal that the per-node capacity and delay for 2-hop nonredundancy strategy are Θ (1) and Θ (n log k), respectively. The optimal delay is Θ (√(n log k)+k) with redundancy, corresponding to a capacity of Θ (√((1/n log k) + (k/n log k)). Therefore, we obtain that the capacity delay tradeoff satisfies delay/rate ≥ Θ (n log k) for both strategies.

It has been shown in a previous version of this paper that hierarchical cooperation achieves a linear throughput scaling for unicast traffic, which is due to the advantage of long-range concurrent transmissions and the technique of distributed multiple-input-multiple-output (MIMO). In this paper, we investigate the scaling law for multicast traffic with hierarchical cooperation, where each of thennodes communicates withkrandomly chosen destination nodes. Specifically, we propose a new class of scheduling policies for multicast traffic. By utilizing the hierarchical cooperative MIMO transmission, our new policies can obtain an aggregate throughput of Ω(( [(n)/(k)])1-ε) for any ε >; 0. This achieves a gain of nearly √{[(n)/(k)]} compared to the noncooperative scheme in Li 's work (Proc. ACM MobiCom, 2007, pp. 266-277). Among all four cooperative strategies proposed in our paper, one is superior in terms of the three performance metrics: throughput, delay, and energy consumption. Two factors contribute to the optimal performance: multihop MIMO transmission and converge-based scheduling. Compared to the single-hop MIMO transmission strategy, the multihop strategy achieves a throughput gain of ( [(n)/(k)])[(h-1)/(h(2h-1))] and meanwhile reduces the energy consumption byk[( α-2)/ 2]times approximately, whereh>; 1 is the number of the hierarchical layers, and α >; 2 is the path-loss exponent. Moreover, to schedule the traffic with the converge multicast instead of the pure multicast strategy, we can dramatically reduce the delay by a factor of about ( [(n)/(k)])[(h)/ 2]. Our optimal cooperative strategy achieves an approximate delay-throughput tradeoffD(n,k)/T(n,k)=Θ(k) whenh→ ∞. This tradeoff ratio is identical to that of noncooperative scheme, while the throughput is greatly improved.

This paper investigates throughput and delay based on a traffic pattern, called convergecast, where each of the n nodes in the network acts as a destination with k randomly chosen sources corresponding to it. Adopting Multiple-Input-Multiple-Output (MIMO) technology, we devise two many-to-one cooperative schemes under convergecast for both static and mobile ad hoc networks (MANETs), respectively. We call them Convergimo Schemes. In static networks, our Convergimo scheme highly utilizes hierarchical cooperation MIMO transmission. This feature overcomes the bottleneck which hinders convergecast traffic from yielding ideal performance in traditional ad hoc network, by turning the originally interfering signals into interference-resistant ones. It helps to achieve an aggregate throughput up to Ω(n1-ϵ) for any ϵ >;0. In the mobile ad hoc case, our Convergimo scheme characterizes on joint transmission from multiple nodes to multiple receivers. With optimal network division where the number of nodes per cell is constantly bounded, the achievable per-node throughput can reach Θ(1) with the corresponding delay reduced to Θ(k). The gain comes from the strong and intelligent cooperation between nodes in our scheme, along with the maximum number of concurrent active cells and the shortest waiting time before transmission for each node within a cell. This increases the chances for each destination to receive the data it needs with minimum overhead on extra transmission. Moreover, our converge-based analysis well unifies and generalizes previous work since the results derived from convergecast in our schemes can also cover other traffic patterns. Last but not the least, our schemes are of interest not only from a theoretical perspective but also provide useful theoretical guidelines to future design of MIMO schemes in wireless networks.

Abstract Most of analysis so far for IEEE 802.11 wireless local area networks (WLANs) focuses on saturated condition. However, it is of practical value to take into account the unsaturation case. In this paper, we modified Bianchi's Markov back‐off model to make it applicable to unsaturated condition and the analytic results are provided by employing the renewal‐reward theorem. Under our proposed model, we study the fixed‐point solution of the system and provide a condition to guarantee both the uniqueness and balance of the fixed point. From the fixed point, we find that under unsaturated condition, network parameters should be adjusted according to the traffic load. Then, we study the system throughput. In the case where there are a large number of nodes, we provide closed‐form formulas for the collision probability, the aggregate attempt rate, and the throughput. We find that in such a scenario, the system yields similar performance as that under saturated situation. Moreover, we compare all the results with those under saturated condition and find the latter is a special case of our results. Hence, all of our analysis based on unsaturated condition well covers saturated condition. Our analytical results are validated through ns2 simulations. Copyright © 2010 John Wiley & Sons, Ltd.

In this paper, we study the multicast capacity-delay tradeoff of a wireless network consisting of mobile wireless nodes and base stations. m = nbbase stations are regularly placed in a square region and n is the number of mobile nodes in the network. We assume that mobile nodes move according to an independent and identical distributed (i.i.d.) pattern and each desires to send packets to k = nddistinctive destinations. Under this basic network model, we study capacity, delay tradeoff in two transmission protocols: 2-hop relay algorithm with and without redundancy. We derive that the upper bound of per-node capacity of 2-hop relay algorithm without redundancy is O(n-min{1, 1 - b + d})and its corresponding delay is Θ(nmin{1, 1 - b + d}/2). The lower bound of delay of this protocol is Θ(n1-b), with a smaller capacity O(nb-2). For 2-hop relay algorithm with redundancy, the largest capacity and its corresponding delay are O(n-min{1, 1 - b + d}) and Θ(nmin{1, 1 - b + d}/2). The smallest delay and its corresponding capacity are Θ(n1 - b/2) and O(nb - 3/2). When d >; 1/2 or b >; min{1+d/3, 1 - d}, adding base stations will improve the tradeoff mentioned in [7].

In this paper, we study the capacity and delay scaling laws for cognitive radio networks (CRN). The primary network consists of n static, randomly and evenly distributed primary users (PUs), which require high throughput with low delay. The secondary network consists of m = O(n1+δ) randomly and evenly distributed cognitive secondary users (SUs) with δ >; 0, which move in different area according to the hierarchical i.i.d. mobility model. The secondary network is carefully designed to support the primary network, so that PUs may achieve near-optimal performance in both capacity and delay aspects. Then by utilizing hierarchical cooperation among SUs with different mobility, a new hierarchical relay algorithm is proposed to improve the delay performance extensively. Under optimal condition, this algorithm may provide Ω(n-δ') per-node throughput and O(nδ") average delay for PU with δ', δ" >; 0, and significantly improve the performance of SU at the same time.

This paper investigates throughput and delay based on a newly predominant traffic pattern, called converge-cast, where each of the n nodes in the network act as a destination with k randomly chosen sources corresponding to it. Adopting Multiple-Input-Multiple-Output (MIMO) technology, we devise two many-to-one cooperative schemes under converge-cast for both static and mobile ad hoc networks (MANETs), respectively. In a static network, our scheme highly utilizes hierarchical cooperation MIMO transmission. This feature overcomes the bottleneck which hinders converge-cast traffic from yielding ideal performance in traditional ad hoc network, by turning the originally interfering signals into interference-resistant ones. It helps to achieve an aggregate throughput up to Ω(n1-ε) for any ε >; 0. In the mobile ad hoc case, our scheme characterizes on joint transmission from multiple nodes to multiple receivers. With optimal network division where the number of nodes per cell is constant bounded, the achievable per-node throughput can reach Θ(1) with the corresponding delay reduced to Θ(k). The gain comes from the strong and intelligent cooperation between nodes in our scheme, along with the maximum number of concurrent active cells and the shortest waiting time before transmission for each node within a cell. This, to a great extent, increases the chances for each destination to receive the data it needs with minimum overhead on extra transmission. Moreover, our converge-based analysis well unifies and generalizes previous work since the results derived from converge-cast in our schemes can also cover other traffic patterns. Last but not least, our cooperative schemes are of interest not only from a theoretical perspective but also shed light on future design of MIMO schemes in wireless networks.

We investigate the fundamental relationship between node density and transmission delay in large-scale wireless ad hoc networks with unreliable links from percolation perspective. Previous works[11][2][10] have already showed the relationship between transmission delay and distance from source to destination. However, it still remains as an open question how transmission delay varies in accordance with node density. Answering this question can provide guidance for determining the number of nodes to meet the delay requirement when designing ad hoc networks. In this paper, we study the impact of node density λ on the ratio of delay and distance, denoted by γ(λ). We analytically characterize the properties of γ(λ) as a function of λ. And then we present upper and lower bounds to γ(λ). Next, we take propagation delay into consideration and obtain further results on the upper and lower bounds of γ(λ). Finally, we make simulations to verify our theoretical analysis.

In this paper, we study a unified mobility model for mobile multicast (MotionCast) with n nodes, and k destinations for each multicast session. This model considers nodes which can either serve in a local region or move around globally, with a restricted speed R. In other words, there are two particular forms: Local-based Speed-Restricted Model (LSRM) and Global-based Speed-Restricted Model (GSRM). We find that there is a special turning point when mobility speed varies from zero to the scale of network. For LSRM, as R increases, the delay-capacity trade-off ratio decreases iff R is greater than the turning point θ(√1/k); For GSRM, as R increases, the trade-off ratio decreases R R is smaller than the turning point, where the turning point is located at Θ(k√nn25) when k = o(n2/3), and at θ(k/n) when k = ω(n2/3). As k increases from 1 ton -1, the region that mobility can improve delay-capacity trade-off is enlarged. When R = θ(1), the optimal delay-capacity trade-off ratio is achieved. This paper presents a general approach to study the performance of wireless networks under more flexible mobility models.

Intercontact time between moving vehicles is one of the key metrics in vehicular ad hoc networks (VANETs) and central to forwarding algorithms and the end-to-end delay. Due to prohibitive costs, little work has conducted experimental study on intercontact time in urban vehicular environments. In this paper, we carry out an extensive experiment involving thousands of operational taxies in Shanghai city. Studying the taxi trace data on the frequency and duration of transfer opportunities between taxies, we observe that the tail distribution of the intercontact time, that is, the time gap separating two contacts of the same pair of taxies, exhibits an exponential decay, over a large range of timescale. This observation is in sharp contrast to recent empirical data studies based on human mobility, in which the distribution of the intercontact time obeys a power law. By analyzing a simplified mobility model that captures the effect of hot areas in the city, we rigorously prove that common traffic influxes, where large volume of traffic converges, play a major role in generating the exponential tail of the intercontact time. Our results thus provide fundamental guidelines on design of new vehicular mobility models in urban scenarios, new data forwarding protocols and their performance analysis.

Inter-contact time between moving vehicles is one of the key metrics in vehicular ad hoc networks (VANETs) and central to forwarding algorithms and the end-to-end delay. Due to prohibitive costs, little work has conducted experimental study on inter-contact time in urban vehicular environments. In this paper, we carry out an extensive experiment involving thousands of operational taxies in Shanghai city. Studying the taxi trace data on the frequency and duration of transfer opportunities between taxies, we observe that the tail distribution of the inter-contact time, that is the time gap separating two contacts of the same pair of taxies, exhibits a light tail such as one of an exponential distribution, over a large range of timescale. This observation is in sharp contrast to recent empirical data studies based on human mobility, in which the distribution of the inter-contact time obeys a power law. By performing a least squares fit, we establish an exponential model that can accurately depict the tail behavior of the inter-contact time in VANETs. Our results thus provide fundamental guidelines on design of new vehicular mobility models in urban scenarios, new data forwarding protocols and their performance analysis.

Initialization is an indispensable process for wireless sensor networks since newly deployed sensors lack a reliable infrastructure for communication. Many efforts have been made to address the problem on initialization. However, most of them fall into the category of energy efficiency. In mission-critical scenarios, it is vital to reduce the initialization time in order to gather information as early as possible. In this paper, we study a new problem of accelerating initialization. First, we provide a novel parallel initialization mechanism that selects cluster heads before deployment and organizes single-hop clusters simultaneously after random deployment. Then, we prior-estimate that the number of cluster head candidates from n sensors is ¿(log n). Finally, simulation results show that these cluster head candidates can achieve the parallel initialization bounded by 16 time slots even for a large n.

In a heterogeneous wireless network, where many different wireless networks interwork together, call admission control is an important issue to distribute user traffic among different access networks in order to provide quality of service (QoS). In this paper, we present and analyze the performance of a call admission control (CAC) policy for voice and data calls, which is based on one-hop cooperation among the mobile nodes, in a cellular-WLAN interworking scenario. For call-level queueing analysis of the CAC scheme, we use a more general phase-type distribution to model the characteristics of the system. Based on the analytical model, we illustrate the effect of one-hop cooperation on call-level QoS performance (e.g., call blocking probability, call dropping probability).

Most of analysis so far for IEEE 802.11(e) WLANs focuses on saturated condition. But it is of practical value to take into account the unsaturation case. In this paper, we extend Bianchi's Markov back-off model to unsaturated condition but analyze it using renewal-reward theorem. In this more general framework, we study the fixed point solution of the system and provide a condition to guarantee both the uniqueness and balance of the fixed point. From the fixed point analysis we find that under unsaturated condition, network parameters should be designed according to the traffic load in order to avoid short-term unfairness or multistability. Then, we study the system throughput. Furthermore, in an asymptotic regime with a large number of nodes, we provide explicit formulas for the collision probability, the aggregate attempt rate and the aggregate throughput. All of our analysis based on unsaturated condition is the generalized analysis which can be applied to saturated condition as well. We provide the validation of our analysis through ns2 simulations.