umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Structures in complex systems: Playing dice with networks and books
Umeå University, Faculty of Science and Technology, Department of Physics.
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Complex systems are neither perfectly regular nor completely random. They consist of a multitude of players who, in many cases, playtogether in a way that makes their combined strength greater than the sum of their individual achievements. It is often very effective to represent these systems as networks where the actual connections between the players take on a crucial role.Networks exist all around us and are an important part of our world, from the protein machinery inside our cells to social interactions and man-madecommunication systems. Many of these systems have developed over a long period of time and are constantly undergoing changes driven by complicated microscopic events. These events are often too complicated for us to accurately resolve, making the world seem random and unpredictable. There are however ways of using this unpredictability in our favor by replacing the true events by much simpler stochastic rules giving effectively the same outcome. This allows us to capture the macroscopic behavior of the system, to extract important information about the dynamics of the system and learn about the reason for what we observe. Statistical mechanics gives the tools to deal with such large systems driven by underlying random processes under various external constraints, much like how intracellular networks are driven by random mutations under the constraint of natural selection.This similarity makes it interesting to combine the two and to apply some of the tools provided by statistical mechanics on biological systems.In this thesis, several null models are presented, with this view point in mind, to capture and explain different types of structural properties of real biological networks.

The most recent major transition in evolution is the development of language, both spoken and written. This thesis also brings up the subject of quantitative linguistics from the eyes of a physicist, here called linguaphysics. Also in this case the data is analyzed with an assumption of an underlying randomness. It is shown that some statistical properties of books, previously thought to be universal, turn out to exhibit author specific size dependencies. A meta book theory is put forward which explains this dependency by describing the writing of a text as pulling a section out of a huge, individual, abstract mother book.

Abstract [sv]

Komplexa system är varken perfekt ordnade eller helt slumpmässiga. De består av en mängd aktörer, som i många fall agerar tillsammans på ett sådant sätt att deras kombinerade styrka är större än deras individuella prestationer. Det är ofta effektivt att representera dessa system som nätverk där de faktiska kopplingarna mellan aktörerna spelar en avgörande roll. Nätverk finns överallt omkring oss och är en viktig del av vår värld , från proteinmaskineriet inne i våra celler till sociala samspel och människotillverkade kommunikationssystem.Många av dessa system har utvecklats under lång tid och genomgår hela tiden förändringar som drivs på av komplicerade småskaliga händelser.Dessa händelser är ofta för komplicerade för oss att noggrant kunna analysera, vilket får vår värld att verka slumpmässig och oförutsägbar. Det finns dock sätt att använda denna oförutsägbarhet till vår fördel genom att byta ut de verkliga händelserna mot mycket enklare regler baserade på sannolikheter, som ger effektivt sett samma utfall. Detta tillåter oss att fånga systemets övergripande uppförande, att utvinna viktig information om systemets dynamik och att få kunskap om anledningen till vad vi observerar. Statistisk mekanik hanterar stora system pådrivna av sådana underliggande slumpmässiga processer under olika restriktioner, på liknande sätt som nätverk inne i celler drivs av slumpmässiga mutationer under restriktionerna från naturligt urval. Denna likhet gör det intressant att kombinera de två och att applicera de verktyg som ges av statistisk mekanik på biologiska system. I denna avhandling presenteras flera nollmodeller som, baserat på detta synsätt, fångar och förklarar olika typer av strukturella egenskaper hos verkliga biologiska nätverk.

Den senaste stora evolutionära övergången är utvecklandet av språk, både talat och skrivet. Denna avhandling tar också upp ämnet om kvantitativ linguistik genom en fysikers ögon, här kallat linguafysik. även i detta fall så analyseras data med ett antagande om en underliggande slumpmässighet. Det demonstreras att vissa statistiska egenskaper av böcker, som man tidigare trott vara universella, egentligen beror på bokens längd och på författaren. En metaboksteori ställs fram vilken förklarar detta beroende genom att beskriva författandet av en text som att rycka ut en sektion ur en stor, individuell, abstrakt moderbok.

Place, publisher, year, edition, pages
Umeå: Umeå University, Department of physics , 2009. , 63 p.
Keyword [en]
Complex systems, networks, statistical physics, biological networks, quantitative linguistics, word frequencies.
National Category
Physical Sciences
Identifiers
URN: urn:nbn:se:umu:diva-27694ISBN: 978-91-7264-910-1 (print)OAI: oai:DiVA.org:umu-27694DiVA: diva2:277138
Public defence
2009-12-17, N360, Naturvetarhuset, Umeå universitet, 901 87, Umeå, Umeå, 13:00 (English)
Opponent
Supervisors
Available from: 2009-11-20 Created: 2009-11-16 Last updated: 2010-11-01Bibliographically approved
List of papers
1. Models and average properties of scale-free directed networks
Open this publication in new window or tab >>Models and average properties of scale-free directed networks
2006 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 74, 026104-026104-7 p.Article in journal (Refereed) Published
Abstract [en]

We extend the merging model for undirected networks by Kim et al. [Eur. Phys. J. B 43, 369 (2004)] to directed networks and investigate the emerging scale-free networks. Two versions of the directed merging model, friendly and hostile merging, give rise to two distinct network types. We uncover that some nontrivial features of these two network types resemble two levels of a certain randomization/nonspecificity in the link reshuffling during network evolution. Furthermore, the same features show up, respectively, in metabolic networks and transcriptional networks. We introduce measures that single out the distinguishing features between the two prototype networks, as well as point out features that are beyond the prototypes.

Keyword
large-scale systems, graph theory, cellular biophysics
Identifiers
urn:nbn:se:umu:diva-10926 (URN)10.1103/PhysRevE.74.026104 (DOI)
Note
Selected for Aug.15, 2006 issue of Virtual Journal of Biological Physics ResearchAvailable from: 2007-03-05 Created: 2007-03-05 Last updated: 2017-12-14Bibliographically approved
2. Degree landscapes in scale-free networks
Open this publication in new window or tab >>Degree landscapes in scale-free networks
Show others...
2006 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 74, 036119- p.Article in journal (Refereed) Published
Abstract [en]

We generalize the degree-organizational view of real-world networks with broad degree distributions in a landscape analog with mountains (high-degree nodes) and valleys (low-degree nodes). For example, correlated degrees between adjacent nodes correspond to smooth landscapes (social networks), hierarchical networks to one-mountain landscapes (the Internet), and degree-disassortative networks without hierarchical features to rough landscapes with several mountains. To quantify the topology, we here measure the widths of the mountains and the separation between different mountains. We also generate ridge landscapes to model networks organized under constraints imposed by the space the networks are embedded in, associated to spatial or in molecular networks to functional localization.

Keyword
topology, random processes
Identifiers
urn:nbn:se:umu:diva-5242 (URN)10.1103/PhysRevE.74.036119 (DOI)
Available from: 2006-08-31 Created: 2006-08-31 Last updated: 2017-12-14Bibliographically approved
3. One hub-one process: A tool based view on regulatory network topology
Open this publication in new window or tab >>One hub-one process: A tool based view on regulatory network topology
2008 (English)In: BMC Systems Biology, ISSN 1752-0509, Vol. 2, 25- p.Article in journal (Refereed) Published
Abstract [en]

The relationship between the regulatory design and the functionality of molecular networks is a key issue in biology. Modules and motifs have been associated to various cellular processes, thereby providing anecdotal evidence for performance based localization on molecular networks. To quantify structure-function relationship we investigate similarities of proteins which are close in the regulatory network of the yeast Saccharomyces Cerevisiae. We find that the topology of the regulatory network show weak remnants of its history of network reorganizations, but strong features of co-regulated proteins associated to similar tasks. This suggests that local topological features of regulatory networks, including broad degree distributions, emerge as an implicit result of matching a number of needed processes to a finite toolbox of proteins.

Keyword
Regulatory network, topology
National Category
Condensed Matter Physics
Identifiers
urn:nbn:se:umu:diva-11457 (URN)doi:10.1186/1752-0509-2-25 (DOI)
Available from: 2009-01-08 Created: 2009-01-08 Last updated: 2009-11-17Bibliographically approved
4. Scale-freeness for networks as a degenerate ground state: A Hamiltonian formulation
Open this publication in new window or tab >>Scale-freeness for networks as a degenerate ground state: A Hamiltonian formulation
2007 (English)In: Europhysics letters, ISSN 0295-5075, E-ISSN 1286-4854, Vol. 78, no 2, 28004-1-28004-5 p.Article in journal (Other (popular science, discussion, etc.)) Published
Abstract [en]

The origin of scale-free degree distributions in the context of networks is addressed through an analogous non-network model in which the node degree corresponds to the number of balls in a box and the rewiring of links to balls moving between the boxes. A statistical mechanical formulation is presented and the corresponding Hamiltonian is derived. The energy, the entropy, as well as the degree distribution and its fluctuations are investigated at various temperatures. The scale-free distribution is shown to correspond to the degenerate ground state, which has small fluctuations in the degree distribution and yet a large entropy. We suggest an implication of our results from the viewpoint of the stability in evolution of networks.

Keyword
Complex systems, Networks
National Category
Condensed Matter Physics
Identifiers
urn:nbn:se:umu:diva-6513 (URN)10.1209/0295-5075/78/28004 (DOI)
Available from: 2007-12-13 Created: 2007-12-13 Last updated: 2017-12-14Bibliographically approved
5. Optimization and scale-freeness for complex networks
Open this publication in new window or tab >>Optimization and scale-freeness for complex networks
2007 (English)In: Chaos, ISSN 1054-1500, E-ISSN 1089-7682, Vol. 17, no 026117, 7- p.Article in journal (Refereed) Published
Abstract [en]

Complex networks are mapped to a model of boxes and balls where the balls are distinguishable. It is shown that the scale-free size distribution of boxes maximizes the information associated with the boxes provided configurations including boxes containing a finite fraction of the total amount of balls are excluded. It is conjectured that for a connected network with only links between different nodes, the nodes with a finite fraction of links are effectively suppressed. It is hence suggested that for such networks the scale-free node-size distribution maximizes the information encoded on the nodes. The noise associated with the size distributions is also obtained from a maximum entropy principle. Finally, explicit predictions from our least bias approach are found to be borne out by metabolic networks.

Keyword
Statistical physics, Networks
National Category
Condensed Matter Physics
Identifiers
urn:nbn:se:umu:diva-6521 (URN)10.1063/1.2720101 (DOI)
Available from: 2007-12-13 Created: 2007-12-13 Last updated: 2017-12-14Bibliographically approved
6. The blind watchmaker network: Scale-freeness and evolution
Open this publication in new window or tab >>The blind watchmaker network: Scale-freeness and evolution
2008 (English)In: PLoS ONE, ISSN 1932-6203, Vol. 3, no 2, e1690-1-e1690-5 p.Article in journal (Other (popular science, discussion, etc.)) Published
Abstract [en]

It is suggested that the degree distribution for networks of the cell-metabolism for simple organisms reflects an ubiquitous randomness. This implies that natural selection has exerted no or very little pressure on the network degree distribution during evolution. The corresponding random network, here termed the blind watchmaker network has a power-law degree distribution with an exponent gamma >= 2. It is random with respect to a complete set of network states characterized by a description of which links are attached to a node as well as a time-ordering of these links. No a priory assumption of any growth mechanism or evolution process is made. It is found that the degree distribution of the blind watchmaker network agrees very precisely with that of the metabolic networks. This implies that the evolutionary pathway of the cell-metabolism, when projected onto a metabolic network representation, has remained statistically random with respect to a complete set of network states. This suggests that even a biological system, which due to natural selection has developed an enormous specificity like the cellular metabolism, nevertheless can, at the same time, display well defined characteristics emanating from the ubiquitous inherent random element of Darwinian evolution. The fact that also completely random networks may have scale-free node distributions gives a new perspective on the origin of scale-free networks in general.

Keyword
Metabolic networks, statistical mechanics, evolution
National Category
Condensed Matter Physics
Identifiers
urn:nbn:se:umu:diva-11458 (URN)10.1371/journal.pone.0001690 (DOI)
Available from: 2009-01-08 Created: 2009-01-08 Last updated: 2009-11-17Bibliographically approved
7. Selective pressure on metabolic network structures as measured from the random blind-watchmaker network
Open this publication in new window or tab >>Selective pressure on metabolic network structures as measured from the random blind-watchmaker network
2010 (English)In: New Journal of Physics, ISSN 1367-2630, E-ISSN 1367-2630, Vol. 12, no 103047Article in journal (Refereed) Published
Abstract [en]

A random null model termed the Blind Watchmaker network (BW) has been shown to reproduce the degree distribution found in metabolic networks. This might suggest that natural selection has had little influence on this particular network property. We here investigate to what extent other structural network properties have evolved under selective pressure from the corresponding ones of the random null model: The clustering coefficient and the assortativity measures are chosen and it is found that these measures for the metabolic network structure are close enough to the BW-network so as to fit inside its reachable random phase space. It is furthermore shown that the use of this null model indicates an evolutionary pressure towards low assortativity and that this pressure is stronger for larger networks. It is also shown that selecting for BW networks with low assortativity causes the BW degree distribution to slightly deviate from its power-law shape in the same way as the metabolic networks. This implies that an equilibrium model with fluctuating degree distribution is more suitable as a null model, when identifying selective pressures, than a randomized counterpart with fixed degree sequence, since the overall degree sequence itself can change under selective pressure on other global network properties.

Place, publisher, year, edition, pages
IOP Publishing Ltd and Deutsche Physikalische Gesellschaft, 2010
Keyword
Metabolic networks, network structures, random null-models
National Category
Condensed Matter Physics
Identifiers
urn:nbn:se:umu:diva-37373 (URN)10.1088/1367-2630/12/10/103047 (DOI)000284770300004 ()
Available from: 2010-11-01 Created: 2010-10-29 Last updated: 2017-12-12Bibliographically approved
8. Size dependent word frequencies and translational invariance of books
Open this publication in new window or tab >>Size dependent word frequencies and translational invariance of books
2010 (English)In: Physica A: Statistical Mechanics and its Applications, ISSN 0378-4371, E-ISSN 1873-2119, Vol. 389, no 2, 330-341 p.Article in journal (Refereed) Published
Abstract [en]

It is shown that a real novel shares many characteristic features with a null model in which the words are randomly distributed throughout the text. Such a common feature is a certain translational invariance of the text. Another is that the functional form of the word-frequency distribution of a novel depends on the length of the text in the same way as the null model.This means that an approximate power-law tail ascribed to the data will have an exponent which changes with the size of the text-section which is analyzed.A further consequence is that a novel cannot be described by text-evolution models like the Simon model.The size-transformation of a novel is found to be well described by a specific Random Book Transformation.This size transformation in addition enables a more precise determination of the functional form of the word-frequency distribution.The implications of the results are discussed.

Place, publisher, year, edition, pages
Elsevier, 2010
Keyword
Word frequencies, Zipf's law, Simon model
National Category
Specific Languages Other Physics Topics
Identifiers
urn:nbn:se:umu:diva-27635 (URN)10.1016/j.physa.2009.09.022 (DOI)000271844100015 ()
Available from: 2009-11-16 Created: 2009-11-12 Last updated: 2017-12-12
9. The meta book and size-dependent properties of written language
Open this publication in new window or tab >>The meta book and size-dependent properties of written language
2009 (English)In: New Journal of Physics, ISSN 1367-2630, E-ISSN 1367-2630, Vol. 11, 123015Article in journal (Refereed) Published
Abstract [en]

Evidence is given for a systematic text-length dependence of the power-law index $\gamma$ of a single book. The estimated $\gamma$ values are consistent with a monotonic decrease from 2 to 1 with increasing length of a text. A direct connection to an extended Heap's lawis explored. The infinite book limit is, as a consequence, proposed to be given by $\gamma = 1$ instead of the value $\gamma=2$ expected if the Zipf's law was ubiquitously applicable. In addition we explore the idea that the systematic text-length dependence can be described by a meta book concept, which is an abstract representation reflecting the word-frequency structure of a text. According to this concept the word-frequency distribution of a text, with a certain length written by a single author, has the same characteristics as a text of the same length pulled out from an imaginary complete infinite corpus written by the same author.

Place, publisher, year, edition, pages
Bristol: Institute of Physics Publishing (IOPP), 2009
Keyword
Quantitative linguistics, word frequencies, size dependencies, meta book
National Category
Physical Sciences
Identifiers
urn:nbn:se:umu:diva-27643 (URN)10.1088/1367-2630/11/12/123015 (DOI)000272703100001 ()
External cooperation:
Available from: 2009-11-16 Created: 2009-11-12 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

fulltext(1197 kB)613 downloads
File information
File name FULLTEXT01.pdfFile size 1197 kBChecksum SHA-512
0d742b7a62113b791a6d551e003a9e2b11f5231d4267a754e9b6e215c8b36c5f5d55211975ab31798d48104f731b7bfc4d661390541c02ebea61ac53f7a5341f
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Bernhardsson, Sebastian
By organisation
Department of Physics
Physical Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 613 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1231 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf