Search

Understanding intra-urban human mobility patterns and their potential driving forces are vital to city planning and commercial site selection. In this paper, we first investigate the functions of urban regions and how different region types dynamically influence people’s trip decisions. Furthermore, we characterize urban circadian rhythms by time-vary inter-regional transition probabilities between these regions with different functions, and integrate them into intervening opportunity model to predict human mobility. Public transportation card data in Shanghai are used to demonstrate the effectiveness of the model in terms of station passenger flows, travel time and trip flux. By taking regional function into consideration, the proposed model significantly improved the prediction accuracy. Quantitative analysis ulteriorly indicates that trip intentions and regional features are critical elements in trip flux prediction, especially in the afternoon and evening when people have an abundance of opportunities to travel by their own volition. When the function of a certain region changes, our model is able to make reasonable predictions accordingly. The results indicate the importance of considering individual travel motivation and regional function in modeling human mobility. The proposed model could serve as a guide for popularity and trip flux prediction in urban planning and reconstruction. [ABSTRACT FROM AUTHOR]

Pattern mining (PM) refers to the process of discovering patterns of interest to users from data. However, most studies have considered only one pattern, such as frequent pattern or high-utility pattern. With the continuous requirement of businesses in various industries, the single-objective PM methods are difficult to meet the increasingly diverse needs of users. In this paper, a multi-objective problem model for high quality pattern mining (HQPM) is proposed, where the objectives are support, occupancy, and utility. In order to solve the proposed three-objective problem efficiently, an improved multi-objective evolutionary algorithm for HQPM (MOEA-PM) is proposed. Two kinds of population initialization strategies are designed, which is used to ensure the population is effectively distributed in the feasible solution space. By taking the properties of the model into consideration, an auxiliary tool is proposed to accelerate the convergence of the algorithm. Experimental results on real-world datasets show that the proposed three-objective problem model with the MOEA-PM algorithm can discover patterns that are both frequently occurring and has a high utility in the transaction datasets, while at the same time being relatively complete. Compared with the state-of-the-art MOEA-based HQPM algorithms, MOEA-PM has better performance in terms of efficiency, quality, and convergence speed. [ABSTRACT FROM AUTHOR]

Knowledge graph is becoming an indispensable resource that offers structured information for numerous AI applications. However, the knowledge graph often suffers from its incompleteness. Building a complete, high-quality knowledge graph is time-consuming and requires significant human annotation efforts. In this paper, we study the Knowledge Graph Population task, which aims at extending the scale of structured knowledge, with a special focus on reducing data preparation and annotation efforts. Previous works mainly based on discriminative methods build classifiers and verify candidate triplets that are extracted from texts, which heavily rely on the quality of data collection and co-occurrance of entities in the text. However, such methods fail to generalize on entity pairs that are not highly co-occurred, and fail to discover entity pairs that are not co-occurred at all in the given text corpus. We introduce a generative perspective to approach this task and define each relationship by learning the data distribution that embodies the core common properties for relational reasoning. A generative model KGGen is proposed, which samples from the learned data distribution for each relation and can generate triplets regardless of entity pair co-occurrence in the text corpus. To further improve the generation quality while alleviate human annotation efforts, adversarial learning is adopted to not only encourage generating high quality triplets, but also give model the ability to automatically assess the generation quality. Quantitative and qualitative experimental results conducted on two real-world generic knowledge graphs show that the proposed model KGGen generates novel and meaningful triplets with improved efficiency and less human annotation comparing with the state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

With the ever-increasing urbanization process, modeling people's spatiotemporal activities from their online traces has become a crucial task. State-of-the-art methods for this task rely on cross-modal embedding, which maps items from different modalities (e.g., location, time, text) into the same latent space. Despite their inspiring results, existing cross-modal embedding methods merely capture co-occurrences between items without modeling their high-order interactions. In this paper, we first construct two graphs from raw data records to represent the user interaction graph layer and activity graph layer and propose a hierarchical cross-modal embedding method that takes the high-order relationships into consideration. The key notion behind our method is a novel hierarchical embedding framework with meta-graphs connecting different layers. We introduce both inter-record and intra-record meta-graph structures, which enable learning distributed representations that preserve high-order proximities across graphs from different layers. Our empirical experiments on three real-world datasets demonstrate that our method not only outperforms state-of-the-art methods for spatiotemporal activity prediction, but also captures cross-modal proximity at a finer granularity. [ABSTRACT FROM AUTHOR]

Multi-layer network community detection has drawn an increasing amount of attention recently. Despite success, the existing methods mainly focus on the lower-order connectivity structure at the level of individual nodes and edges. And the higher-order connectivity structure has been largely ignored, which contains better signature of community compared with edges. The main challenges in utilizing higher-order structure for multi-layer network community detection are that the most representative higher-order structure may vary from one layer to another and the connectivity structure formed by the same node subset may exhibit different higher-order connectivity patterns in different layers. To this end, this paper proposes a novel higher-order structure, termed harmonic motif, which is a dense subgraph having on average the largest statistical significance in each layer. Based on the harmonic motif, a primary layer is constructed by integrating higher-order structural information from all layers. Additionally, the higher-order structural information of each individual layer is taken as the auxiliary information. A coupling is established between the primary layer and each auxiliary layer. Accordingly, a harmonic motif modularity is designed to generate the community structure. Extensive experiments on eleven real-world multi-layer network datasets have been conducted to confirm the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Recent years have witnessed the world-wide emergence of mega-metropolises with incredibly huge populations. Understanding residents mobility patterns, or urban dynamics, thus becomes crucial for building modern smart cities. In this paper, we propose a Neighbor-Regularized and context-aware Non-negative Tensor Factorization model (NR-cNTF) to discover interpretable urban dynamics from urban heterogeneous data. Different from many existing studies concerned with prediction tasks via tensor completion, NR-cNTF focuses on gaining urban managerial insights from spatial, temporal, and spatio-temporal patterns. This is enabled by high-quality Tucker factorizations regularized by both POI-based urban contexts and geographically neighboring relations. NR-cNTF is also capable of unveiling long-term evolutions of urban dynamics via a pipeline initialization approach. We apply NR-cNTF to a real-life data set containing rich taxi GPS trajectories and POI records of Beijing. The results indicate: 1) NR-cNTF accurately captures four kinds of city rhythms and seventeen spatial communities; 2) the rapid development of Beijing, epitomized by the CBD area, indeed intensifies the job-housing imbalance; 3) the southern areas with recent government investments have shown more healthy development tendency. Finally, NR-cNTF is compared with some baselines on traffic prediction, which further justifies the importance of urban contexts awareness and neighboring regulations. [ABSTRACT FROM AUTHOR]

Social hierarchy (i.e., pyramid structure of societies) is a fundamental concept in sociology and social network analysis. The importance of social hierarchy in a social network is that the topological structure of the social hierarchy is essential in both shaping the nature of social interactions between individuals and unfolding the structure of the social networks. The social hierarchy found in a social network can be utilized to improve the accuracy of link prediction, provide better query results, rank web pages, and study information flow and spread in complex networks. In this paper, we model a social network as a directed graph G, and consider the social hierarchy as DAG (directed acyclic graph) of G, denoted as GD. By DAG, all the vertices in G can be partitioned into different levels, the vertices at the same level represent a disjoint group in the social hierarchy, and all the edges in DAG follow one direction. The main issue we study in this paper is how to find DAG GD in G. The approach we take is to find GD by removing all possible cycles from G such that G=U(G)∪GD, where U(G) is a maximum Eulerian subgraph which contains all possible cycles. We give the reasons for doing so, investigate the properties of GD found, and discuss the applications. In addition, we develop a novel two-phase algorithm, called Greedy-&-Refine, which greedily computes an Eulerian subgraph and then refines this greedy solution to find the maximum Eulerian subgraph. We give a bound between the greedy solution and the optimal. The quality of our greedy approach is high. We conduct comprehensive experimental studies over 14 real-world datasets. The results show that our algorithms are at least two orders of magnitude faster than the baseline algorithm. [ABSTRACT FROM AUTHOR]

The demand for automatic extraction of true information (i.e., truths) from conflicting multi-source data has soared recently. A variety of truth discovery methods have witnessed great successes via jointly estimating source reliability and truths. All existing truth discovery methods focus on providing a point estimator for each object's truth, but in many real-world applications, confidence interval estimation of truths is more desirable, since confidence interval contains richer information. To address this challenge, in this paper, we propose a novel truth discovery method (ETCIBoot) to construct confidence interval estimates as well as identify truths, where the bootstrapping techniques are nicely integrated into the truth discovery procedure. Due to the properties of bootstrapping, the estimators obtained by ETCIBoot are more accurate and robust compared with the state-of-the-art truth discovery approaches. The proposed framework is further adapted to deal with large-scale truth discovery task in distributed paradigm. Theoretically, we prove the asymptotical consistency of the confidence interval obtained by ETCIBoot. Experimentally, we demonstrate that ETCIBoot is not only effective in constructing confidence intervals but also able to obtain better truth estimates. [ABSTRACT FROM AUTHOR]

Privacy concern in data sharing especially for health data gains particularly increasing attention nowadays. Now, some patients agree to open their information for research use, which gives rise to a new question of how to effectively use the public information to better understand the private dataset without breaching privacy. In this paper, we specialize this question as selecting an optimal subset of the public dataset for M-estimators in the framework of differential privacy (DP) in [1] . From a perspective of non-interactive learning, we first construct the weighted private density estimation from the hybrid datasets under DP. Along the same line as [2] , we analyze the accuracy of the DP M-estimators based on the hybrid datasets. Our main contributions are (i) we find that the bias-variance tradeoff in the performance of our M-estimators can be characterized in the sample size of the released dataset; (ii) based on this finding, we develop an algorithm to select the optimal subset of the public dataset to release under DP. Our simulation studies and application to the real datasets confirm our findings and set a guideline in the real application. [ABSTRACT FROM AUTHOR]

Generalization is an effective technique for protecting confidential information of individuals, and has been studied by proposing numerous algorithms. However, the previous works do not separate the protection against identity disclosure and sensitive disclosure. Thus, when the requirement of attribute protection is higher than that of identity protection, generalization for $l$ -diversity causes overprotection for identity and large mounts of information utility loss. This paper presents a novel approach, called cross-bucket generalization, as a solution to meet the problem. The rationale is to divide microdata into equivalence groups and buckets. First, it provides separate protection for identity and sensitive values, and the level of protection can be flexibly adjusted based on actual demands. Second, the sizes of equivalence groups and buckets are minimized as far as possible by only satisfying the protection requirements, which avoid the overprotection for identity and reduce information loss. The experiments we conducted illustrate the effectiveness of our solution. [ABSTRACT FROM AUTHOR]

Heterogeneous information networks that consist of multi-type, interconnected objects are becoming increasingly popular, such as social media networks and bibliographic networks. The task of linking named entity mentions detected from unstructured Web text with their corresponding entities in a heterogeneous information network is of practical importance for the problem of information network population. This task is challenging due to name ambiguity and limited knowledge existing in the network. Most existing entity linking methods focus on linking entities with Wikipedia and cannot be applied to our task. In this paper, we present SHINE+, a general framework for linking named entitieS in Web free text with a Heterogeneous I nformation NEtwork. We propose a probabilistic linking model, which unifies an entity popularity model with an entity object model. As the entity knowledge contained in the information network is insufficient, we propose a knowledge population algorithm to iteratively enrich the network entity knowledge by leveraging the context information of mentions mapped by the linking model with high confidence, which subsequently boosts the linking performance. Experimental results over two real heterogeneous information networks (i.e., DBLP and IMDb) demonstrate the effectiveness and efficiency of our proposed framework in comparison with the baselines. [ABSTRACT FROM PUBLISHER]

A standard procedure for evaluating the performance of classification algorithms is k-fold cross validation. Since the training sets for any pair of iterations in k-fold cross validation are overlapping when the number of folds is larger than two, the resulting accuracy estimates are considered to be dependent. In this paper, the overlapping of training sets is shown to be irrelevant in determining whether two fold accuracies are dependent or not. Then a statistical method is proposed to test the appropriateness of assuming independence for the accuracy estimates in k-fold cross validation. This method is applied on 20 data sets, and the experimental results suggest that it is generally appropriate to assume that the fold accuracies are independent. The cross validation of non-overlapping training sets can make fold accuracies to be dependent. However, this dependence almost has no impact on estimating the sample variance of fold accuracies, and hence they can generally be assumed to be independent. [ABSTRACT FROM PUBLISHER]

This paper discusses the bias problem when estimating the population size of big data such as online social networks (OSN) using uniform random sampling and simple random walk. Unlike the traditional estimation problem where the sample size is not very small relative to the data size, in big data, a small sample relative to the data size is already very large and costly to obtain. We point out that when small samples are used, there is a bias that is no longer negligible. This paper shows analytically that the relative bias can be approximated by the reciprocal of the number of collisions; thereby, a bias correction estimator is introduced. The result is further supported by both simulation studies and the real Twitter network that contains 41.7 million nodes. [ABSTRACT FROM AUTHOR]

The widespread use of online social networks (OSNs) to disseminate information and exchange opinions, by the general public, news media, and political actors alike, has enabled new avenues of research in computational political science. In this paper, we study the problem of quantifying and inferring the political leaning of Twitter users. We formulate political leaning inference as a convex optimization problem that incorporates two ideas: (a) users are consistent in their actions of tweeting and retweeting about political issues, and (b) similar users tend to be retweeted by similar audience. We then apply our inference technique to 119 million election-related tweets collected in seven months during the 2012 U.S. presidential election campaign. On a set of frequently retweeted sources, our technique achieves 94 percent accuracy and high rank correlation as compared with manually created labels. By studying the political leaning of 1,000 frequently retweeted sources, 232,000 ordinary users who retweeted them, and the hashtags used by these sources, our quantitative study sheds light on the political demographics of the Twitter population, and the temporal dynamics of political polarization as events unfold. [ABSTRACT FROM AUTHOR]

The past decade has seen a dramatic increase in the amount of data captured and made available to scientists for research. This increase amplifies the difficulty scientists face in finding the data most relevant to their information needs. In prior work, we hypothesized that Information Retrieval-style ranked search can be applied to data sets to help a scientist discover the most relevant data amongst the thousands of data sets in many formats, much like text-based ranked search helps users make sense of the vast number of Internet documents. To test this hypothesis, we explored the use of ranked search for scientific data using an existing multi-terabyte observational archive as our test-bed. In this paper, we investigate whether the concept of varying relevance, and therefore ranked search, applies to numeric data—that is, are data sets are enough like documents for Information Retrieval techniques and evaluation measures to apply? We present a user study that demonstrates that data set similarity resonates with users as a basis for relevance and, therefore, for ranked search. We evaluate a prototype implementation of ranked search over data sets with a second user study and demonstrate that ranked search improves a scientist's ability to find needed data. [ABSTRACT FROM PUBLISHER]

Exponential growth of information generated by online social networks demands effective and scalable recommender systems to give useful results. Traditional techniques become unqualified because they ignore social relation data; existing social recommendation approaches consider social network structure, but social contextual information has not been fully considered. It is significant and challenging to fuse social contextual factors which are derived from users’ motivation of social behaviors into social recommendation. In this paper, we investigate the social recommendation problem on the basis of psychology and sociology studies, which exhibit two important factors: individual preference and interpersonal influence. We first present the particular importance of these two factors in online behavior prediction. Then we propose a novel probabilistic matrix factorization method to fuse them in latent space. We further provide a scalable algorithm which can incrementally process the large scale data. We conduct experiments on both Facebook style bidirectional and Twitter style unidirectional social network data sets. The empirical results and analysis on these two large data sets demonstrate that our method significantly outperforms the existing approaches. [ABSTRACT FROM AUTHOR]

The discovery of evolving communities in dynamic networks is an important research topic that poses challenging tasks. Evolutionary clustering is a recent framework for clustering dynamic networks that introduces the concept of temporal smoothness inside the community structure detection method. Evolutionary-based clustering approaches try to maximize cluster accuracy with respect to incoming data of the current time step, and minimize clustering drift from one time step to the successive one. In order to optimize both these two competing objectives, an input parameter that controls the preference degree of a user towards either the snapshot quality or the temporal quality is needed. In this paper the detection of communities with temporal smoothness is formulated as a multiobjective problem and a method based on genetic algorithms is proposed. The main advantage of the algorithm is that it automatically provides a solution representing the best trade-off between the accuracy of the clustering obtained, and the deviation from one time step to the successive. Experiments on synthetic data sets show the very good performance of the method when compared with state-of-the-art approaches. [ABSTRACT FROM PUBLISHER]