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
Information horizons in a complex world
Umeå University, Faculty of Science and Technology, Physics.
2006 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The whole in a complex system is the sum of its parts, plus the interactions between the parts. Understanding social, biological, and economic systems therefore often depends on understanding their patterns of interactions---their networks. In this thesis, the approach is to understand complex systems by making simple network models with nodes and links. It is first of all an attempt to investigate how the communication over the network affects the network structure and, vice versa, how the network structure affects the conditions for communication.

To explore the local mechanism behind network organization, we used simplified social systems and modeled the response to communication. Low communication levels resulted in random networks, whereas higher communication levels led to structured networks with most nodes having very few links and a few nodes having very many links. We also explored various models where nodes merge into bigger units, to reduce communication costs, and showed that these merging models give rise to the same kind of structured networks.

In addition to this modeling of communication networks, we developed new ways to measure and characterize real-world networks. For example, we found that they in general favor communication on short distance, two-three steps away in the network, within what we call the information horizon.

Abstract [sv]

Helheten i ett komplext system är mer än summan av dess delar, då den även inbegriper interaktionerna mellan dem. Att studera sociala, biologiska och ekonomiska system blir därför ofta en fråga om att förstå deras interaktionsmönster, d.v.s. deras nätverk av noder och länkar. Med utgångspunkt i enkla nätverksmodeller undersöker avhandlingen i huvudsak hur kommunikation i nätverk påverkar nätverksstrukturen och, vice versa, hur nätverksstrukturen påverkar villkoren för kommunikation.

Vi utforskade mekanismerna bakom hur nätverk är organiserade genom att modellera effekten av kommunikation i förenklade sociala system. En låg kommunikationsnivå visade sig ge upphov till kaotiska nätverk där ingen nod i princip hade fler länkar än någon annan. En hög kommunikationsnivå resulterade däremot i strukturerade nätverk, med några få centrala noder med många länkar, medan flertalet noder var perifera med enbart några få länkar. Det visade sig också att alla aktörer i nätverket gynnades av kommunikation, även när den var ojämnt fördelad. Kvaliteten på kommunikationen, d.v.s. informationens giltighet, var också avgörande för vilka positioner som gynnades i ett nätverk, vilket vi visade genom att studera aktörer som spred falsk information.

Eftersom effektiv kommunikation är en viktig del i många nätverk betraktar vi utvecklingen av dem som en optimeringsprocess. Varje kommunikationshandling mellan noderna tar tid och genom att slå sig samman till större enheter begränsas dessa kostnader och gör nätverket effektivare. Dessa s.k. sammanslagningsmodeller gav upphov till samma typ av strukturerade nätverk som ovan.

Genom att utveckla olika sätt att mäta nätverksstrukturer visade vi bland annat att många verkliga system främjar kommunikation över korta avstånd, två-tre steg bort i nätverket, innanför det vi kallar informationshorisonten. Vi uppskattade också den mängd information som krävs för att orientera sig i städer, och fann att det är lättare att hitta i moderna, planerade städer än i äldre städer som utvecklats under lång tid.

Place, publisher, year, edition, pages
Department of Physics , 2006. , 76 p.
Keyword [en]
Complex systems, networks, information, communication, self-organization, network topology, agent-based modeling.
National Category
Physical Sciences
Identifiers
URN: urn:nbn:se:umu:diva-840ISBN: 9172641177 (print)OAI: oai:DiVA.org:umu-840DiVA: diva2:144706
Public defence
2006-08-22, MA121, MIT-huset, Umeå universitet, Umeå, 13:00 (English)
Opponent
Supervisors
Available from: 2006-08-31 Created: 2006-08-31 Last updated: 2010-03-12Bibliographically approved
List of papers
1. 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
2. Self-organization of structures and networks from merging and small-scale fluctuations
Open this publication in new window or tab >>Self-organization of structures and networks from merging and small-scale fluctuations
2004 (English)In: Physica A: Statistical Mechanics and its Applications, ISSN 0378-4371, E-ISSN 1873-2119, Vol. 340, no 4, 725-732 p.Article in journal (Refereed) Published
Abstract [en]

We discuss merging-and-creation as a self-organizing process for scale-free topologies in networks. Three power-law classes characterized by the power-law exponents 23 , 2 and 25 are identified and the process is generalized to networks. In the network context the merging can be viewed as a consequence of optimization related to more efficient signaling.

Place, publisher, year, edition, pages
Elsevier, 2004
Keyword
Scale-free networks, Self organized criticality, Aggregation, Merging
Identifiers
urn:nbn:se:umu:diva-5243 (URN)10.1016/j.physa.2004.05.019 (DOI)
Available from: 2006-08-31 Created: 2006-08-31 Last updated: 2017-12-14Bibliographically approved
3. A simple model for self-organization of bipartite networks
Open this publication in new window or tab >>A simple model for self-organization of bipartite networks
2004 (English)In: Europhysics Letters, ISSN 1286-4854, Vol. 67, no 3, 349-354 p.Article in journal (Refereed) Published
Abstract [en]

We suggest a minimalistic model for directed networks and suggest an application to injection and merging of magnetic field lines. We obtain a network of connected donor and acceptor vertices with degree distribution 1/s2, and with dynamical reconnection events of size Δs occurring with frequency that scales as 1/Δs3. This suggests that the model is in the same universality class as the model with annihilation for self-organization in the solar atmosphere suggested by Hughes et al. (Phys. Rev. Lett. 90 (2003) 131101).

Place, publisher, year, edition, pages
IOP Publishing, 2004
Identifiers
urn:nbn:se:umu:diva-5244 (URN)10.1209/epl/i2004-10074-0 (DOI)
Available from: 2006-08-31 Created: 2006-08-31 Last updated: 2010-03-12Bibliographically approved
4. Hide-and-seek on complex networks
Open this publication in new window or tab >>Hide-and-seek on complex networks
2005 (English)In: Europhys. Lett., ISSN 1286-4854, Vol. 69, no 5, 853-859 p.Article in journal (Refereed) Published
Abstract [en]

Signaling pathways and networks determine the ability to communicate in systems ranging from living cells to human society. We investigate how the network structure constrains communication in social, man-made and biological networks. We find that human networks of governance and collaboration have predictable communication on tête-à-tête level, reflecting well-defined pathways. In contrast, communication pathways in the Internet are more distributed. For molecular networks, the communication ability in the single-celled yeast resembles the one of human networks, whereas the more complicated Drosophila is closer to the Internet. For all investigated networks, the global communication is worse than for their random counterparts, reflecting the fact that long-distance communication is disfavored.

Place, publisher, year, edition, pages
IOP Publishing, 2005
Identifiers
urn:nbn:se:umu:diva-5245 (URN)10.1209/epl/i2004-10422-0 (DOI)
Available from: 2006-08-31 Created: 2006-08-31 Last updated: 2011-03-01Bibliographically approved
5. Networks and cities: an information perspective
Open this publication in new window or tab >>Networks and cities: an information perspective
2005 In: Phys. Rev. Lett., Vol. 94, no 028701Article in journal (Refereed) Published
Identifiers
urn:nbn:se:umu:diva-5246 (URN)
Available from: 2006-08-31 Created: 2006-08-31Bibliographically approved
6. Communication boundaries in networks
Open this publication in new window or tab >>Communication boundaries in networks
2005 (English)In: Physical Review Letters, ISSN 0031-9007, E-ISSN 1079-7114, Vol. 94, no 23, 238701- p.Article in journal (Refereed) Published
Abstract [en]

We investigate and quantify the interplay between topology and the ability to send specific signals in complex networks. We find that in a majority of investigated real-world networks the ability to communicate is favored by the network topology at small distances, but disfavored at larger distances. We further suggest how the ability to locate specific nodes can be improved if information associated with the overall traffic in the network is available.

 

Identifiers
urn:nbn:se:umu:diva-5247 (URN)10.1103/PhysRevLett.94.238701 (DOI)
Available from: 2006-08-31 Created: 2006-08-31 Last updated: 2017-12-14Bibliographically approved
7. Navigating networks with limited information
Open this publication in new window or tab >>Navigating networks with limited information
2005 (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. 71, no 6, 066111- p.Article in journal (Refereed) Published
Abstract [en]

We study navigation with limited information in networks and demonstrate that many real-world networks have a structure which can be described as favoring communication at short distance at the cost of constraining communication at long distance. This feature, which is robust and more evident with limited than with complete information, reflects both topological and possibly functional design characteristics. For example, the characteristics of the networks studied derived from a city and from the Internet are manifested through modular network designs. We also observe that directed navigation in typical networks requires remarkably little information on the level of individual nodes. By studying navigation or specific signaling, we take a complementary approach to the common studies of information transfer devoted to broadcasting of information in studies of virus spreading and the like.

Place, publisher, year, edition, pages
American Physical Society, 2005
National Category
Condensed Matter Physics
Identifiers
urn:nbn:se:umu:diva-5248 (URN)10.1103/PhysRevE.71.066111 (DOI)
Available from: 2006-08-31 Created: 2006-08-31 Last updated: 2017-12-14Bibliographically approved
8. Searchability of networks
Open this publication in new window or tab >>Searchability of networks
2005 (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. 72, no 4, 046117-046125 p.Article in journal (Refereed) Published
Abstract [en]

We investigate the searchability of complex systems in terms of their interconnectedness. Associating searchability with the number and size of branch points along the paths between the nodes, we find that scale-free networks are relatively difficult to search, and thus that the abundance of scale-free networks in nature and society may reflect an attempt to protect local areas in a highly interconnected network from nonrelated communication. In fact, starting from a random node, real-world networks with higher order organization like modular or hierarchical structure are even more difficult to navigate than random scale-free networks. The searchability at the node level opens the possibility for a generalized hierarchy measure that captures both the hierarchy in the usual terms of trees as in military structures, and the intrinsic hierarchical nature of topological hierarchies for scale-free networks as in the Internet.

Place, publisher, year, edition, pages
American Physical Society, 2005
Identifiers
urn:nbn:se:umu:diva-5249 (URN)10.1103/PhysRevE.72.046117 (DOI)
Available from: 2006-08-31 Created: 2006-08-31 Last updated: 2017-12-14Bibliographically approved
9. Modeling dynamics of information networks
Open this publication in new window or tab >>Modeling dynamics of information networks
2003 In: Phys. Rev. Lett., Vol. 91, no 178701Article in journal (Refereed) Published
Identifiers
urn:nbn:se:umu:diva-5250 (URN)
Available from: 2006-08-31 Created: 2006-08-31Bibliographically approved
10. Self-assembly of information in networks
Open this publication in new window or tab >>Self-assembly of information in networks
2006 (English)In: Europhysics letters, ISSN 0295-5075, E-ISSN 1286-4854, Vol. 74, no 6, 1109-1115 p.Article in journal (Refereed) Published
Abstract [en]

We model self-assembly of information in networks to investigate necessary conditions for building a global perception of a system by local communication. Our approach is to let agents chat in a model system to self-organize distant communication pathways. We demonstrate that simple local rules allow agents to build a perception of the system, that is robust to dynamical changes and mistakes. We find that messages are most effectively forwarded in the presence of hubs, while transmission in hub-free networks is more robust against misinformation and failures.

National Category
Physical Sciences
Identifiers
urn:nbn:se:umu:diva-5251 (URN)10.1209/epl/i2006-10064-2 (DOI)
Available from: 2006-08-31 Created: 2006-08-31 Last updated: 2017-12-14Bibliographically approved
11. Modeling self-organization of communication and topology in social networks
Open this publication in new window or tab >>Modeling self-organization of communication and topology in social 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, no 1, 016108- p.Article in journal (Refereed) Published
Abstract [en]

This paper introduces a model of self-organization between communication and topology in social networks, with a feedback between different communication habits and the topology. To study this feedback, we let agents communicate to build a perception of a network and use this information to create strategic links. We observe a narrow distribution of links when the communication is low and a system with a broad distribution of links when the communication is high. We also analyze the outcome of chatting, cheating, and lying, as strategies to get better access to information in the network. Chatting, although only adopted by a few agents, gives a global gain in the system. Contrary, a global loss is inevitable in a system with too many liars.

National Category
Physical Sciences
Identifiers
urn:nbn:se:umu:diva-5252 (URN)10.1103/PhysRevE.74.016108 (DOI)
Available from: 2006-08-31 Created: 2006-08-31 Last updated: 2017-12-14Bibliographically approved

Open Access in DiVA

fulltext(1152 kB)3206 downloads
File information
File name FULLTEXT01.pdfFile size 1152 kBChecksum SHA-1
e3fb23287e268b97ad4ca000e92a692071220294812773b6acae5d479e0019e5eae47e63
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Rosvall, Martin
By organisation
Physics
Physical Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 3206 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: 13425 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