Hirsch M.J., Pardalos P.M., Murphey R. Dynamics of Information Systems: Theory and Applications

Подождите немного. Документ загружается.

DYNAMICS OF INFORMATION SYSTEMS

Springer Optimization and Its Applications

VOLUME 40

Managing Editor

Panos M. Pardalos (University of Florida)

Editor–Combinatorial Optimization

Ding-Zhu Du (University of Texas at Dallas)

Advisory Board

J. Birge (University of Chicago)

C.A. Floudas (Princeton University)

F. Giannessi (University of Pisa)

H.D. Sherali (Virginia Polytechnic and State University)

T. Terlaky (McMaster University)

Y. Ye (Stanford University)

Aims and Scope

Optimization has been expanding in all directions at an astonishing rate dur-

ing the last few decades. New algorithmic and theoretical techniques have

been developed, the diffusion into other disciplines has proceeded at a rapid

pace, and our knowledge of all aspects of the ﬁeld has grown even more

profound. At the same time, one of the most striking trends in optimization

is the constantly increasing emphasis on the interdisciplinary nature of the

ﬁeld. Optimization has been a basic tool in all areas of applied mathematics,

engineering, medicine, economics and other sciences.

The series Springer Optimization and Its Applications publishes under-

graduate and graduate textbooks, monographs and state-of-the-art exposi-

tory works that focus on algorithms for solving optimization problems and

also study applications involving such problems. Some of the topics cov-

ered include nonlinear optimization (convex and nonconvex), network ﬂow

problems, stochastic optimization, optimal control, discrete optimization,

multi-objective programming, description of software packages, approxima-

tion techniques and heuristic approaches.

DYNAMICS OF INFORMATION SYSTEMS

Theory and Applications

Edited By

MICHAEL J. HIRSCH

Raytheon, Inc.

Orlando, Florida, USA

PANOS M. PARDALOS

University of Florida

Department of Industrial and Systems Engineering

Gainesville, Florida, USA

ROBERT MURPHEY

Air Force Research Laboratory

Munitions Directorate

Eglin AFB, Florida, USA

Editors

Michael J. Hirsch

Raytheon, Inc.

3323 Pelham Road

Orlando, Florida, 32803

USA

mjh8787@uﬂ.edu

Panos M. Pardalos

University of Florida

Department of Industrial

& Systems Engineering

303 Weil Hall

Gainesville, Florida, 32611-6595

USA

pardalos@ise.uﬂ.edu

Robert Murphey

Air Force Research Laboratory

Munitions Directorate

101 W. Eglin Boulevard

Eglin AFB, Florida, 32542

USA

murphey@eglin.af.mil

ISSN 1931-6828

ISBN 978-1-4419-5688-0 e-ISBN 978-1-4419-5689-7

DOI 10.1007/978-1-4419-5689-7

Springer New York Dordrecht Heidelberg London

Library of Congress Control Number: 2010925362

Mathematics Subject Classiﬁcation (2010): 37D40, 65Kxx, 68U35, 68Txx

permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York,

NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in

connection with any form of information storage and retrieval, electronic adaptation, computer software,

or by similar or dissimilar methodology now known or hereafter developed is forbidden.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are

not identiﬁed as such, is not to be taken as an expression of opinion as to whether or not they are subject

to proprietary rights.

Cover illustration: “Temple of Poseidon at Cape Sounion, circa 440 BC”. Photo taken by Elias Tyligadas.

Printed on acid-free paper

Springer is part of Springer Science+Business Media (www.springer.com)

Preface

Dynamics of Information plays an increasingly critical role in our society. Networks

affect our lives every day. The inﬂuence of information on social, biological, ge-

netic, and military systems must be better understood to achieve large advances in

the capability and understanding of these systems. Applications are wide-spread and

include: the detection of terrorist networks, the design of highly functioning busi-

nesses and computer networks, modeling the distributed sensory and control physi-

ology of animals, quantum entanglement, genome modeling, multi-robotic systems,

and industrial and manufacturing safety.

Classical Information Theory is built upon the notion of entropy which states

that for a message to contain information it must dispel uncertainty associated with

the knowledge of some object or process. Hence, large uncertainty means more in-

formation, small uncertainty means less information. For a networked system, clas-

sical information theory describes information that is both joint and time varying.

However, for networked systems, information theory can be of limited value. It is

cumbersome if not confusing to deﬁne joint and conditional information in even

relatively small (Bayesian) networks. The curse of dimensionality is one large fac-

tor. So is causality, which is functionally critical to determine yet often difﬁcult

to ascertain. Entropy does not attend to the value or inﬂuence of information, even

though in a network, some information, though potentially large in its entropy, could

have little value or inﬂuence on the rest of the network, while another, less entropic,

piece of information may have a great deal of inﬂuence on the rest of the system.

How information ﬂows and is modiﬁed through a system is not dependent upon en-

tropy but more likely on how potentially useful the information is. How the value of

information is linked to the connectedness of the network (and vice versa) is criti-

cal to analyzing and designing high performing distributed systems, yet is not well

studied.

This book presents the state of the art concerning how information, usually in the

form of sensing and control, inﬂuences the evolution of a distributed or networked

system. Fundamentally, this deals with the potential inﬂuence information has on the

system and how that information ﬂows through a system and is modiﬁed in time and

space. The chapters in this book relate to concepts that increase knowledge of the

relational aspects of information as opposed to the entropic content of information.

vi Preface

We gratefully acknowledge the ﬁnancial support of the Air Force Research Lab-

oratory and The Center for Applied Optimization at The University of Florida. We

thank the contributing authors, the anonymous referees, and Springer Publishing for

making the publication of this book possible.

Michael J. Hirsch

Panos M. Pardalos

Robert Murphey

Contents

Preface ..................................... v

1 The Role of Dynamics in Extracting Information Sparsely Encoded

in High Dimensional Data Streams ................... 1

Mario Sznaier, Octavia Camps, Necmiye Ozay, Tao Ding,

Gilead Tadmor, and Dana Brooks

1.1 Introduction ............................. 1

1.2 Key Subproblems Arising in the Context of Dynamic Information

Extraction .............................. 2

1.3 Nonlinear Embedding of Dynamic Data ............... 5

1.4 Structure Extraction from High Dimensional Data Streams ..... 7

1.5 Robust Dynamic Data Segmentation ................ 10

1.5.1 Example1:VideoSegmentation .............. 13

1.5.2 Example 2: Segmentation of Dynamic Textures ...... 15

1.6 Constrained Interpolation of High Dimensional Signals ...... 17

1.7 Hypothesis Testing and Data Sharing ................ 20

1.8 Conclusions ............................. 25

References . ............................. 25

2 Information Trajectory of Optimal Learning ............. 29

Roman V. Belavkin

2.1 Introduction ............................. 29

2.2 Topology and Geometry of Learning Systems . . ......... 32

2.2.1 Problem Statement and Basic Concepts . . ......... 32

2.2.2 Asymmetric Topologies and Gauge Functions ....... 34

2.2.3 Trajectories Continuous in Information . . ......... 35

2.3 Optimal Evolution and Bounds ................... 37

2.4 Empirical Evaluation on Learning Agents .............. 40

2.5 Conclusion . ............................. 43

References . ............................. 44

vii

viii Contents

3 Performance-Information Analysis and Distributed Feedback

Stabilization in Large-Scale Interconnected Systems ......... 45

Khanh D. Pham

3.1 Introduction ............................. 45

3.2 ProblemFormulation ........................ 48

3.3 Performance-Information Analysis ................. 52

3.4 ProblemStatements ......................... 62

3.5 Distributed Risk-Averse Feedback Stabilization . ......... 74

3.6 Conclusions ............................. 80

References . ............................. 81

4 A General Approach for Modules Identiﬁcation in Evolving Networks 83

Thang N. Dinh, Incheol Shin, Nhi K. Thai, My T. Thai, and Taieb Znati

4.1 Introduction ............................. 84

4.2 Preliminaries and Problem Deﬁnition ................ 85

4.2.1 Preliminaries......................... 85

4.2.2 Problem Deﬁnition . . . ................... 86

4.3 Compact Representation of a Network ............... 86

4.3.1 StructurePreservation.................... 88

4.3.2 Size of the Compact Representation ............. 91

4.4 Partition Based on Evolution History ................ 92

4.4.1 Algorithm .......................... 93

4.4.2 Complexity ......................... 95

4.5 Experimental Evaluation . . . ................... 96

4.6 Conclusions ............................. 99

References . ............................. 99

5 Topology Information Control in Feedback Based Reconﬁguration

Processes .................................101

Alexandru Murgu, Ian Postlethwaite, Dawei Gu, and Chris Edwards

5.1 Introduction and Motivation . . ...................101

5.2 GroupCommunicationNetworking.................103

5.3 Reconﬁguration Process Optimization ...............108

5.3.1 Topology Information Model ................108

5.3.2 InformationControlProblem ................111

5.4 Topology Information Control . ...................113

5.4.1 Lagrangian Solution . . ...................113

5.4.2 DistributedImplementation .................116

5.4.3 Summary of Computational Results .............120

5.5 Concluding Remarks .........................122

References . .............................123

6 Effect of Network Geometry and Interference on Consensus

in Wireless Networks ...........................125

Sundaram Vanka, Vijay Gupta, and Martin Haenggi

6.1 Introduction .............................125

Contents ix

6.2 ProblemFormulation ........................126

6.3 AnalysisofaRinganda2DTorus .................129

6.3.1 The 1-D Case: Nodes on a Ring ...............129

6.3.2 Nodes on a Two-Dimensional Torus .............132

6.4 HierarchicalNetworks........................138

6.5 Conclusions .............................141

References . .............................142

7 Analyzing the Theoretical Performance of Information Sharing ...145

Paul Scerri, Prasanna Velagapudi, and Katia Sycara

7.1 Introduction .............................145

7.2 Information Sharing .........................147

7.2.1 TokenAlgorithms ......................148

7.3 Experimental Results ........................149

7.3.1 Optimality of the Lookahead Policy .............150

7.3.2 Optimality of the Random Policies .............151

7.3.3 EffectsofNoisyEstimation.................152

7.3.4 Properties Affecting Optimality ...............154

7.3.5 ScalingNetworkSize ....................156

7.4 RelatedWork ............................161

7.5 Conclusions and Future Work . ...................162

References . .............................163

8 Self-Organized Criticality of Belief Propagation in Large

Heterogeneous Teams ..........................165

Robin Glinton, Praveen Paruchuri, Paul Scerri, and Katia Sycara

8.1 Introduction .............................165

8.2 Self-Organized Criticality . . . ...................167

8.3 Belief Sharing Model ........................168

8.4 SystemOperationRegimes .....................169

8.5 SimulationResults..........................170

8.6 RelatedWork ............................181

8.7 Conclusions and Future Work . ...................182

References . .............................182

9 Effect of Humans on Belief Propagation in Large Heterogeneous

Teams ...................................183

Praveen Paruchuri, Robin Glinton, Katia Sycara, and Paul Scerri

9.1 Introduction .............................183

9.2 Self-OrganizedCriticalSystems...................185

9.3 The Enabler-Impeder Effect . . ...................185

9.4 Model of Information Dissemination in a Network .........186

9.5 SimulationResults..........................187

9.6 RelatedWork ............................194

9.7 Conclusions and Future Work . ...................195

References . .............................195