Minimum Spanning Markovian Trees: Introducing Context-Sensitivity into the Generation of Spanning Trees

Alexander Mehler ()
Additional contact information
Alexander Mehler: Goethe-University Frankfurt am Main

Chapter Chapter 15 in Structural Analysis of Complex Networks, 2011, pp 381-401 from Springer

Abstract: Abstract This chapter introduces a novel class of graphs: Minimum Spanning Markovian Trees (MSMTs). The idea behind MSMTs is to provide spanning trees that minimize the costs of edge traversals in a Markovian manner, that is, in terms of the path starting with the root of the tree and ending at the vertex under consideration. In a second part, the chapter generalizes this class of spanning trees in order to allow for damped Markovian effects in the course of spanning. These two effects, (1) the sensitivity to the contexts generated by consecutive edges and (2) the decreasing impact of more antecedent (or “weakly remembered”) vertices, are well known in cognitive modeling [6, 10, 21, 23]. In this sense, the chapter can also be read as an effort to introduce a graph model to support the simulation of cognitive systems. Note that MSMTs are not to be confused with branching Markov chains or Markov trees [20] as we focus on generating spanning trees from given weighted undirected networks.

Keywords: Markovian trees; Minimum spanning trees; Cohesion trees; Linguistic networks; Semiotic networks (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-0-8176-4789-6_15

Ordering information: This item can be ordered from
http://www.springer.com/9780817647896

DOI: 10.1007/978-0-8176-4789-6_15

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().