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

Efficient community detection with additive constrains on large networks

KNOWLEDGE-BASED SYSTEMS 2013年 52卷 268-278页

作者： Li, Yakun Wang, Hongzhi Li, Jianzhong Gao, Hong Harbin Inst Technol Dept Comp Sci & Technol Harbin 150001 Peoples R China

The community structure is one of the most important patterns in network. Since finding the communities in the network can significantly improve our understanding of the complex relations, lots of work has been done in recent years. Yet it still lies vacant on the exact definition and practical algorithms for community detection. This paper proposes a novel definition for community which overcomes the drawbacks of existing methods. With the new definition, efficient community detection algorithms are developed, which take advantage of additive topological and other constrains to discover communities in arbitrary shape based on the feedback. The algorithm has a linear run time with the size of graph. Experimental results demonstrate that the community definition in this paper is effective and the algorithm is scalable for large graphs. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Community detection Feedback control Additive constrains Large networks Scale-free network graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A TECHNIQUE FOR EXACT COMPUTATION OF PRECOLORING EXTENSION ON INTERVAL graphS

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2013年第1期24卷 109-122页

作者： Ehmsen, Martin R. Larsen, Kim S. Univ Southern Denmark Dept Math & Comp Sci DK-5230 Odense M Denmark

Inspired by a real life application, we investigate the computationally hard problem of extending a precoloring of an interval graph to a proper coloring under some bound on the number of available colors. We are interested in quickly determining whether or not such an extension exists on instances occurring in practice in connection with campsite bookings on a campground. A naive exhaustive search does not terminate in reasonable time. We have formulated a new approach which moves the computation time within I he usable range on all the data samples available to us.

关键词： graph algorithm interval graphs graph coloring

来源：评论

学校读者我要写书评

暂无评论

Learning to Reassemble Shredded Documents

引用

IEEE TRANSACTIONS ON MULTIMEDIA 2013年第3期15卷 582-593页

作者： Richter, Fabian Ries, Christian X. Cebron, Nicolas Lienhart, Rainer Univ Augsburg Multimedia Comp & Comp Vis Lab D-86159 Augsburg Germany

In this paper, we address the problem of automatically assembling shredded documents. We propose a two-step algorithmic framework. First, we digitize each fragment of a given document and extract shape- and content-based local features. Based on these multimodal features, we identify pairs of corresponding points on all pairs of fragments using an SVM classifier. Each pair is considered a point of attachment for aligning the respective fragments. In order to restore the layout of the document, we create a document graph in which nodes represent fragments and edges correspond to alignments. We assign weights to the edges by evaluating the alignments using a set of inter-fragment constraints which take into account shape- and content-based information. Finally, we use an iterative algorithm that chooses the edge having the highest weight during each iteration. However, since selecting edges corresponds to combining groups of fragments and thus provides new evidence, we reevaluate the edge weights after each iteration. We quantitatively evaluate the effectiveness of our approach by conducting experiments on a novel dataset. It comprises a total of 120 pages taken from two magazines which have been shredded and annotated manually. We thus provide the means for a quantitative evaluation of assembly algorithms which, to the best of our knowledge, has not been done before.

关键词： Annotated dataset document assembly graph algorithm supervised learning

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for testing goal-minimality of graphs

引用

DISCRETE APPLIED MATHEMATICS 2013年第10-11期161卷 1632-1634页

作者： Gyuerki, Stefan Mazak, Jan Slovak Univ Technol Bratislava Fac Chem & Food Technol Bratislava 81237 Slovakia Trnava Univ Trnava Fac Educ Trnava 91843 Slovakia

An undirected graph G with diameter k is said to be goal-minimally k-diametric if for every edge uv of G the distance d(G-uv)(x, y) > k if and only if {x, y} = {u, v}. We describe an efficient algorithm for determining whether a given graph is goal-minimally k-diametric or not. In addition, we illustrate the use of the algorithm on a large graph with diameter 26. (C) 2013 Elsevier B.V. All rights reserved.

关键词： graph algorithm Distance Diameter Edge-critical

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Network-Based Interpretation of Genomic Variation Data

引用

JOURNAL OF MOLECULAR BIOLOGY 2013年第21期425卷 3964-3969页

作者： Halldorsson, Bjarni V. Sharan, Roded Reykjavik Univ IS-101 Reykjavik Iceland Tel Aviv Univ IL-69978 Tel Aviv Israel

Advances in sequencing technologies are allowing genome-wide association studies at an ever-growing scale. The interpretation of these studies requires dealing with statistical and combinatorial challenges, owing to the multi-factorial nature of human diseases and the huge space of genomic markers that are being monitored. Recently, it was proposed that using protein protein interaction network information could help in tackling these challenges by restricting attention to markers or combinations of markers that map to close proteins in the network. In this review, we survey techniques for integrating genomic variation data with network information to improve our understanding of complex diseases and reveal meaningful associations. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： copy number variation (CNV) disease association expression quantitative trait loci (eQTLs) genome-wide association studies (GWAS) graph algorithm molecular pathway protein–protein interaction single-nucleotide polymorphism single-nucleotide polymorphism (SNP)

来源：评论

学校读者我要写书评

暂无评论

An Early Evaluation of the Scalability of graph algorithms on the Intel MIC Architecture

An Early Evaluation of the Scalability of Graph Algorithms o...

引用

26th IEEE International Parallel and Distributed Processing Symposium (IPDPS) / Workshop on High Performance Data Intensive Computing

作者： Saule, Erik Catalyuerek, Uemit V. Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA

ISBN: (纸本)9780769546766

graph algorithms are notorious for not getting good speedup on parallel architectures. These algorithms tend to suffer from irregular dependencies and a high synchronization cost that prevent an efficient execution on distributed memory machines. Hence such algorithms are mostly parallelized on shared memory machines. However, current commodity shared memory machines do not typically offer enough parallelism to process these problems. In this paper, we are presenting an early investigation of the scalability of such algorithms on Intel's upcoming Many Integrated Core (Intel MIC) architecture which, when it will be released in 2012, is expected to provide more than 50 physical cores with SMT capability. The Intel MIC architecture can be programmed through many programming models, here we investigate the three most popular of these models namely OpenMP, Cilk Plus and Intel's TBB. We present scalability results of a parallel graph coloring algorithm, three variations of a breadth-first search algorithm and a microbenchmark for irregular computations using these three programming models. Our results on a prototype board show that the multi-threaded architecture of Intel MIC can be effectively used for hiding latencies in irregular applications to achieve almost perfect speedup.

关键词： graph algorithm unstructured irregular computation scalability multi-threaded architectures graph coloring breadth-first search

来源：评论

学校读者我要写书评

暂无评论

Finding and listing induced paths and cycles

引用

DISCRETE APPLIED MATHEMATICS 2013年第4-5期161卷 633-641页

作者： Hoang, Chinh T. Kaminski, Marcin Sawada, Joe Sritharan, R. Wilfrid Laurier Univ Waterloo ON N2L 3C5 Canada Univ Libre Bruxelles Dept Informat Algorithms Res Grp B-1050 Brussels Belgium Univ Guelph Sch Comp Sci Guelph ON N1G 2W1 Canada Univ Dayton Dept Comp Sci Dayton OH 45469 USA

Many recognition problems for special classes of graphs and cycles can be reduced to finding and listing induced paths and cycles in a graph. We design algorithms to list all P-3's in O(m(1.5) + p(3)(G)) time, and for k >= 4 all P-k's in O(n(k-1) + p(k)(G) + k.c(k)(G)) time, where p(k)(G), respectively, c(k)(G), are the number of P-k's, respectively, C-k's, of a graph G. We also provide an algorithm to find a P-k, k >= 5, in time O(k!! . m((k-1)/2)) if k is odd, and O(k!! . nm((k/2)-1)) if k is even. As applications of our findings, we give algorithms to recognize quasi-triangulated graphs and brittle graphs. Our algorithms' time bounds are incomparable with previously known algorithms. (C) 2012 Elsevier B.V. All rights reserved.

关键词： graph algorithm Induced path Induced cycle

来源：评论

学校读者我要写书评

暂无评论

Approximating the k-Splittable Capacitated Network Design Problem

Approximating the k-Splittable Capacitated Network Design Pr...

引用

39th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Morsy, Ehab Nanyang Technol Univ Div Math Sci Singapore 637371 Singapore Suez Canal Univ Dept Math Ismailia 22541 Egypt

ISBN: (纸本)9783642358432

We consider the k-splittable capacitated network design problem (kSCND) in a graph G = (V, E) with edge weight w(e) >= 0, e is an element of E. We are given a vertex s is an element of V designated as a sink, a cable capacity lambda > 0, and a source set S subset of V with demand q(v) >= 0, v is an element of S. For any edge e is an element of E, we are allowed to install an integer number h(e) of copies of e. The kSCND asks to simultaneously send demand q(v) from each source v is an element of S along at most k paths to the sink s. A set of such paths can pass through a single copy of an edge in G as long as the total demand along the paths does not exceed the cable capacity lambda. The objective is to find a set P of paths of G that minimizes the installing cost Sigma(e is an element of Eh)(e)w(e). In this paper, we propose a ((k + 1)/ k + rho(ST))-approximation algorithm to the kSCND, where rho(ST) is any approximation ratio achievable for the Steiner tree problem.

关键词： approximation algorithm graph algorithm routing problems network optimization

来源：评论

学校读者我要写书评

暂无评论

CONNECTED LIAR'S DOMINATION IN graphS: COMPLEXITY AND algorithmS

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2013年第4期5卷 1350024-1-1350024-16页

作者： Panda, B. S. Paul, S. Indian Inst Technol Delhi Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

A subset L subset of V of a graph G = (V, E) is called a connected liar's dominating set of G if (i) for all v. V, |NG[v] n L| >= 2, ( ii) for every pair u, v is an element of V of distinct vertices, |(N-G[u]. N-G[v]) boolean AND L| >= 3, and ( iii) the induced subgraph of G on L is connected. In this paper, we initiate the algorithmic study of minimum connected liar's domination problem by showing that the corresponding decision version of the problem is NP-complete for general graph. Next we study this problem in subclasses of chordal graphs where we strengthen the NP-completeness of this problem for undirected path graph and prove that this problem is linearly solvable for block graphs. Finally, we propose an approximation algorithm for minimum connected liar's domination problem and investigate its hardness of approximation in general graphs.

关键词： Domination liar's domination chordal graph graph algorithm NP-completeness approximation algorithm APX-completeness

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：