Search

The design of fusion engines is a subject of great importance in a variety of fields. In this paper, we focus on the problem of linear fusion at the feature level for multiple signal matrices with noises, with the features being extremal eigenvectors. When given multiple similarity matrices, the objective is to find an estimate of the latent signal eigenspace. The concentration result for the inner product of features from different matrix samples is developed, utilizing the random matrix theory. Based on of the theoretical results, we proposed an efficient algorithm, EigFuse, to solve the constrained data-driven optimization problem with different level of noises. Our method is of high efficiency by comparing it with state-of-the-art baseline approaches with multiple noise levels. Comprehensive experiments on several synthetic as well as real-life networks demonstrate our method’s superior performance. [ABSTRACT FROM AUTHOR]

Influence analysis aims at detecting influential vertices in networks and utilizing them in cost-effective business strategies. Influence analysis in large-scale networks is a key technique in many important applications ranging from viral marketing and online advertisement to recommender systems, and thus has attracted great interest from both academia and industry. Early investigations on influence analysis often assume static networks. However, it is well recognized that real networks like social networks and the web network are not static but evolve rapidly over time. Thus, to make the results of influence analysis in real networks up-to-date, we have to take network evolution into consideration. Incorporating evolution of networks into influence analysis raises many new challenges, since an evolving network often updates at a fast rate and, except for the network owner, the evolution is usually even not entirely known to people. In this survey, we provide an overview on recent research in influence analysis in evolving networks, which has not been systematically reviewed in literature. We first revisit mathematical models of evolving networks and commonly used influence models. Then, we review recent research in five major tasks of evolving network influence analysis. We also discuss some future directions to explore. [ABSTRACT FROM AUTHOR]

Skyline queries are important in many application domains. In this paper, we propose a novel structure Skyline Diagram, which given a set of points, partitions the plane into a set of regions, referred to as skyline polyominos. All query points in the same skyline polyomino have the same skyline query results. Similar to $k$ k th-order Voronoi diagram commonly used to facilitate $k$ k nearest neighbor ($k$ k NN) queries, skyline diagram can be used to facilitate skyline queries and many other applications. However, it may be computationally expensive to build the skyline diagram. By exploiting some interesting properties of skyline, we present several efficient algorithms for building the diagram with respect to three kinds of skyline queries, quadrant, global, and dynamic skylines. In addition, we propose an approximate skyline diagram which can significantly reduce the space cost. Experimental results on both real and synthetic datasets show that our algorithms are efficient and scalable. [ABSTRACT FROM AUTHOR]

Skyline, aiming at finding a Pareto optimal subset of points in a multi-dimensional dataset, has gained great interest due to its extensive use for multi-criteria analysis and decision making. The skyline consists of all points that are not dominated by any other points. It is a candidate set of the optimal solution, which depends on a specific evaluation criterion for optimum. However, conventional skyline queries, which return individual points, are inadequate in group querying case since optimal combinations are required. To address this gap, we study the skyline computation in the group level and propose efficient methods to find the Group-based skyline (G-skyline). For computing the front $l$ l skyline layers, we lay out an efficient approach that does the search concurrently on each dimension and investigates each point in the subspace. After that, we present a novel structure to construct the G-skyline with a queue of combinations of the first-layer points. We further demonstrate that the G-skyline is a complete candidate set of top- $l$ l solutions, which is the main superiority over previous group-based skyline definitions. However, as G-skyline is complete, it contains a large number of groups which can make it impractical. To represent the “contour” of the G-skyline, we define the Representative G-skyline (RG-skyline). Then, we propose a Group-based clustering (G-clustering) algorithm to find out RG-skyline groups. Experimental results show that our algorithms are several orders of magnitude faster than the previous work. [ABSTRACT FROM AUTHOR]

Outsourcing data and computation to cloud server provides a cost-effective way to support large scale data storage and query processing. However, due to security and privacy concerns, sensitive data (e.g., medical records) need to be protected from the cloud server and other unauthorized users. One approach is to outsource encrypted data to the cloud server and have the cloud server perform query processing on the encrypted data only. It remains a challenging task to support various queries over encrypted data in a secure and efficient way such that the cloud server does not gain any knowledge about the data, query, and query result. In this paper, we study the problem of secure skyline queries over encrypted data. The skyline query is particularly important for multi-criteria decision making but also presents significant challenges due to its complex computations. We propose a fully secure skyline query protocol on data encrypted using semantically-secure encryption. As a key subroutine, we present a new secure dominance protocol, which can be also used as a building block for other queries. Furthermore, we demonstrate two optimizations, data partitioning and lazy merging, to further reduce the computation load. Finally, we provide both serial and parallelized implementations and empirically study the protocols in terms of efficiency and scalability under different parameter settings, verifying the feasibility of our proposed solutions. [ABSTRACT FROM AUTHOR]

Network embedding assigns nodes in a network to low-dimensional representations and effectively preserves the network structure. Recently, a significant amount of progresses have been made toward this emerging network analysis paradigm. In this survey, we focus on categorizing and then reviewing the current development on network embedding methods, and point out its future research directions. We first summarize the motivation of network embedding. We discuss the classical graph embedding algorithms and their relationship with network embedding. Afterwards and primarily, we provide a comprehensive overview of a large number of network embedding methods in a systematic manner, covering the structure- and property-preserving network embedding methods, the network embedding methods with side information, and the advanced information preserving network embedding methods. Moreover, several evaluation approaches for network embedding and some useful online resources, including the network data sets and softwares, are reviewed, too. Finally, we discuss the framework of exploiting these network embedding methods to build an effective system and point out some potential future directions. [ABSTRACT FROM AUTHOR]

Network embedding, aiming to embed a network into a low dimensional vector space while preserving the inherent structural properties of the network, has attracted considerable attention. However, most existing embedding methods focus on the static network while neglecting the evolving characteristic of real-world networks. Meanwhile, most of previous methods cannot well preserve the high-order proximity, which is a critical structural property of networks. These problems motivate us to seek an effective and efficient way to preserve the high-order proximity in embedding vectors when the networks evolve over time. In this paper, we propose a novel method of Dynamic High-order Proximity preserved Embedding (DHPE). Specifically, we adopt the generalized SVD (GSVD) to preserve the high-order proximity. Then, by transforming the GSVD problem to a generalized eigenvalue problem, we propose a generalized eigen perturbation to incrementally update the results of GSVD to incorporate the changes of dynamic networks. Further, we propose an accelerated solution to the DHPE model so that it achieves a linear time complexity with respect to the number of nodes and number of changed edges in the network. Our empirical experiments on one synthetic network and several real-world networks demonstrate the effectiveness and efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we tackle a challenging problem inherent in a series of applications: tracking the influential nodes in dynamic networks. Specifically, we model a dynamic network as a stream of edge weight updates. This general model embraces many practical scenarios as special cases, such as edge and node insertions, deletions as well as evolving weighted graphs. Under the popularly adopted linear threshold model and independent cascade model, we consider two essential versions of the problem: finding the nodes whose influences passing a user specified threshold and finding the top-$k$ most influential nodes. Our key idea is to use the polling-based methods and maintain a sample of random RR sets so that we can approximate the influence of nodes with provable quality guarantees. We develop an efficient algorithm that incrementally updates the sample random RR sets against network changes. We also design methods to determine the proper sample sizes for the two versions of the problem so that we can provide strong quality guarantees and, at the same time, be efficient in both space and time. In addition to the thorough theoretical results, our experimental results on five real network data sets clearly demonstrate the effectiveness and efficiency of our algorithms. [ABSTRACT FROM PUBLISHER]

In a social network, even about the same information the excitement between different users are different. If we want to spread a piece of new information and maximize the expected total amount of excitement, which seed users should we choose? This problem indeed is substantially different from the renowned influence maximization problem and cannot be tackled using the existing approaches. In this paper, motivated by the demand in a few interesting applications, we model the novel problem of activity maximization, and tackle the problem systematically. We first analyze the complexity and the approximability of the problem. We develop an upper bound and a lower bound that are submodular so that the Sandwich framework can be applied. We then devise a polling-based randomized algorithm that guarantees a data dependent approximation factor. Our experiments on four real data sets clearly verify the effectiveness and scalability of our method, as well as the advantage of our method against the other heuristic methods. [ABSTRACT FROM PUBLISHER]

We present an online visual analytics approach to helping users explore and understand hierarchical topic evolution in high-volume text streams. The key idea behind this approach is to identify representative topics in incoming documents and align them with the existing representative topics that they immediately follow (in time). To this end, we learn a set of streaming tree cuts from topic trees based on user-selected focus nodes. A dynamic Bayesian network model has been developed to derive the tree cuts in the incoming topic trees to balance the fitness of each tree cut and the smoothness between adjacent tree cuts. By connecting the corresponding topics at different times, we are able to provide an overview of the evolving hierarchical topics. A sedimentation-based visualization has been designed to enable the interactive analysis of streaming text data from global patterns to local details. We evaluated our method on real-world datasets and the results are generally favorable. [ABSTRACT FROM PUBLISHER]