Mathew Penrose
- Published in print:
- 2003
- Published Online:
- September 2007
- ISBN:
- 9780198506263
- eISBN:
- 9780191707858
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198506263.003.0001
- Subject:
- Mathematics, Probability / Statistics
This introductory chapter contains a general discussion of both the historical and the applied background behind the study of random geometric graphs. A brief overview is presented, along with some ...
More
This introductory chapter contains a general discussion of both the historical and the applied background behind the study of random geometric graphs. A brief overview is presented, along with some standard definitions in graph theory and probability theory. Specific terminology is introduced for two limiting regimes in the choice of r=r(n) (namely the thermodynamic limit where the mean vertex degree is made to approach a finite constant) and the connectivity regime (where it grows logarithmically with n). Some elementary probabilistic results are given on large deviations for the binomial and Poisson distribution, and on Poisson point processes.Less
This introductory chapter contains a general discussion of both the historical and the applied background behind the study of random geometric graphs. A brief overview is presented, along with some standard definitions in graph theory and probability theory. Specific terminology is introduced for two limiting regimes in the choice of r=r(n) (namely the thermodynamic limit where the mean vertex degree is made to approach a finite constant) and the connectivity regime (where it grows logarithmically with n). Some elementary probabilistic results are given on large deviations for the binomial and Poisson distribution, and on Poisson point processes.
Yannis M. Ioannides
- Published in print:
- 2012
- Published Online:
- October 2017
- ISBN:
- 9780691126852
- eISBN:
- 9781400845385
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691126852.003.0002
- Subject:
- Economics and Finance, Development, Growth, and Environmental
This chapter discusses the theory and empirics of social interactions, with particular emphasis on the role of social context in individual decisions. It begins by introducing a sequence of models ...
More
This chapter discusses the theory and empirics of social interactions, with particular emphasis on the role of social context in individual decisions. It begins by introducing a sequence of models that highlight applications in different empirical social interaction settings, including a simple static model that is used to link social interactions theory with social networks theory, notably random graph theory. A dynamic model, where the social structure accommodates a variety of social interaction motives, is then described and solved as a dynamic system of evolving individual actions. The solution links social interactions theory with spatial econometrics. The chapter examines the econometrics of social interactions in social networks and social learning in urban settings before concluding with a review of the literature on social interactions in economics.Less
This chapter discusses the theory and empirics of social interactions, with particular emphasis on the role of social context in individual decisions. It begins by introducing a sequence of models that highlight applications in different empirical social interaction settings, including a simple static model that is used to link social interactions theory with social networks theory, notably random graph theory. A dynamic model, where the social structure accommodates a variety of social interaction motives, is then described and solved as a dynamic system of evolving individual actions. The solution links social interactions theory with spatial econometrics. The chapter examines the econometrics of social interactions in social networks and social learning in urban settings before concluding with a review of the literature on social interactions in economics.
Rolf Niedermeier
- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198566076
- eISBN:
- 9780191713910
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566076.003.0011
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter surveys further important techniques for designing fixed-parameter algorithms. These include color-coding, integer linear programming, iterative compression, greedy localization, and ...
More
This chapter surveys further important techniques for designing fixed-parameter algorithms. These include color-coding, integer linear programming, iterative compression, greedy localization, and graph minor theory. The practical relevance of each technique is also evaluated. From a practical point of view, the two most important techniques are colour-coding and iterative compression.Less
This chapter surveys further important techniques for designing fixed-parameter algorithms. These include color-coding, integer linear programming, iterative compression, greedy localization, and graph minor theory. The practical relevance of each technique is also evaluated. From a practical point of view, the two most important techniques are colour-coding and iterative compression.
Roger D. Roger and Miles A. Whittington
- Published in print:
- 2010
- Published Online:
- May 2010
- ISBN:
- 9780195342796
- eISBN:
- 9780199776276
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780195342796.003.0010
- Subject:
- Neuroscience, Molecular and Cellular Systems, Development
VFO occurs in in vitro models when chemical receptors are blocked. In particular, VFO does not require GABAA receptors, even though interneurons fire at high rates during in vivo very fast ...
More
VFO occurs in in vitro models when chemical receptors are blocked. In particular, VFO does not require GABAA receptors, even though interneurons fire at high rates during in vivo very fast oscillations. VFO can be accounted for by a model in which neuronal spiking percolates through a sparse network of electrically coupled axons. This model predicts that VFO frequency depends on gap junction conductance, mediated by an effect on crossing time (i.e. the time it takes for a spike in one axon to elicit a spike in a coupled axon, estimated to be of order 0.2 ms). VFO in cerebellar slices also depends on gap junctions, but the physical principles are slightly different: cerebellar VFO appears to depend on many:one propagation of spiking, in effect a form of axonal coincidence detection.Less
VFO occurs in in vitro models when chemical receptors are blocked. In particular, VFO does not require GABAA receptors, even though interneurons fire at high rates during in vivo very fast oscillations. VFO can be accounted for by a model in which neuronal spiking percolates through a sparse network of electrically coupled axons. This model predicts that VFO frequency depends on gap junction conductance, mediated by an effect on crossing time (i.e. the time it takes for a spike in one axon to elicit a spike in a coupled axon, estimated to be of order 0.2 ms). VFO in cerebellar slices also depends on gap junctions, but the physical principles are slightly different: cerebellar VFO appears to depend on many:one propagation of spiking, in effect a form of axonal coincidence detection.
Andrew Goodall
- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0007
- Subject:
- Mathematics, Probability / Statistics
This article reviews basic techniques of Fourier analysis on a finite abelian group Q, with subsequent applications in graph theory. These include evaluations of the Tutte polynomial of a graph G in ...
More
This article reviews basic techniques of Fourier analysis on a finite abelian group Q, with subsequent applications in graph theory. These include evaluations of the Tutte polynomial of a graph G in terms of cosets of the Q-flows of G. Other applications to spanning trees of Cayley graphs and to group-valued models on phylogenetic trees are also presented to illustrate methods.Less
This article reviews basic techniques of Fourier analysis on a finite abelian group Q, with subsequent applications in graph theory. These include evaluations of the Tutte polynomial of a graph G in terms of cosets of the Q-flows of G. Other applications to spanning trees of Cayley graphs and to group-valued models on phylogenetic trees are also presented to illustrate methods.
Alexander Bird
- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780199227013
- eISBN:
- 9780191711121
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199227013.003.0006
- Subject:
- Philosophy, Metaphysics/Epistemology
It is often claimed (e.g., by Swinburne, Armstrong, and Lowe) that the view that all natural properties are potencies leads to a vicious regress or circularity. The possible interpretations of this ...
More
It is often claimed (e.g., by Swinburne, Armstrong, and Lowe) that the view that all natural properties are potencies leads to a vicious regress or circularity. The possible interpretations of this argument are examined, and the most pressing is that the regress leaves the identity of potencies indeterminate. This argument is equivalent to the claim that when the network of properties is represented as a graph, that graph has non-trivial automorphisms. It is shown that a graph can suitably represent the network of essentially dispositional properties while having no non-trivial automorphisms; and so the identity of each member of a set of potencies can supervene solely on the structure of relations among those potencies.Less
It is often claimed (e.g., by Swinburne, Armstrong, and Lowe) that the view that all natural properties are potencies leads to a vicious regress or circularity. The possible interpretations of this argument are examined, and the most pressing is that the regress leaves the identity of potencies indeterminate. This argument is equivalent to the claim that when the network of properties is represented as a graph, that graph has non-trivial automorphisms. It is shown that a graph can suitably represent the network of essentially dispositional properties while having no non-trivial automorphisms; and so the identity of each member of a set of potencies can supervene solely on the structure of relations among those potencies.
Mark Newman
- Published in print:
- 2010
- Published Online:
- September 2010
- ISBN:
- 9780199206650
- eISBN:
- 9780191594175
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199206650.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
The scientific study of networks, including computer networks, social networks, and biological networks, has received an enormous amount of interest in the last few years. The rise of the Internet ...
More
The scientific study of networks, including computer networks, social networks, and biological networks, has received an enormous amount of interest in the last few years. The rise of the Internet and the wide availability of inexpensive computers have made it possible to gather and analyze network data on a large scale, and the development of a variety of new theoretical tools has allowed us to extract new knowledge from many different kinds of networks. The study of networks is broadly interdisciplinary and important developments have occurred in many fields, including mathematics, physics, computer and information sciences, biology, and the social sciences. This book brings together the most important breakthroughs in each of these fields and presents them in a coherent fashion, highlighting the strong interconnections between work in different areas. Subjects covered include the measurement and structure of networks in many branches of science, methods for analyzing network data, including methods developed in physics, statistics, and sociology, the fundamentals of graph theory, computer algorithms, and spectral methods, mathematical models of networks, including random graph models and generative models, and theories of dynamical processes taking place on networks.Less
The scientific study of networks, including computer networks, social networks, and biological networks, has received an enormous amount of interest in the last few years. The rise of the Internet and the wide availability of inexpensive computers have made it possible to gather and analyze network data on a large scale, and the development of a variety of new theoretical tools has allowed us to extract new knowledge from many different kinds of networks. The study of networks is broadly interdisciplinary and important developments have occurred in many fields, including mathematics, physics, computer and information sciences, biology, and the social sciences. This book brings together the most important breakthroughs in each of these fields and presents them in a coherent fashion, highlighting the strong interconnections between work in different areas. Subjects covered include the measurement and structure of networks in many branches of science, methods for analyzing network data, including methods developed in physics, statistics, and sociology, the fundamentals of graph theory, computer algorithms, and spectral methods, mathematical models of networks, including random graph models and generative models, and theories of dynamical processes taking place on networks.
Sergey N. Dorogovtsev
- Published in print:
- 2010
- Published Online:
- May 2010
- ISBN:
- 9780199548927
- eISBN:
- 9780191720574
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199548927.003.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter introduces the basic notions of graph theory and discusses the starting point of network science, namely the Konigsberg bridge problem. A few examples of different graphs, lattices, and ...
More
This chapter introduces the basic notions of graph theory and discusses the starting point of network science, namely the Konigsberg bridge problem. A few examples of different graphs, lattices, and fractals are considered. These are used to explain the notions of a node degree, the shortest path length, clustering and so on. Milgram's experiment is also considered, and the notion of a random network is explained. A fundamental difference between small worlds and lattices and fractals, is discussed.Less
This chapter introduces the basic notions of graph theory and discusses the starting point of network science, namely the Konigsberg bridge problem. A few examples of different graphs, lattices, and fractals are considered. These are used to explain the notions of a node degree, the shortest path length, clustering and so on. Milgram's experiment is also considered, and the notion of a random network is explained. A fundamental difference between small worlds and lattices and fractals, is discussed.
M. E. J. Newman
- Published in print:
- 2010
- Published Online:
- September 2010
- ISBN:
- 9780199206650
- eISBN:
- 9780191594175
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199206650.003.0006
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter introduces the basic theoretical tools used to describe and analyze networks, most of which come from graph theory, the branch of mathematics that deals with networks. Topics covered ...
More
This chapter introduces the basic theoretical tools used to describe and analyze networks, most of which come from graph theory, the branch of mathematics that deals with networks. Topics covered include the adjacency matrix, weighted networks, directed networks, hypergraphs, bipartite networks, trees, planar networks, the graph Laplacian, and random walks. Exercises are provided at the end of the chapter.Less
This chapter introduces the basic theoretical tools used to describe and analyze networks, most of which come from graph theory, the branch of mathematics that deals with networks. Topics covered include the adjacency matrix, weighted networks, directed networks, hypergraphs, bipartite networks, trees, planar networks, the graph Laplacian, and random walks. Exercises are provided at the end of the chapter.
Arthur Benjamin, Gary Chartrand, and Ping Zhang
- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691175638
- eISBN:
- 9781400852000
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691175638.003.0013
- Subject:
- Mathematics, Applied Mathematics
This book concludes with an epilogue, which traces the evolution of graph theory, from the conceptualization of the Königsberg Bridge Problem and its generalization by Leonhard Euler, whose solution ...
More
This book concludes with an epilogue, which traces the evolution of graph theory, from the conceptualization of the Königsberg Bridge Problem and its generalization by Leonhard Euler, whose solution led to the subject of Eulerian graphs, to the various efforts to solve the Four Color Problem. It considers elements of graph theory found in games and puzzles of the past, and the famous mathematicians involved including Sir William Rowan Hamilton and William Tutte. It also discusses the remarkable increase since the 1960s in the number of mathematicians worldwide devoted to graph theory, along with research journals, books, and monographs that have graph theory as a subject. Finally, it looks at the growth in applications of graph theory dealing with communication and social networks and the Internet in the digital age and the age of technology.Less
This book concludes with an epilogue, which traces the evolution of graph theory, from the conceptualization of the Königsberg Bridge Problem and its generalization by Leonhard Euler, whose solution led to the subject of Eulerian graphs, to the various efforts to solve the Four Color Problem. It considers elements of graph theory found in games and puzzles of the past, and the famous mathematicians involved including Sir William Rowan Hamilton and William Tutte. It also discusses the remarkable increase since the 1960s in the number of mathematicians worldwide devoted to graph theory, along with research journals, books, and monographs that have graph theory as a subject. Finally, it looks at the growth in applications of graph theory dealing with communication and social networks and the Internet in the digital age and the age of technology.
Kevin D. Hoover, Selva Demiralp, and Stephen J. Perez
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780199237197
- eISBN:
- 9780191717314
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199237197.003.0002
- Subject:
- Economics and Finance, Econometrics
The M2 monetary aggregate is monitored by the Federal Reserve, using a broad brush theoretical analysis and an informal empirical analysis. This chapter illustrates empirical identification of an ...
More
The M2 monetary aggregate is monitored by the Federal Reserve, using a broad brush theoretical analysis and an informal empirical analysis. This chapter illustrates empirical identification of an eleven-variable system, in which M2 and the factors that the Fed regards as causes and effects are captured in a vector autoregression. Taking account of cointegration, the methodology combines recent developments in graph-theoretical causal search algorithms with a general-to-specific search algorithm to identify a fully specified structural vector autoregression (SVAR). The SVAR is used to examine the causes and effects of M2 in a variety of ways. The chapter concludes that while the Fed has rightly identified a number of special factors that influence M2 and while M2 detectably affects other important variables, there is 1) little support for the core quantity-theoretic approach to M2 used by the Fed; and 2) M2 is a trivial linkage in the transmission mechanism from monetary policy to real output and inflation.Less
The M2 monetary aggregate is monitored by the Federal Reserve, using a broad brush theoretical analysis and an informal empirical analysis. This chapter illustrates empirical identification of an eleven-variable system, in which M2 and the factors that the Fed regards as causes and effects are captured in a vector autoregression. Taking account of cointegration, the methodology combines recent developments in graph-theoretical causal search algorithms with a general-to-specific search algorithm to identify a fully specified structural vector autoregression (SVAR). The SVAR is used to examine the causes and effects of M2 in a variety of ways. The chapter concludes that while the Fed has rightly identified a number of special factors that influence M2 and while M2 detectably affects other important variables, there is 1) little support for the core quantity-theoretic approach to M2 used by the Fed; and 2) M2 is a trivial linkage in the transmission mechanism from monetary policy to real output and inflation.
J. L. Ramírez Alfonsín
- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198568209
- eISBN:
- 9780191718229
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198568209.003.0001
- Subject:
- Mathematics, Algebra, Combinatorics / Graph Theory / Discrete Mathematics
This chapter is devoted to the computational aspects of the Frobenius number. After discussing a number of methods to solve FP when n = 3 (some of these procedures make use of diverse concepts, such ...
More
This chapter is devoted to the computational aspects of the Frobenius number. After discussing a number of methods to solve FP when n = 3 (some of these procedures make use of diverse concepts, such as the division remainder, continued fractions and maximal lattice free bodies) it presents a variety of algorithms to compute g(a1, . . . , an) for general n. The main ideas of these algorithms are based on concepts from graph theory, index of primitivity of non-negative matrices, and mathematical programming. While the running times of these algorithms are super-polynomial, there exists a method, due to R. Kannan, that solves FP in polynomial time for any fixed n. This method is described, in which the covering radius concept is introduced. The chapter ends by proving that FP is NP-hard under Turing reductions.Less
This chapter is devoted to the computational aspects of the Frobenius number. After discussing a number of methods to solve FP when n = 3 (some of these procedures make use of diverse concepts, such as the division remainder, continued fractions and maximal lattice free bodies) it presents a variety of algorithms to compute g(a1, . . . , an) for general n. The main ideas of these algorithms are based on concepts from graph theory, index of primitivity of non-negative matrices, and mathematical programming. While the running times of these algorithms are super-polynomial, there exists a method, due to R. Kannan, that solves FP in polynomial time for any fixed n. This method is described, in which the covering radius concept is introduced. The chapter ends by proving that FP is NP-hard under Turing reductions.
Guido Caldarelli
- Published in print:
- 2007
- Published Online:
- January 2010
- ISBN:
- 9780199211517
- eISBN:
- 9780191705984
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199211517.003.0002
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This introductory chapter provides the basics of the graph theory used in the book.
This introductory chapter provides the basics of the graph theory used in the book.
Yannis M. Ioannides
- Published in print:
- 2012
- Published Online:
- October 2017
- ISBN:
- 9780691126852
- eISBN:
- 9781400845385
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691126852.003.0010
- Subject:
- Economics and Finance, Development, Growth, and Environmental
This chapter considers the prospect of a deeper understanding of social interactions in urban settings as well as their significance for the functioning and future role of cities and regions. It ...
More
This chapter considers the prospect of a deeper understanding of social interactions in urban settings as well as their significance for the functioning and future role of cities and regions. It introduces broader sets of tools for exploring the properties of urban networks, from the lowest microscale up to the highest levels of aggregation. Graph theory, for example, offers a promising means of elucidating the urban social fabric and the interactions that define it, and more specifically the link between urban infrastructure and aspatial social networks. The chapter also compares individuals and their social interactions to an archipelago, a metaphor that offers a picture of the magic of the city. It concludes by emphasizing the interdependence between the creation of cities over physical space, on the one hand, and the urban archipelago and its internal social and economic structures, which are man-made, on the other.Less
This chapter considers the prospect of a deeper understanding of social interactions in urban settings as well as their significance for the functioning and future role of cities and regions. It introduces broader sets of tools for exploring the properties of urban networks, from the lowest microscale up to the highest levels of aggregation. Graph theory, for example, offers a promising means of elucidating the urban social fabric and the interactions that define it, and more specifically the link between urban infrastructure and aspatial social networks. The chapter also compares individuals and their social interactions to an archipelago, a metaphor that offers a picture of the magic of the city. It concludes by emphasizing the interdependence between the creation of cities over physical space, on the one hand, and the urban archipelago and its internal social and economic structures, which are man-made, on the other.
Marc Mézard and Andrea Montanari
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0003
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter provides an elementary introduction to some basic concepts in theoretical computer science. It includes basic notions of graph theory and an informal introduction to computational ...
More
This chapter provides an elementary introduction to some basic concepts in theoretical computer science. It includes basic notions of graph theory and an informal introduction to computational complexity, presenting the basic classes P, NP, and NP-complete. These notions are illustrated by discussions of the minimal spanning tree and satisfiability problems, and by applications from statistical physics (spin glasses and maximum cuts), and from coding theory (decoding complexity).Less
This chapter provides an elementary introduction to some basic concepts in theoretical computer science. It includes basic notions of graph theory and an informal introduction to computational complexity, presenting the basic classes P, NP, and NP-complete. These notions are illustrated by discussions of the minimal spanning tree and satisfiability problems, and by applications from statistical physics (spin glasses and maximum cuts), and from coding theory (decoding complexity).
Ping Zhang, Gary Chartrand, and Arthur Benjamin
- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691175638
- eISBN:
- 9781400852000
- Item type:
- book
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691175638.001.0001
- Subject:
- Mathematics, Applied Mathematics
Graph theory goes back several centuries and revolves around the study of graphs—mathematical structures showing relations between objects. With applications in biology, computer science, ...
More
Graph theory goes back several centuries and revolves around the study of graphs—mathematical structures showing relations between objects. With applications in biology, computer science, transportation science, and other areas, graph theory encompasses some of the most beautiful formulas in mathematics—and some of its most famous problems. This book explores the questions and puzzles that have been studied, and often solved, through graph theory. It looks at graph theory's development and the vibrant individuals responsible for the field's growth. Introducing fundamental concepts, the book explores a diverse plethora of classic problems such as the Lights Out Puzzle, and each chapter contains math exercises for readers to savor. An eye-opening journey into the world of graphs, the book offers exciting problem-solving possibilities for mathematics and beyond.Less
Graph theory goes back several centuries and revolves around the study of graphs—mathematical structures showing relations between objects. With applications in biology, computer science, transportation science, and other areas, graph theory encompasses some of the most beautiful formulas in mathematics—and some of its most famous problems. This book explores the questions and puzzles that have been studied, and often solved, through graph theory. It looks at graph theory's development and the vibrant individuals responsible for the field's growth. Introducing fundamental concepts, the book explores a diverse plethora of classic problems such as the Lights Out Puzzle, and each chapter contains math exercises for readers to savor. An eye-opening journey into the world of graphs, the book offers exciting problem-solving possibilities for mathematics and beyond.
Iwo Białynicki-Birula and Iwona Białynicka-Birula
- Published in print:
- 2004
- Published Online:
- January 2010
- ISBN:
- 9780198531005
- eISBN:
- 9780191713033
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198531005.003.0010
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
A simple idea of drawing crude sketches made of line segments to visualize the solutions of some problems has developed over the years into a sophisticated branch of mathematics: graph theory. Simple ...
More
A simple idea of drawing crude sketches made of line segments to visualize the solutions of some problems has developed over the years into a sophisticated branch of mathematics: graph theory. Simple examples of applications of this theory, including the famous problems of the bridges of Königsberg and of the travelling salesman, are discussed.Less
A simple idea of drawing crude sketches made of line segments to visualize the solutions of some problems has developed over the years into a sophisticated branch of mathematics: graph theory. Simple examples of applications of this theory, including the famous problems of the bridges of Königsberg and of the travelling salesman, are discussed.
S. N. Dorogovtsev and J. F. F. Mendes
- Published in print:
- 2003
- Published Online:
- January 2010
- ISBN:
- 9780198515906
- eISBN:
- 9780191705670
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198515906.003.0002
- Subject:
- Physics, Soft Matter / Biological Physics
This chapter introduces the basic characteristics and notions of graph theory and the science of networks: degree, degree distribution, clustering coefficient, the average length of the shortest path ...
More
This chapter introduces the basic characteristics and notions of graph theory and the science of networks: degree, degree distribution, clustering coefficient, the average length of the shortest path between two nodes in a network, the size of a giant connected component, and others. The classical random graphs and their characteristics are introduced and explained. The contrasting types of degree distributions are discussed: namely, Poisson and scale-free distributions.Less
This chapter introduces the basic characteristics and notions of graph theory and the science of networks: degree, degree distribution, clustering coefficient, the average length of the shortest path between two nodes in a network, the size of a giant connected component, and others. The classical random graphs and their characteristics are introduced and explained. The contrasting types of degree distributions are discussed: namely, Poisson and scale-free distributions.
Anat Ninio
- Published in print:
- 2006
- Published Online:
- April 2010
- ISBN:
- 9780199299829
- eISBN:
- 9780191584985
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199299829.003.0006
- Subject:
- Psychology, Cognitive Models and Architectures
This chapter examines the role of the environment in syntactic development, and argues for novel conceptualization derived from complexity theory. According to this view, language is a complex ...
More
This chapter examines the role of the environment in syntactic development, and argues for novel conceptualization derived from complexity theory. According to this view, language is a complex network, consisting of linguistic items as well as speakers who produce words and sentences when they speak. This chapter introduces complex systems and complex networks, in particular bipartite networks, which are then used to conceptualize speakers and linguistic items. The basics of graph theory are presented and so are Zipf and Pareto curves depicting distributions of items' frequency of use in a network. The principle of preferential attachment is described, contrasting it with a deterministic frequency effect. The implication for first language acquisition is that learning means linking to the huge language network; children learning to produce syntactic combinations do not reinvent language, nor do they internalize it; instead, they link to networks of other speakers producing similar combinations.Less
This chapter examines the role of the environment in syntactic development, and argues for novel conceptualization derived from complexity theory. According to this view, language is a complex network, consisting of linguistic items as well as speakers who produce words and sentences when they speak. This chapter introduces complex systems and complex networks, in particular bipartite networks, which are then used to conceptualize speakers and linguistic items. The basics of graph theory are presented and so are Zipf and Pareto curves depicting distributions of items' frequency of use in a network. The principle of preferential attachment is described, contrasting it with a deterministic frequency effect. The implication for first language acquisition is that learning means linking to the huge language network; children learning to produce syntactic combinations do not reinvent language, nor do they internalize it; instead, they link to networks of other speakers producing similar combinations.
LOWELL BEINEKE and ROBIN WILSON
- Published in print:
- 2013
- Published Online:
- September 2013
- ISBN:
- 9780199656592
- eISBN:
- 9780191748059
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199656592.003.0015
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics, History of Mathematics
During the first half of the 20th century many classic theorems about graphs were discovered, but it was not until the second half of the century that graph theory emerged as an important field in ...
More
During the first half of the 20th century many classic theorems about graphs were discovered, but it was not until the second half of the century that graph theory emerged as an important field in its own right. In this chapter we develop themes arising from the four-colour problem, before focusing on three specific subject areas — the factorization of graphs, connectivity, and graph algorithms.Less
During the first half of the 20th century many classic theorems about graphs were discovered, but it was not until the second half of the century that graph theory emerged as an important field in its own right. In this chapter we develop themes arising from the four-colour problem, before focusing on three specific subject areas — the factorization of graphs, connectivity, and graph algorithms.
