1 December 2002 in ACM Computing Surveys
The unabated growth and increasing significance of the World Wide Web has resulted in a flurry of research activity to improve its capacity for serving information more effectively. But at the heart of these efforts lie implicit assumptions about "quality" and "usefulness" of Web resources and services. This observation points towards measurements and models that quantify various attributes of web sites. The science of measuring all aspects of information, especially its storage and retrieval or informetrics has interested information scientists for decades before the existence of the Web. Is Web informetrics any different, or is it just an application of classical informetrics to a new medium? In this article, we examine this issue by classifying and discussing a wide ranging set of Web metrics. We present the origins, measurement functions, formulations and comparisons of well-known Web metrics for quantifying Web graph properties , Web page significance , Web page similarity , search and retrieval , usage characterization and information theoretic properties . We also discuss how these metrics can be applied for improving Web information access and use.
5 May 2022 in IEEE Transactions on Computational Social Systems
Since its introduction in 2003, the influence maximization (IM) problem has drawn significant research attention in the literature. The aim of IM, which is NP-hard, is to select a set of $k$ users known as seed users who can influence the most individuals in the social network. The state-of-the-art algorithms estimate the expected influence of nodes based on sampled diffusion paths. As the number of required samples has been recently proven to be lower bounded by a particular threshold that presets tradeoff between the accuracy and the efficiency, the result quality of these traditional solutions is hard to be further improved without sacrificing efficiency. In this article, we present an orthogonal and novel paradigm to address the IM problem by leveraging deep reinforcement learning (RL) to estimate the expected influence. In particular, we present a novel framework called deeP reInforcement leArning-based iNfluence maximizatiOn (PIANO) that incorporates network embedding and RL techniques to address this problem. In order to make it practical, we further present PIANO-E and PIANO $\text{@}\langle d\rangle $ , both of which can be applied directly to answer IM without training the model from scratch. Experimental study on real-world networks demonstrates that PIANO achieves the best performance with respect to efficiency and influence spread quality compared to state-of-the-art classical solutions. We also demonstrate that the learned parametric models generalize well across different networks. Besides, we provide a pool of pretrained PIANO models such that any IM task can be addressed by directly applying a model from the pool without training over the targeted network.
19 October 2015 in IEEE Transactions on Knowledge and Data Engineering
The increasing availability and significance of large-scale protein-protein interaction (PPI) data has resulted in a flurry of research activity to comprehend the organization, processes, and functioning of cells by analyzing these data at network level. Network clustering, that analyzes the topological and functional properties of a PPI network to identify clusters of interacting proteins, has gained significant popularity in the bioinformatics as well as data mining research communities. Many studies since the last decade have shown that clustering PPI networks is an effective approach for identifying functional modules, revealing functions of unknown proteins, etc. In this paper, we examine this issue by classifying, discussing, and comparing a wide ranging approaches proposed by the bioinformatics community to cluster PPI networks. A pervasive desire of this review is to emphasize the uniqueness of the network clustering problem in the context of PPI networks and highlight why generic network clustering algorithms proposed by the data mining community cannot be directly adopted to address this problem effectively. We also review a closely related problem to PPI network clustering, network summarization, which can enable us to make sense out of the information contained in large PPI networks by generating multi-level functional summaries.
5 August 2014 in The VLDB Journal
19 May 2020 in IEEE Transactions on Knowledge and Data Engineering
Time-series shapelets are discriminative subsequences, recently found effective for time series classification (TSC). It is evident that the quality of shapelets is crucial to the accuracy of TSC. However, major research has focused on building accurate models from some shapelet candidates. To determine such candidates, existing studies are surprisingly simple, e.g., enumerating subsequences of some fixed lengths, or randomly selecting some subsequences as shapelet candidates. The major bulk of computation is then on building the model from the candidates. In this paper, we propose a novel efficient shapelet discovery method, called BSPCOVER, to discover a set of high-quality shapelet candidates for model building. Specifically, BSPCOVER generates abundant candidates via Symbolic Aggregate approXimation with sliding window, then prunes identical and highly similar candidates via Bloom filters, and similarity matching, respectively. We next propose a p-Cover algorithm to efficiently determine discriminative shapelet candidates that maximally represent each time-series class. Finally, any existing shapelet learning method can be adopted to build a classification model. We have conducted extensive experiments with well-known time-series datasets and representative state-of-the-art methods. Results show that BSPCOVER speeds up the state-of-the-art methods by more than 70 times, and the accuracy is often comparable to or higher than existing works.