Kao / Li Algorithmic Aspects in Information and Management

Third International Conference, AAIM 2007, Portland, OR, USA, June 6-8, 2007, Proceedings
2007
ISBN: 978-3-540-72870-2
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 441 Seiten

Reihe: Information Systems and Applications, incl. Internet/Web, and HCI

This book constitutes the refereed proceedings of the Third International Conference on Algorithmic Aspects in Information and Management, AAIM 2007, held in Portland, OR, USA in June 2007.

The 39 revised full papers presented together with abstracts of three invited talks were carefully reviewed and selected from 120 submissions. The papers are organized in topical sections on graph algorithms, combinatorics, scheduling, graph theory, network algorithms, game theory, option theory, computational geometry, graph theory and combinatorics, as well as networks and data.

Written for: Researchers and professionals

Keywords: QoS, Web services, algorithmic mathematics, algorithmics, algorithms, approximation, combinatorial optimization, complexity, computational graph theory, equilibrium computation, game theory, graph theory, heuristics, network algorithms, plane triangulation, randomized algorithms, scheduling.

Autoren/Hrsg.

Kao, Ming-Yang

Li, Xiang-Yang

Inhaltsverzeichnis

1;Title page;2
2;Preface;6
3;Organization;8
4;Table of Contents;10
5;Solving Generalized Maximum Dispersion withLinear Programming;14
6;Significance-Driven Graph Clustering;24
7;An Improved Approximation Algorithm forMaximum Edge 2-Coloring in Simple Graphs;40
8;Digraph Strong Searching: Monotonicity andComplexity;50
9;Algorithms for Counting 2-Sat Solutions andColorings with Applications;60
10;Collaborative Ranking: An AggregationAlgorithm for Individuals’ PreferenceEstimation;71
11;A Compact Encoding of Rectangular Drawingswith Efficient Query Supports;81
12;A New Efficient Algorithm for Computing theLongest Common Subsequence;95
13;Scheduling a Flexible Batching Machine;104
14;Global Search Method for Parallel Machine Scheduling;113
15;Releasing and Scheduling of Lots in a Wafer Fab;121
16;Mixed Criteria Packet Scheduling;133
17;Efficient Algorithms for k-Disjoint PathsProblems on DAGs;147
18;Acyclic Edge Colouring of Outerplanar Graphs;157
19;Smallest Bipartite Bridge-ConnectivityAugmentation (Extended Abstract);166
20;Approximation Algorithms forthe Graph Orientation Minimizingthe Maximum Weighted Outdegree;180
21;An Efficient Algorithm for the EvacuationProblem in a Certain Class of a Network withUniform Path-Lengths;191
22;Online OVSF Code Assignment with ResourceAugmentation;204
23;Optimal Joint Rate and Power Allocation inCDMA Networks;214
24;Suppressing Maximum Burst Size Throughoutthe Path with Non-work Conserving Schedulers;224
25;How to Play the Majority Game with Liars;234
26;On Satisfiability Games and the Power ofCongestion Games;244
27;The Complexity of Algorithms ComputingGame Trees on Random Assignments;254
28;An Efficient, and Fast Convergent Algorithm forBarrier Options;264
29;An Ingenious, Piecewise Linear InterpolationAlgorithm for Pricing Arithmetic AverageOptions;275
30;Optimal Order Allocation with Discount Pricing;286
31;Convex Hulls of Point-Sets and Non-uniformHypergraphs;298
32;Optimal st-Orientations for Plane Triangulations;309
33;Minimum Spanning Tree with Neighborhoods;319
34;An Almost Linear Time 2.8334-ApproximationAlgorithm for the Disc Covering Problem;330
35;Optimal Field Splitting with Feathering inIntensity-Modulated Radiation Therapy;340
36;Approximating the Maximum Independent Setand Minimum Vertex Coloring on Box Graphs;350
37;BMA*: An Efficient Algorithm for theOne-to-Some Shortest Path Problem on RoadMaps;359
38;Strip Packing vs. Bin Packing;371
39;Probe Matrix Problems:Totally Balanced Matrices;381
40;Efficiency of Data Distributionin BitTorrent-Like Systems;391
41;Design of a Fuzzy PI Controller to GuaranteeProportional Delay Differentiation on WebServers;402
42;Improved Approximation Algorithms for PredictingRNA Secondary Structures with Arbitrary Pseudoknots;412
43;A Heuristic Method forSelecting Support Features from Large Datasets;424
44;Author Index;440

Leseproben

Significance-Driven Graph Clustering (p. 11-12)

Marco Gaertler, Robert G¨orke, and Dorothea Wagner
Faculty of Informatics, Universit¨at Karlsruhe (TH)

Abstract. Modularity, the recently defined quality measure for clusterings, has attained instant popularity in the fields of social and natural sciences. We revisit the rationale behind the definition of modularity and explore the founding paradigm. This paradigm is based on the trade-off between the achieved quality and the expected quality of a clustering with respect to networks with similar intrinsic structure. We experimentally evaluate realizations of this paradigm systematically, including modularity, and describe efficient algorithms for their optimization. We confirm the feasibility of the resulting generality by a first systematic analysis of the behavior of these realizations on both artificial and on real-world data, arriving at remarkably good results of community detection.

1 Introduction

Discovering natural groups and large scale inhomogeneities is a crucial task in the exploration and analysis of large and complex networks. This task is usually realized with clustering methods. The majority of algorithms for graph clustering are based on the paradigm of intra-cluster density versus inter-cluster sparsity. Several formalizations have been proposed and evaluated, an overview of such techniques is given in [1]. Recently, Girvan and Newman [2] proposed the objective function modularity, which indirectly incorporates this paradigm. Modularity evaluates a clustering based on the fraction of intra-cluster edges compared to the expected value of this number. Modularity was .rst introduced as a quality measure of a clustering, however, a simple greedy algorithm, solely based on modularity, has been proposed shortly after by Newman [3]. The definition of modularity and this algorithm evoked a surge of interest, yielding many studies concerning different applications, such as protein interaction dependencies, recommendation systems or social network analysis, and possible adjustments (see e.g. [4,5,6,7]). Moreover, a range of alternative algorithmic approaches has been proposed, based on a greedy agglomeration [8,9], on spectral division [10,11], simulated annealing [12,13] and extremal optimization [14]. Recently, it has been proven, that it is NP-hard to optimize modularity [15], which justi.es the need for heuristics and approximations. Note that little is known on the approximability of modularity.

However, to our knowledge, no systematic evaluation of modularity-based clustering has been performed, yet. In this work, we conduct such an evaluation and, additionally, we advance towards a profound understanding of the rationales modularity is based upon. We formally state and investigate the generalized founding paradigm for the signi.cance of a clustering as the trade-off between the achieved quality and the expected quality for random networks incorporating the intrinsic properties of the original network. We experimentally evaluate realizations of this paradigm (including modularity itself) and extensively evaluate algorithms that each optimize a realization, followed by a partial discussion of their behavior. Furthermore, we present an algorithm that efficiently optimizes the particularly promising realization relative performance signi.cance in O(n2 log n) time. We compare the performance of these algorithms in terms of clustering quality to that of other clustering algorithms, on a set of random pre-clustered graphs and complement our findings with results on real data. Our results indicate the feasibility of the paradigm in that, on the whole, our algorithms surpass the benchmark algorithms, and in that the generality of the approach is justified by specific realizations excelling on real-world data.

This paper is organized as follows: After introducing the necessary preliminaries for graph clustering and some quality measures (Sec. 2), we give the formal definition of our significance paradigm and present some realizations (Sec. 3). Section 4 scrutinizes the greedy algorithms which are employed to obtain clusterings with high signi.cance score, including an e.cient implementation for a quick divisive merge. The setup and the results of the experimental evaluation are described in Section 5 which are followed by a conclusion.