Publications

An abundance of centrality indices has been proposed which capture the importance of nodes in a network based on different structural features. While there remains a persistent belief that similarities in outcomes of indices is contingent on their technical definitions, a growing body of research shows that structural features affect observed similarities more than technicalities. We conduct a series of experiments on artificial networks to trace the influence of specific structural features on the similarity of indices which confirm previous results in the literature. Our analysis on 1163 real-world networks, however, shows that little of the observations on synthetic networks convincingly carry over to empirical settings. Our findings suggest that although it seems clear that (dis)similarities among centralities depend on structural properties of the network, using correlation type analyses do not seem to be a promising approach to uncover such connections.

Goodness of fit tests for two probabilistic multigraph models are presented. The first model is random stub matching given fixed degrees (RSM) so that edge assignments to vertex pair sites are dependent, and the second is independent edge assignments (IEA) according to a common probability distribution. Tests are performed using goodness of fit measures between the edge multiplicity sequence of an observed multigraph, and the expected one according to a simple or composite hypothesis. Test statistics of Pearson type and of likelihood ratio type are used, and the expected values of the Pearson statistic under the different models are derived. Test performances based on simulations indicate that even for small number of edges, the null distributions of both statistics are well approximated by their asymptotic χ2-distribution. The non-null distributions of the test statistics can be well approximated by proposed adjusted χ2-distributions used for power approximations. The influence of RSM on both test statistics is substantial for small number of edges and implies a shift of their distributions towards smaller values compared to what holds true for the null distributions under IEA. Two applications on social networks are included to illustrate how the tests can guide in the analysis of social structure.

Multivariate networks comprising several compositional and structural variables can be represented as multigraphs by various forms of aggregations based on vertex attributes. We propose a framework to perform exploratory and confirmatory multiplexity analysis of aggregated multigraphs in order to find relevant associations between vertex and edge attributes. The exploration is performed by comparing frequencies of the different edges within and between aggregated vertex categories, while the confirmatory analysis is performed using derived complexity or multiplexity statistics under different random multigraph models. These statistics are defined by the distribution of edge multiplicities and provide information on the covariation and dependencies of different edges given vertex attributes. The presented approach highlights the need to further analyse and model structural dependencies with respect to edge entrainment. We illustrate the approach by applying it on a well known multivariate network dataset which has previously been analysed in the context of multiplexity.

Reconstructing ties between archaeological contexts may contribute to explain and describe a variety of past social phenomena. Several models have been formulated to infer the structure of such archaeological networks. The applicability of these models in diverse archaeological contexts is limited by the restricted set of assumptions that fully determine the mathematical formulation of the models and are often articulated on a dyadic basis. Here, we present a general framework in which we combine exponential random graph models with archaeological substantiations of mechanisms that may be responsible for network formation. This framework may be applied to infer the structure of ancient networks in a large variety of archaeological settings. We use data collected over a set of sites in the Caribbean during the period AD 100–400 to illustrate the steps to obtain a network reconstruction.

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.

Random multigraphs with fixed degrees are obtained by the configuration model or by so called random stub matching. New combinatorial results are given for the global probability distribution of edge multiplicities and its marginal local distributions of loops and edges. The number of multigraphs on triads is determined for arbitrary degrees, and aggregated triads are shown to be useful for analyzing regular and almost regular multigraphs. Relationships between entropy and complexity are given and numerically illustrated for multigraphs with different number of vertices and specified average and variance for the degrees.

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.

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.

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.

Graphs can be used as a model for online social networks. In this framework, vertices represent individuals and edges relationships between individuals. In recent years, different approaches have been considered to offer data privacy to online social networks and for developing graph protection. Perturbative approaches are formally defined in terms of perturbation and modification of graphs. In this paper, we discuss the concept of P -stability on graphs and its relation to data privacy. The concept of P -stability is rooted in the number of graphs given a fixed degree sequence. In this paper, we show that for any graph there exists a class of P -stable graphs. This result implies that there is a fully polynomial randomized approximation for graph masking for the graphs in the class. In order to further refine the classification of a given graph, we introduce the concept of natural class of a graph. It is based on a class of scale-free networks.

Multigraphs with numerical or qualitative attributes defined on vertices and edges can benefit from systematic methods based on multivariate entropies for describing and analysing the interdependencies that are present between vertex and edge attributes. This is here illustrated by application of these tools to a subset of data on the social relations among Renaissance Florentine families collected by John Padgett. Using multivariate entropies we show how it is possible to systematically check for tendencies in data that can be described as independencies or conditional independencies, or as dependencies allowing certain combinations of variables to predict other variables. We also show how different structural models can be tested by divergence measures obtained from the multivariate entropies.

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.

Multigraphs are graphs where multiple edges and edge loops are permitted. The main purpose of this article is to show the versatility of a multigraph approach when analysing social networks. Multigraph data structures are described and it is exemplified how they naturally occur in many contexts but also how they can be constructed by different kinds of aggregation in graphs. Special attention is given to a random multigraph model based on independent edge assignments to sites of vertex pairs and some useful measures of the local and global structure under this model are presented. Further, it is shown how some general measures of simplicity and complexity of multigraphs are easily handled under the present model.

An abundance of centrality indices has been proposed which capture the importance of nodes in a network based on different structural features. While there remains a persistent belief that similarities in outcomes of indices is contingent on their technical definitions, a growing body of research shows that structural features affect observed similarities more than technicalities. We conduct a series of experiments on artificial networks to trace the influence of specific structural features on the similarity of indices which confirm previous results in the literature. Our analysis on 1163 real-world networks, however, shows that little of the observations on synthetic networks convincingly carry over to empirical settings. Our findings suggest that although it seems clear that (dis)similarities among centralities depend on structural properties of the network, using correlation type analyses do not seem to be a promising approach to uncover such connections.

Goodness of fit tests for two probabilistic multigraph models are presented. The first model is random stub matching given fixed degrees (RSM) so that edge assignments to vertex pair sites are dependent, and the second is independent edge assignments (IEA) according to a common probability distribution. Tests are performed using goodness of fit measures between the edge multiplicity sequence of an observed multigraph, and the expected one according to a simple or composite hypothesis. Test statistics of Pearson type and of likelihood ratio type are used, and the expected values of the Pearson statistic under the different models are derived. Test performances based on simulations indicate that even for small number of edges, the null distributions of both statistics are well approximated by their asymptotic χ2-distribution. The non-null distributions of the test statistics can be well approximated by proposed adjusted χ2-distributions used for power approximations. The influence of RSM on both test statistics is substantial for small number of edges and implies a shift of their distributions towards smaller values compared to what holds true for the null distributions under IEA. Two applications on social networks are included to illustrate how the tests can guide in the analysis of social structure.

Multivariate networks comprising several compositional and structural variables can be represented as multigraphs by various forms of aggregations based on vertex attributes. We propose a framework to perform exploratory and confirmatory multiplexity analysis of aggregated multigraphs in order to find relevant associations between vertex and edge attributes. The exploration is performed by comparing frequencies of the different edges within and between aggregated vertex categories, while the confirmatory analysis is performed using derived complexity or multiplexity statistics under different random multigraph models. These statistics are defined by the distribution of edge multiplicities and provide information on the covariation and dependencies of different edges given vertex attributes. The presented approach highlights the need to further analyse and model structural dependencies with respect to edge entrainment. We illustrate the approach by applying it on a well known multivariate network dataset which has previously been analysed in the context of multiplexity.

Reconstructing ties between archaeological contexts may contribute to explain and describe a variety of past social phenomena. Several models have been formulated to infer the structure of such archaeological networks. The applicability of these models in diverse archaeological contexts is limited by the restricted set of assumptions that fully determine the mathematical formulation of the models and are often articulated on a dyadic basis. Here, we present a general framework in which we combine exponential random graph models with archaeological substantiations of mechanisms that may be responsible for network formation. This framework may be applied to infer the structure of ancient networks in a large variety of archaeological settings. We use data collected over a set of sites in the Caribbean during the period AD 100–400 to illustrate the steps to obtain a network reconstruction.

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.

Random multigraphs with fixed degrees are obtained by the configuration model or by so called random stub matching. New combinatorial results are given for the global probability distribution of edge multiplicities and its marginal local distributions of loops and edges. The number of multigraphs on triads is determined for arbitrary degrees, and aggregated triads are shown to be useful for analyzing regular and almost regular multigraphs. Relationships between entropy and complexity are given and numerically illustrated for multigraphs with different number of vertices and specified average and variance for the degrees.

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.

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.

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.

Graphs can be used as a model for online social networks. In this framework, vertices represent individuals and edges relationships between individuals. In recent years, different approaches have been considered to offer data privacy to online social networks and for developing graph protection. Perturbative approaches are formally defined in terms of perturbation and modification of graphs. In this paper, we discuss the concept of P -stability on graphs and its relation to data privacy. The concept of P -stability is rooted in the number of graphs given a fixed degree sequence. In this paper, we show that for any graph there exists a class of P -stable graphs. This result implies that there is a fully polynomial randomized approximation for graph masking for the graphs in the class. In order to further refine the classification of a given graph, we introduce the concept of natural class of a graph. It is based on a class of scale-free networks.

Multigraphs with numerical or qualitative attributes defined on vertices and edges can benefit from systematic methods based on multivariate entropies for describing and analysing the interdependencies that are present between vertex and edge attributes. This is here illustrated by application of these tools to a subset of data on the social relations among Renaissance Florentine families collected by John Padgett. Using multivariate entropies we show how it is possible to systematically check for tendencies in data that can be described as independencies or conditional independencies, or as dependencies allowing certain combinations of variables to predict other variables. We also show how different structural models can be tested by divergence measures obtained from the multivariate entropies.

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.

Multigraphs are graphs where multiple edges and edge loops are permitted. The main purpose of this article is to show the versatility of a multigraph approach when analysing social networks. Multigraph data structures are described and it is exemplified how they naturally occur in many contexts but also how they can be constructed by different kinds of aggregation in graphs. Special attention is given to a random multigraph model based on independent edge assignments to sites of vertex pairs and some useful measures of the local and global structure under this model are presented. Further, it is shown how some general measures of simplicity and complexity of multigraphs are easily handled under the present model.