检索结果-内蒙古大学图书馆

Improving search via personalized query expansion using social media

INFORMATION RETRIEVAL 2012年第3-4期15卷 218-242页

作者： Zhou, Dong Lawless, Seamus Wade, Vincent Trinity Coll Dublin Sch Comp Sci & Stat Knowledge & Data Engn Grp Ctr Next Generat Localisat Dublin 2 Ireland

Social tagging systems have gained increasing popularity as a method of annotating and categorizing a wide range of different web resources. Web search that utilizes social tagging data suffers from an extreme example of the vocabulary mismatch problem encountered in traditional information retrieval (IR). This is due to the personalized, unrestricted vocabulary that users choose to describe and tag each resource. Previous research has proposed the utilization of query expansion to deal with search in this rather complicated space. However, non-personalized approaches based on relevance feedback and personalized approaches based on co-occurrence statistics only showed limited improvements. This paper proposes a novel query expansion framework based on individual user profiles mined from the annotations and resources the user has marked. The underlying theory is to regularize the smoothness of word associations over a connected graph using a regularizer function on terms extracted from top-ranked documents. The intuition behind the model is the prior assumption of term consistency: the most appropriate expansion terms for a query are likely to be associated with, and influenced by terms extracted from the documents ranked highly for the initial query. The framework also simultaneously incorporates annotations and web documents through a Tag-Topic model in a latent graph. The experimental results suggest that the proposed personalized query expansion method can produce better results than both the classical non-personalized search approach and other personalized query expansion methods. Hence, the proposed approach significantly benefits personalized web search by leveraging users' social media data.

关键词： Personalization Query expansion Web search Social media Tag-Topic model graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Searching a polygonal room with one door by a 1-searcher

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2000年第2期10卷 201-220页

作者： Lee, JH Park, SM Chwa, KY Korea Adv Inst Sci & Technol Dept Comp Sci Yusong Gu Taejon 305701 South Korea

The 1-searcher is a mobile guard whose visibility is limited to a ray emanating from his position, where the direction of the ray can be changed continuously with bounded angular rotation speed. Given a polygonal region P with a specified boundary point d, is it possible for a 1-searcher to eventually see a mobile intruder that is arbitrarily faster than the searcher within P, before the intruder reaches d? We decide this question in O(n log n)-time for an n-sided polygon. Our main result is a simple characterization of the class of polygons (with a boundary point d) that admits such a search strategy. We also present a simple O(n(2))-time algorithm for constructing a search schedule, if one exists. Finally, we compare the search capability of a 1-searcher with that of two guards.

关键词： visibility motion planning pursuit-evasion graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Generalizations of Wiener Polarity Index and Terminal Wiener Index

引用

graphS AND COMBINATORICS 2013年第5期29卷 1403-1416页

作者： Ilic, Aleksandar Ilic, Milovan Univ Nis Fac Sci & Math Nish 18000 Serbia Metropolitan Univ Fac Informat Technol Belgrade 11000 Serbia

In theoretical chemistry, distance-based molecular structure descriptors are used for modeling physical, pharmacologic, biological and other properties of chemical compounds. We introduce a generalized Wiener polarity index W (k) (G) as the number of unordered pairs of vertices {u, v} of G such that the shortest distance d (u, v) between u and v is k (this is actually the kth coefficient in the Wiener polynomial). For k = 3, we get standard Wiener polarity index. Furthermore, we generalize the terminal Wiener index TW (k) (G) as the sum of distances between all pairs of vertices of degree k. For k = 1, we get standard terminal Wiener index. In this paper we describe a linear time algorithm for computing these indices for trees and partial cubes, and characterize extremal trees maximizing the generalized Wiener polarity index and generalized terminal Wiener index among all trees of given order n.

关键词： Distance in graphs Wiener polarity index Terminal Wiener index Wiener index Partial cube graph algorithm

来源：评论

学校读者我要写书评

暂无评论

The (p, q)-total labeling problem for trees

引用

DISCRETE MATHEMATICS 2012年第8期312卷 1407-1420页

作者： Hasunuma, Toru Ishii, Toshimasa Ono, Hirotaka Uno, Yushi Otani Univ Commerce Dept Informat & Management Sci Otaru Hokkaido 0478501 Japan Univ Tokushima Dept Math & Nat Sci Tokushima 7708502 Japan Kyushu Univ Dept Econ Engn Fukuoka 8128581 Japan Osaka Prefecture Univ Dept Math & Informat Sci Grad Sch Sci Sakai Osaka 5998531 Japan

A (p, q)-total labeling of a graph G is an assignment f from the vertex set V (G) and the edge set E(G) to the set of nonnegative integers such that left perpendicularf(x) - f (y)right perpendicular >= p if x is a vertex and y is an edge incident to x, and left perpendicularf(x) - f (y)right perpendicular >= q if x and y are a pair of adjacent vertices or a pair of adjacent edges, for all x and y in V(G) U E(G). A k-(p, q)-total labeling is a (p, q)-total labeling f : V (G) boolean OR E(G) -> {0, ..., k}, and the (p, q)-total labeling problem asks the minimum k, which we denote by Apl.q (G), among all possible assignments. In this paper, we first give new upper and lower bounds on lambda(T)(p,q)(G) for some classes of graphs G, in particular, tight bounds on lambda(T)(p,q)(T) for trees T. We then show that if p <= 3q/2, the problem for trees T is linearly solvable, and completely determine lambda(T)(p,q)(T) for trees T with Delta >= 4, where Delta is the maximum degree of T. It is contrasting to the fact that the L(p, q)-labeling problem, which is a generalization of the (p, q)-total labeling problem, is NP-hard for any two positive integers p and q such that q is not a divisor of p. (C) 2012 Elsevier B.V. All rights reserved.

关键词： (p, q)-total labeling L(p, q)-labeling Tree graph algorithm Distance constrained labeling

来源：评论

学校读者我要写书评

暂无评论

Finding Small and Large k-Clique Instances on a Quantum Computer

IEEE TRANSACTIONS ON QUANTUM ENGINEERING

引用

IEEE TRANSACTIONS ON QUANTUM ENGINEERING 2020年 1卷 1页

作者： Metwalli, Sara Ayman Le Gall, Francois Van Meter, Rodney Keio Univ Quantum Comp Ctr Tokyo 1088345 Japan Nagoya Univ Grad Sch Math Nagoya Aichi 4648601 Japan

algorithms for triangle finding, the smallest nontrivial instance of the k-clique problem, have been proposed for quantum computers. Still, those algorithms assume the use of fixed access time quantum RAM. In this article, we present a practical gate-based approach to both the triangle-finding problem and its NP-hard k-clique generalization. We examine both constant factors for near-term implementation on a noisy intermediate scale quantum computing (NISQ) device and the scaling of the problem to evaluate long-term use of quantum computers. We compare the time complexity and circuit practicality of the theoretical approach and actual implementation. We propose and apply two different strategies to the k-clique problem, examining the circuit size of Qiskit implementations. We analyze our implementations by simulating triangle finding with various error models, observing the effect on damping the amplitude of the correct answer, and compare to execution on six real IBM quantum machines. Finally, we estimate the approximate quantum volume needed so that the smallest instance of our approach can be executable with minimal error on a real NISQ device.

关键词： Clique finding graph algorithm Grover's algorithm noisy intermediate scale quantum computing (NISQ)

来源：评论

学校读者我要写书评

暂无评论

An O(n^1.75) algorithm for L(2,1)-labeling of trees

引用

THEORETICAL COMPUTER SCIENCE 2009年第38-40期410卷 3702-3710页

作者： Hasunuma, Toru Ishii, Toshimasa Ono, Hirotaka Uno, Yushi Kyushu Univ Dept Comp Sci & Commun Engn Fukuoka 8128581 Japan Univ Tokushima Dept Math & Nat Sci Tokushima 7708502 Japan Otaru Univ Dept Informat & Management Sci Otaru Hokkaido 0478501 Japan Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka 5998531 Japan

An L(2, 1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that [f (x) - f (y)] >= 2 if x and y are adjacent and [f (x) - f (y)] >= 1 if x and y are at distance 2 for all x and y in V(G). A k-L(2, 1)-labeling is an L(2, 1)-labeling f : V(G) -> {0, ... , k}, and the L(2, 1)-labeling problem asks the minimum k, which we denote by lambda(G), among all possible L(2, 1)-labelings. It is known that this problem is NP-hard even for graphs of treewidth 2. Tree is one of a few classes for which the problem is polynomially solvable, but still only an O(Delta(4.5)n) time algorithm for a tree T has been known so far, where Delta is the maximum degree of T and n = vertical bar V(T)vertical bar. In this paper, we first show that an existent necessary condition for lambda(T) = Delta + 1 is also sufficient for a tree T with Delta = Omega(root n), which leads to a linear time algorithm for computing lambda(T) under this condition. We then show that lambda(T) can be computed in O(Delta(1.5)n) time for any tree T. Combining these, we finally obtain an O(n(1.75)) time algorithm, which substantially improves upon previously known results. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Frequency/channel assignment graph algorithm L(2,1)-labeling Vertex coloring

来源：评论

学校读者我要写书评

暂无评论

ON EFFICIENT PARALLEL STRONG ORIENTATION

引用

INFORMATION PROCESSING LETTERS 1985年第5期20卷 235-240页

作者： VISHKIN, U NYU COURANT INST MATH SCIDEPT COMP SCINEW YORKNY 10003

A family of parallel random access machines (PRAM) characterized by synchronous processors accessing a common memory is examined. The family includes 3 types of PRAMs, which vary in power according to whether they allow simultaneous reading and writing from the same memory. A high-level description is provided for an algorithm that ensures an efficient parallel strong orientation for this family of PRAMs.

关键词： graph algorithm parallel algorithm strongly connected component

来源：评论

学校读者我要写书评

暂无评论

A review of clique-based overlapping community detection algorithms

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2022年第8期64卷 2023-2058页

作者： Gupta, Sumit Kumar Singh, Dhirendra Pratap Choudhary, Jaytrilok Maulana Azad Natl Inst Technol Dept Comp Sci & Engn Bhopal 462001 MP India

Detection of communities is one of the prominent characteristics of vast and complex networks like social networks, collaborative networks, and web graphs. In the modern era, new users get added to these complex networks, which results in an expansion of application-generated networks. Extracting relevant information from these large networks has become one of the most prominent research areas. Community detection tries to reduce the application-generated graph into smaller communities in which nodes within the community are similar. Most of the recent proposals are focused on detecting overlapping communities in the network with higher accuracy. An integral issue in graph theory is the enumeration of cliques in a larger graph. As clique is a group of completely connected nodes which shows the explicit communities means these nodes share the same types of information. Clique-based community detection algorithm utilizing the clique property of the graph also identifies the implicit communities, which is not directly shown in the graph. Many overlapping community detection algorithms are proposed by researchers that rely on cliques. The goal of this paper is to offer a comparative analysis of clique-based community detection algorithms. This paper provides a pervasive survey on research works identifying the cliques in a network for detecting overlapping communities. We bring together most of the state-of-the-art clique-based community detection algorithms into a single article with their accessible benchmark data sets. It presents a detailed description of methods based on K-cliques, maximal cliques, and triad percolation methods and addresses these approaches' challenges. Finally, the comparative analysis of overlapping community detection methodologies is also reported.

关键词： graph algorithm Community detection algorithm Clique-based algorithm Maximal clique-based algorithm Clique percolation method Triad percolation method Overlapping community detection algorithm

来源：评论

学校读者我要写书评

暂无评论

A new approach to the minimum cut problem

引用

JOURNAL OF THE ACM 1996年第4期43卷 601-640页

作者： Karger, DR Stein, C DARTMOUTH COLL HANOVER NH 03755 USA

This paper presents a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in O(n(2)log(3)n) time, a significant improvement over the previous (O) over tilde(mn) time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures. Our algorithm can be parallelized to run in RNC with n(2) processors;this gives the first proof that the minimum cut problem can be solved in RNC. The algorithm does more than find a single minimum cut;it finds all of them. With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of cu of the minimum cut's in expected (O) over tilde(n(2 alpha)) time, or in RNC with n(2 alpha) processors. The problem of finding a minimum multiway cut of a graph into r pieces is solved in expected (O) over tilde(n(2(r-1))) time, or in RNC with n(2(r-1)) processors. The ''trace'' of the algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representation for minimum cuts.

关键词： graph algorithm minimum cut network reliability parallel computing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Robustness of Topological Supertree Methods for Reconciling Dense Incompatible Data

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2009年第1期6卷 62-75页

作者： Willson, Stephen J. Iowa State Univ Dept Math Ames IA 50011 USA

Given a collection of rooted phylogenetic trees with overlapping sets of leaves, a compatible supertree S is a single tree whose set of leaves is the union of the input sets of leaves and such that S agrees with each input tree when restricted to the leaves of the input tree. Typically, with trees from real data, no compatible supertree exists, and various methods may be utilized to reconcile the incompatibilities in the input trees. This paper focuses on a measure of robustness of a supertree method called its "radius" R. The larger the value of R is, the further the data set can be from a natural correct tree T, and yet, the method will still output T. It is shown that the maximal possible radius for a method is R=1/2. Many familiar methods, both for supertrees and consensus trees, are shown to have R=0, indicating that they need not output a tree T that would seem to be the natural correct answer. A polynomial-time method, Normalized Triplet Supertree ( NTS), with the maximal possible R=1/2 is defined. A geometric interpretation is given, and NTS is shown to solve an optimization problem. Additional properties of NTS are described.

关键词： graph algorithm phylogenetic tree supertree rooted triple

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：