NEXUS 1492

Beschreibung

The ambition of NEXUS 1492 is to rewrite a chapter in global history by focusing on transformations of indigenous, Amerindian cultures and societies across the historical divide of 1492. It investigates the impacts of colonial encounters in the Caribbean, the nexus of the first interactions between the New and the Old World. The project is a joint effort with groups from Universiteit Leiden and Vrije Universiteit Amsterdam.pOur role is the reconstructing of archaeological aetworks and their transformations. We address the transformations of archaeological networks of people, objects and ideas across the historical divide by foundational research on ways of reconstructing archaeological networks from sparse, fragmented and dissimilar datasets, driven by and tested in case-studies of interdependent, multi-level Amerindian networks in the period AD 1000-1800. Unparalleled by conventional methods, network approaches bring to archaeology the potential to model relations between past cultures, communities and individuals as opposed to emphasising the inherent qualities of such entities.

Institutionen
  • Zukunftskolleg
Publikationen
    Amati, Viviana; Munson, Jessica; Scholnick, Jonathan; Habiba (2019): Applying event history analysis to explain the diffusion of innovations in archaeological networks Journal of Archaeological Science. 2019, 104, pp. 1-9. ISSN 0305-4403. Available under: doi: 10.1016/j.jas.2019.01.006

Applying event history analysis to explain the diffusion of innovations in archaeological networks

×

The simple dyadic structure of a network is the basis for studying a wide variety of entities and their relationships, as well as the outcomes of processes such as the diffusion of innovations. Here, we apply models from event history analysis and cultural evolutionary theory to investigate whether and by what means network ties facilitated the transmission of certain cultural traits in past complex societies. To illustrate the application of these models to archaeological data, we examine the spread of dynastic rituals by analyzing data collected from Classic Maya hieroglyphic inscriptions. In addition to providing a cautionary tale for the construction of archaeological networks, the results of this study highlight the compatibility of cultural evolutionary and social network approaches to investigate the spread of novel traits.

Forschungszusammenhang (Projekte)

    Brughmans, Tom; van Garderen, Mereke; Gillings, Mark (2018): Introducing visual neighbourhood configurations for total viewsheds Journal of Archaeological Science. 2018, 96, pp. 14-25. ISSN 0305-4403. eISSN 1095-9238. Available under: doi: 10.1016/j.jas.2018.05.006

Introducing visual neighbourhood configurations for total viewsheds

×

The Visual Neighbourhood Configurations (VNCs) approach is presented: a new approach for exploring complex theories of visual phenomena in landscapes by processing total viewsheds. Such theories most commonly concern the configuration of visual properties of areas around locations rather than solely the visual properties of the locations themselves. The typical approach to interpreting total viewshed results by classifying cell values is therefore problematic because it does not take cells’ local areas into account. VNC overcomes this issue by enabling one to formally describe area-related aspects of the visibility theory, because it formally incorporates the area around a given viewpoint: the shape and size of neighbourhoods as well as, where relevant, the structure and expectation of visual property values within the neighbourhood. Following a brief review that serves to place the notion of the VNC in context, the method to derive visual neighbourhood configurations is explained as well as the VNC analysis tool software created to implement it. The use of the method is then illustrated through a case-study of seclusion, hiding and hunting locales afforded by the standing stone settings of Exmoor (United Kingdom).

Forschungszusammenhang (Projekte)

    Brughmans, Tom; de Waal, Maaike S.; Hofman, Corinne L.; Brandes, Ulrik (2018): Exploring Transformations in Caribbean Indigenous Social Networks through Visibility Studies : the Case of Late Pre-Colonial Landscapes in East-Guadeloupe (French West Indies) Journal of Archaeological Method and Theory. 2018, 25(2), pp. 475-519. ISSN 1072-5369. eISSN 1573-7764. Available under: doi: 10.1007/s10816-017-9344-0

Exploring Transformations in Caribbean Indigenous Social Networks through Visibility Studies : the Case of Late Pre-Colonial Landscapes in East-Guadeloupe (French West Indies)

×

This paper presents a study of the visual properties of natural and Amerindian cultural landscapes in late pre-colonial East-Guadeloupe and of how these visual properties affected social interactions. Through a review of descriptive and formal visibility studies in Caribbean archaeology, it reveals that the ability of visual properties to affect past human behaviour is frequently evoked but the more complex of these hypotheses are rarely studied formally. To explore such complex hypotheses, the current study applies a range of techniques: total viewsheds, cumulative viewsheds, visual neighbourhood configurations and visibility networks. Experiments were performed to explore the control of seascapes, the functioning of hypothetical smoke signalling networks, the correlation of these visual properties with stylistic similarities of material culture found at sites and the change of visual properties over time. The results of these experiments suggest that only few sites in Eastern Guadeloupe are located in areas that are particularly suitable to visually control possible sea routes for short- and long-distance exchange; that visual control over sea areas was not a factor of importance for the existence of micro-style areas; that during the early phase of the Late Ceramic Age networks per landmass are connected and dense and that they incorporate all sites, a structure that would allow hypothetical smoke signalling networks; and that the visual properties of locations of the late sites Morne Souffleur and Morne Cybèle-1 were not ideal for defensive purposes. These results led us to propose a multi-scalar hypothesis for how lines of sight between settlements in the Lesser Antilles could have structured past human behaviour: short-distance visibility networks represent the structuring of navigation and communication within landmasses, whereas the landmasses themselves served as focal points for regional navigation and interaction. We conclude by emphasising that since our archaeological theories about visual properties usually take a multi-scalar landscape perspective, there is a need for this perspective to be reflected in our formal visibility methods as is made possible by the methods used in this paper.

Forschungszusammenhang (Projekte)

  Habiba; Athenstädt, Jan C.; Mills, Barbara J.; Brandes, Ulrik (2018): Social networks and similarity of site assemblages Journal of Archaeological Science. 2018, 92, pp. 63-72. ISSN 0305-4403. eISSN 1095-9238. Available under: doi: 10.1016/j.jas.2017.11.002

Social networks and similarity of site assemblages

×

There have been a number of similarity measures developed in a variety of research domains. Generally, these measures are developed for a specific context and later reused in other contexts and applications, depending on their ease of use and perceived applicability. While there might be statistical reasons to use a particular similarity index, the results of other measures should be taken into account as well, as various similarity measures do not necessarily have similar contextual meaning. Two entities can be similar with respect to a certain similarity criterion but may be distinct in terms of another. Thus, an understanding of the mathematical logic behind a method is crucial to the interpretation of the resulting network of similarities. We review a number of methods from the literature, for constructing similarity networks among disparate entities, regarding their applicability on data from archaeological sites. Formally, given an N X p matrix of N entities with p distinct classes of attributes, how are the entities comparable to each other with respect to the kinds of attributes they share? We distinguish three qualitatively different families of similarity measures for deducing relationships among entities that may meaningfully map onto various distinct social phenomena, such as migration, material acquisition, and movement of goods and skills, among others. Entities can be compared based on: (a) non{uniform weighting of attributes, (b) asymmetric dominance relationships, and (c) rank correlations. We ground the significance and distinction of these classes of measures by giving comparative and contextual examples of selected methods on a case study of archaeological collections pertaining to 1200–1500 CE from the US Southwest region. We attempt to elucidate the differences in outcomes and their meanings when choosing various similarity methods for comparing disparate entities.

Forschungszusammenhang (Projekte)

    Amati, Viviana; Shafie, Termeh; Brandes, Ulrik (2018): Reconstructing Archaeological Networks with Structural Holes Journal of Archaeological Method and Theory. 2018, 25(1), pp. 226-253. ISSN 1072-5369. eISSN 1573-7764. Available under: doi: 10.1007/s10816-017-9335-1

Reconstructing Archaeological Networks with Structural Holes

×

Model-based reconstruction is an approach to infer network structures where they cannot be observed. For archaeological networks, several models based on assumptions concerning distance among sites, site size, or costs and benefits have been proposed to infer missing ties. Since these assumptions are formulated at a dyadic level, they do not provide means to express dependencies among ties and therefore include less plausible network scenarios. In this paper we investigate the use of network models that explicitly incorporate tie dependence. In particular, we consider exponential random graph models, and show how they can be applied to reconstruct networks coherent with Burt's arguments on closure and structural holes (Burt 2001). The approach is illustrated on data from the Middle Bronze Age in the Aegean.

Forschungszusammenhang (Projekte)

  van Garderen, Mereke (2018): Pictures of the Past : Visualization and visual analysis in archaeological context

Pictures of the Past : Visualization and visual analysis in archaeological context

×

Data visualization, the main topic of this dissertation, is the science concerned with the design and creation of visual representations intended to convey information and facilitate understanding. In a scientific context, the data to be visualized are typically research results, which can originate from any discipline. The main challenges in data visualization are to find visual representations which (1) are as accurate as possible, (2) can be understood quickly and well by viewers, and (3) can be produced automatically and efficiently. The latter is especially important when large or dynamic data sets are involved. This dissertation is focused on addressing these challenges for a particular application domain: the visualization of archaeological data. We identify general properties that often characterize archaeological data and discuss a variety of visualization methods suitable for data with these properties. For existing methods from the area of mathematics and computer science, we explain how they can be applied – either directly or with some adaptations – in the context of archaeology. We also introduce new approaches, tailored to various archaeological applications. Case studies and real archaeological data sets are used to demonstrate the use of these approaches in practical applications. However, because of our focus on general data properties rather than specific data sets, the methods presented in this dissertation are in fact widely applicable beyond the field of archaeology as well.

Forschungszusammenhang (Projekte)

  Athenstädt, Jan C. (2018): Reconstruction and Visualization of Archaeological Networks

Reconstruction and Visualization of Archaeological Networks

×

Gegenstand dieser Dissertation sind verschiedene Aspekte der Rekonstruktion und Visualisierung von Netzwerkdaten in einem archäologischen Kontext in der Karibik. Die vorgestellten Methoden können einen Beitrag leisten, Migrations- und Handelswege zu rekonstruieren und die resultierenden Daten zu veranschaulichen.

Die häufig sehr fragmentierten und unvollständigen Datensätze, basierend auf Ausgrabungen und der Analyse von Fundstücken, stellen große Herausforderungen an Archäologen, wenn es darum geht, menschliche Interaktionen in der Vergangenheit zu rekonstruieren. Insbesondere in der Region im Fokus dieser Arbeit, der Karibik, sind vor allem Artefakte aus organischem Material aufgrund der klimatischen Bedingungen kaum erhalten.

In Teil 1 werden optimale Kanurouten zwischen den Inseln der Karibik rekonstruiert, unter Berücksichtigung von Umwelteinflüssen durch Strom, Wind und Wellen. Der Teil beginnt mit einer Analyse der Umwelteinflüsse und ihrer saisonalen Veränderungen mit einem Fokus auf den Strömungsdaten. Hierbei zeigen sich allerdings nur schwache Tendenzen, die von den täglichen Schwankungen überlagert werden.

Zwei existierende Ansätze zur optimalen Routenberechnung von Schiffen werden adaptiert, um der Situation in der Karibik mit vielen Inseln und Strömungsgeschwindigkeiten nahe an der Maximalgeschwindigkeit der Kanus gerecht zu werden. Im Vergleich der Methoden stellt sich die auf Zeitfronten basierende Methode als überlegen in Bezug auf die Rechenzeit heraus. Die Ergebnisse verschiedener Fallstudien mit dem Algorithmus werden vorgestellt.

Um zu evaluieren, inwieweit menschliche Akteure in der Lage sind, die optimalen Routen zu finden, wurde ein Paddelspiel entwickelt, dass es dem Spieler erlaubt, ein Kanu auf verschiedenen Routen zwischen den Inseln der Karibik zu paddeln. Im Rahmen eines zweiwöchigen Wettbewerbs wurden die Routen der Spieler aufgezeichnet und analysiert. Die Spieler waren zwar nicht in der Lage, die optimale Route zu finden; allerdings deutet eine Analyse der Spielzeiten der beiden aktivsten Spieler darauf hin, dass sich die Spieler in der Wahl der Routen kontinuierlich verbessert haben.

In Teil 2 werden Methoden zur Quantifizierung menschlicher Wahrnehmung von Distanzen und Ähnlichkeiten entwickelt und evaluiert mit dem Ziel, diese Distanzmaße für eine Typisierung von Tonscherben einzusetzen. Die entwickelten Methoden werden mit Triadentests, einer etablierten Methode aus dem Bereich der Soziologie, verglichen.

In der ersten Methode (two-dimensional arrangements) werden die Teilnehmer gebeten, Objekte im zweidimensionalen Raum so anzuordnen, dass ihre Abstände den empfundenen Ähnlichkeiten entsprechen.

In der zweiten Methode (multidimensional distance recording, MDR) werden gemeinsam mit dem Teilnehmer mögliche Dimensionen zur Einordnung der Objekte herausgearbeitet und die Objekte in diesen Dimensionen auf kategorischen Skalen, ordinalen Skalen oder der Intervallskala angeordnet. Mit Hilfe der Gower-Distanz können Entfernungen zwischen den Positionen der Objekte berechnet werden.

Die Methoden werden in drei Fallstudien evaluiert.

In Teil 3 der Arbeit wird ein theoretisches, NP-vollständiges Problem aus dem Bereich des Graphenzeichnens betrachtet. Die zentrale Frage ist, ob es möglich ist, einen planaren Graphen mit – durch Regionen gekennzeichneten (überlappenden) Clustern – so zu zeichnen, dass
- die Region jedes Clusters genau die Knoten des Clusters enthält,
- eine Kante eine Clustergrenze maximal einmal schneiden darf,
- die Region eines Clusters, der eine Teilmenge eines anderen Clusters ist, innerhalb der Region des enthaltenden Clusters gezeichnet wird und
- jede zusammenhängende Region aus der Schnittmenge von zwei Clustern mindestens einen Knoten enthält.

Es wird gezeigt, dass das Problem NP-schwer bleibt, auch wenn die Clusterung aus zwei Partitionen zusammengesetzt ist. Im Gegenzug wird ein Algorithmus vorgestellt, der das Problem für zwei Partitionen in Linearzeit löst, wenn jeder Cluster und sein Komplement zusammenhängend sind. Für den generellen Fall (ohne die Bedingung der Partitionen) wird ein Polynomialzeit-Algorithmus präsentiert, der unter der Bedingung funktioniert, dass jeder Cluster einen zusammenhängenden Graphen induziert.

Forschungszusammenhang (Projekte)

    van Garderen, Mereke; Pampel, Barbara; Nocaj, Arlind; Brandes, Ulrik (2017): Minimum-Displacement Overlap Removal for Geo-referenced Data Visualization HEER, Jeffrey, ed. and others. EuroVis 2017 Eurographics / IEEE VGTC Conference on Visualization 2017. 2017, pp. 423-433. Computer Graphics Forum. 36,3. ISSN 0167-7055. eISSN 1467-8659. Available under: doi: 10.1111/cgf.13199

Minimum-Displacement Overlap Removal for Geo-referenced Data Visualization

×

Given a set of rectangles embedded in the plane, we consider the problem of adjusting the layout to remove all overlap while preserving the orthogonal order of the rectangles. The objective is to minimize the displacement of the rectangles. We call this problem MINIMUM-DISPLACEMENT OVERLAP REMOVAL (MDOR). Our interest in this problem is motivated by the application of displaying metadata of archaeological sites. Because most existing overlap removal algorithms are not designed to minimize displacement while preserving orthogonal order, we present and compare several approaches which are tailored to our particular usecase. We introduce a new overlap removal heuristic which we call REARRANGE. Although conceptually simple, it is very effective in removing the overlap while keeping the displacement small. Furthermore, we propose an additional procedure to repair the orthogonal order after every iteration, with which we extend both our new heuristic and PRISM, a widely used overlap removal algorithm. We compare the performance of both approaches with and without this order repair method. The experimental results indicate that REARRANGE is very effective for heterogeneous input data where the overlap is concentrated in few dense regions.

Forschungszusammenhang (Projekte)

    Shafie, Termeh; Schoch, David; Mans, Jimmy; Hofman, Corinne; Brandes, Ulrik (2017): Hypergraph Representations : a Study of Carib Attacks on Colonial Forces, 1509-1700 Journal Of Historical Network Research. 2017, 1(1), pp. 52-70. Available under: doi: 10.25517/jhnr.v1i1.6

Hypergraph Representations : a Study of Carib Attacks on Colonial Forces, 1509-1700

×

Network data consisting of recorded historical events can be represented as hyper-graphs where the ties or events can connect any number of nodes or event related attributes. In this paper, we perform a centrality analysis of a directed hypergraph representing attacks by indigenous peoples from the Lesser Antilles on European colonial settlements, 1509–1700. The results of central attacks with respect to at- tacked colonial force, member of attack alliances, and year and location of attack are discussed and compared to a non-relational exploratory analysis of the data. This comparison points to the importance of a mixed methods approach to enhance the analysis and to obtain a complementary understanding of a network study.

Forschungszusammenhang (Projekte)

    Laffoon, Jason E.; Sonnemann, Till F.; Shafie, Termeh; Hofman, Corinne L.; Brandes, Ulrik; Davies, Gareth R. (2017): Investigating human geographic origins using dual-isotope (87Sr/86Sr, δ18O) assignment approaches PLOS ONE. 2017, 12(2), e0172562. eISSN 1932-6203. Available under: doi: 10.1371/journal.pone.0172562

Investigating human geographic origins using dual-isotope (87Sr/86Sr, δ18O) assignment approaches

×

Substantial progress in the application of multiple isotope analyses has greatly improved the ability to identify nonlocal individuals amongst archaeological populations over the past decades. More recently the development of large scale models of spatial isotopic variation (isoscapes) has contributed to improved geographic assignments of human and animal origins. Persistent challenges remain, however, in the accurate identification of individual geographic origins from skeletal isotope data in studies of human (and animal) migration and provenance. In an attempt to develop and test more standardized and quantitative approaches to geographic assignment of individual origins using isotopic data two methods, combining 87Sr/86Sr and δ18O isoscapes, are examined for the Circum-Caribbean region: 1) an Interval approach using a defined range of fixed isotopic variation per location; and 2) a Likelihood assignment approach using univariate and bivariate probability density functions. These two methods are tested with enamel isotope data from a modern sample of known origin from Caracas, Venezuela and further explored with two archaeological samples of unknown origin recovered from Cuba and Trinidad. The results emphasize both the potential and limitation of the different approaches. Validation tests on the known origin sample exclude most areas of the Circum-Caribbean region and correctly highlight Caracas as a possible place of origin with both approaches. The positive validation results clearly demonstrate the overall efficacy of a dual-isotope approach to geoprovenance. The accuracy and precision of geographic assignments may be further improved by better understanding of the relationships between environmental and biological isotope variation; continued development and refinement of relevant isoscapes; and the eventual incorporation of a broader array of isotope proxy data.

Forschungszusammenhang (Projekte)

    Brughmans, Tom; Brandes, Ulrik (2017): Visibility Network Patterns and Methods for Studying Visual Relational Phenomena in Archeology Frontiers in Digital Humanities. 2017, 4, 17. eISSN 2297-2668. Available under: doi: 10.3389/fdigh.2017.00017

Visibility Network Patterns and Methods for Studying Visual Relational Phenomena in Archeology

×

A review of the archeological and non-archeological use of visibility networks reveals the use of a limited range of formal techniques, in particular for representing visibility theories. This paper aims to contribute to the study of complex visual relational phenomena in landscape archeology by proposing a range of visibility network patterns and methods. We propose first- and second-order visibility graph representations of total and cumulative viewsheds, and two-mode representations of cumulative viewsheds. We present network patterns that can be used to represent aspects of visibility theories and that can be used in statistical simulation models to compare theorized networks with observed networks. We argue for the need to incorporate observed visibility network density in these simulation models, by illustrating strong differences in visibility network density in three example landscapes. The approach is illustrated through a brief case study of visibility networks of long barrows in Cranborne Chase.

Forschungszusammenhang (Projekte)

  Athenstädt, Jan C.; Cornelsen, Sabine (2017): Planarity of Overlapping Clusterings Including Unions of Two Partitions Journal of Graph Algorithms and Applications. 2017, 21(6), pp. 1057-1089. eISSN 1526-1719. Available under: doi: 10.7155/jgaa.00450

Planarity of Overlapping Clusterings Including Unions of Two Partitions

×

We consider clustered planarity with overlapping clusters as introduced by Didimo et al. [14]. It can be deduced from a proof in Athenstädt et al. [2] that the problem is NP-complete, even if restricted to instances where the underlying graph is 2-connected, the set of clusters is the union of two partitions and each cluster contains at most two connected components while their complements contain at most three connected components.
In this paper, we show that clustered planarity with overlapping clusters can be solved in polynomial time if each cluster induces a connected subgraph. It can be solved in linear time if the set of clusters is the union of two partitions of the vertex set such that, for each cluster, both the cluster and its complement induce connected subgraphs.

Forschungszusammenhang (Projekte)

  Shafie, Termeh (2016): Analyzing local and global properties of multigraphs The Journal of Mathematical Sociology. 2016, 40(4), pp. 239-264. ISSN 0022-250X. eISSN 1545-5874. Available under: doi: 10.1080/0022250X.2016.1219732

Analyzing local and global properties of multigraphs

×

The local structure of undirected multigraphs under two random multigraph models is analyzed and compared. The first model generates multigraphs by randomly coupling pairs of stubs according to a fixed degree sequence so that edge assignments to vertex pair sites are dependent. The second model is a simplification that ignores the dependency between the edge assignments. It is investigated when this ignorance is justified so that the simplified model can be used as an approximation, thus facilitating the structural analysis of network data with multiple relations and loops. The comparison is based on the local properties of multigraphs given by marginal distribution of edge multiplicities and some local properties that are aggregations of global properties.

Forschungszusammenhang (Projekte)

    Weidele, Daniel; van Garderen, Mereke; Golitko, Mark; Feinman, Gary M.; Brandes, Ulrik (2016): On graphical representations of similarity in geo-temporal frequency data Journal of Archaeological Science. 2016, 72, pp. 105-116. ISSN 0305-4403. eISSN 1095-9238. Available under: doi: 10.1016/j.jas.2016.05.013

On graphical representations of similarity in geo-temporal frequency data

×

Its focus on dependencies and patterns in relational data makes network science a promising addition to the analytic toolbox in archaeology. Despite its tradition in a number of other fields, however, the methodology of network science is only in development and its scope and proper usage are subject to debate. We argue that the historical linkage with graph theory and limitations in commonly available software form an obstacle to leveraging the full potential of network methods. This is illustrated via replication of a study of Maya obsidian (Golitko et al. Antiquity, 2012), in which it seemed necessary to discard detailed information in order to represent data in networks suitable for further processing. We propose means to avoid such information loss by using methods capable of handling valued rather than binarized data. The resulting representations corroborate previous conclusions but are more reliable and thus justify a more detailed interpretation of shifting supply routes as an underlying process contributing to the collapse of Maya urban centers. Some general conclusions for the use of network science in archaeology are offered.

Forschungszusammenhang (Projekte)

    Hart, John P.; Shafie, Termeh; Birch, Jennifer; Dermarkar, Susan; Williamson, Ronald F. (2016): Nation Building and Social Signaling in Southern Ontario : A.D. 1350–1650 PLoS ONE. 2016, 11(5), e0156178. eISSN 1932-6203. Available under: doi: 10.1371/journal.pone.0156178

Nation Building and Social Signaling in Southern Ontario : A.D. 1350–1650

×

Pottery is a mainstay of archaeological analysis worldwide. Often, high proportions of the pottery recovered from a given site are decorated in some manner. In northern Iroquoia, late pre-contact pottery and early contact decoration commonly occur on collars-thick bands of clay that encircle a pot and extend several centimeters down from the lip. These decorations constitute signals that conveyed information about a pot's user(s). In southern Ontario the period A.D. 1350 to 1650 witnessed substantial changes in socio-political and settlement systems that included population movement, coalescence of formerly separate communities into large villages and towns, waxing and waning of regional strife, the formation of nations, and finally the development of three confederacies that each occupied distinct, constricted areas. Social network analysis demonstrates that signaling practices changed to reflect these regional patterns. Networks become more consolidated through time ultimately resulting in a "small world" network with small degrees of separation between sites reflecting the integration of communities within and between the three confederacies.

Forschungszusammenhang (Projekte)

  Evans, William; van Garderen, Mereke; Löffler, Maarten; Polishchuk, Valentin (2016): Recognizing a DOG is Hard, But Not When It is Thin and Unit DEMAINE, Erik D., ed., Fabrizio GRANDONI, ed.. 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz: Wadern : Schloss Dagstuhl, 2016, pp. 16:1-16:12. LIPIcs : Leibniz International Proceedings in Informatics. 49. ISBN 978-3-95977-005-7. Available under: doi: 10.4230/LIPIcs.FUN.2016.16

Recognizing a DOG is Hard, But Not When It is Thin and Unit

×

We define the notion of disk-obedience for a set of disks in the plane and give results for diskobedient graphs (DOGs), which are disk intersection graphs (DIGs) that admit a planar embedding with vertices inside the corresponding disks. We show that in general it is hard to recognize a DOG, but when the DIG is thin and unit (i.e., when the disks are unit disks), it can be done in linear time

Forschungszusammenhang (Projekte)

    Brandes, Ulrik (2016): Network positions Methodological Innovations. 2016, 9, pp. 1-19. eISSN 2059-7991. Available under: doi: 10.1177/2059799116630650

Network positions

×

A formal definition of position in networks is proposed. Based on the conceptualization of networks as data on intersecting dyads, it leads to integrated means of analysis for various kinds of relational and attribute data and to a simultaneous unification and generalization of a wide range of network-analytic methods. In fact, by defining network positions explicitly, various methods can be broken down into sequences of generic steps that are more amenable to substantive theorizing, integration of qualitative insight, and empirical validation.

Forschungszusammenhang (Projekte)

Mittelgeber
Name Finanzierungstyp Kategorie Kennziffer
ERC Drittmittel Forschungsförderprogramm 718/13
Weitere Informationen
Laufzeit: 01.09.2013 – 31.08.2019