Publications
104 results found
Shang F, Chen B, Expert P, et al., 2022, Local dominance unveils clusters in networks, Publisher: arXiv
Clusters or communities can provide a coarse-grained description of complex systems at multiple scales, but their detection remains challenging in practice. Community detection methods often define communities as dense subgraphs, or subgraphs with few connections in-between, via concepts such as the cut, conductance, or modularity. Here we consider another perspective built on the notion of local dominance, where low-degree nodes are assigned to the basin of influence of high-degree nodes, and design an efficient algorithm based on local information. Local dominance gives rises to community centers, and uncovers local hierarchies in the network. Community centers have a larger degree than their neighbors and are sufficiently distant from other centers. The strength of our framework is demonstrated on synthesized and empirical networks with ground-truth community labels. The notion of local dominance and the associated asymmetric relations between nodes are not restricted to community detection, and can be utilised in clustering problems, as we illustrate on networks derived from vector data.
Evans T, Chen B, 2022, Linking the network centrality measures closeness and degree, Communications Physics, Vol: 5, Pages: 1-11, ISSN: 2399-3650
Measuring the importance of nodes in a network with a centrality measure is an core task in any network application. There many measures available and it is speculated that many encode similar information. We give an explicit non-linear relationship between two of the most popular measures of node centrality: degree and closeness. Based on a shortest-path tree approximation, we give an analytic derivation that shows the inverse ofcloseness is linearly dependent on the logarithm of degree. We show that our hypothesis works well for a range of networks produced from stochastic network models and for networks derived from 130 real-world data sets. We connect our results with previous results for other network distance scales such as average distance. Our results imply that measuring closeness is broadly redundant unless our relationship is used to remove the dependence on degree from closeness. The success of our relationship suggests that most networks can be approximated by shortest-path spanning trees which are all statistically similar two or more steps away from their root nodes.
Evans TS, Chen B, 2022, Linking the network centrality measures closeness and degree, Publisher: ArXiv
We propose a non-linear relationship between two of the most importantmeasures of centrality in a network: degree and closeness. Based on ashortest-path tree approximation, we give an analytic derivation that shows theinverse of closeness is linearly dependent on the logarithm of degree. We showthat our hypothesis works well for a range of networks produced from stochasticnetwork models including the Erdos-Reyni and Barabasi-Albert models. We thentest our relation on networks derived from a wide range of real-world dataincluding social networks, communication networks, citation networks, co-authornetworks, and hyperlink networks. We find our relationship holds true within afew percent in most, but not all, cases. We suggest some ways that thisrelationship can be used to enhance network analysis.
Vasiliauskaite V, Evans TS, Expert P, 2022, Cycle analysis of directed acyclic graphs, Physica A: Statistical Mechanics and its Applications, Vol: 596, Pages: 1-22, ISSN: 0378-4371
In this paper, we employ the decomposition of a directed network as an undirected graph plus its associated node meta-data to characterise the cyclic structure found in directed networks by finding a Minimal Cycle Basis of the undirected graph and augmenting its components with direction information. We show that only four classes of directed cycles exist, and that they can be fully distinguished by the organisation and number of source–sink node pairs and their antichain structure. We are particularly interested in Directed Acyclic Graphs and introduce a set of metrics that characterise the Minimal Cycle Basis using the Directed Acyclic Graphs meta-data information. In particular, we numerically show that transitive reduction stabilises the properties of Minimal Cycle Bases measured by the metrics we introduced while retaining key properties of the Directed Acyclic Graph. This makes the metrics a consistent characterisation of Directed Acyclic Graphs and the systems they represent. We measure the characteristics of the Minimal Cycle Bases of four models of transitively reduced Directed Acyclic Graphs and show that the metrics introduced are able to distinguish the models and are sensitive to their generating mechanisms.
Yao Q, Evans T, Chen B, et al., 2021, Higher-order temporal network effects through triplet evolution, Scientific Reports, Vol: 11, Pages: 1-17, ISSN: 2045-2322
We study the evolution of networks through ‘triplets’ — three-node graphlets. We develop a method to compute a transitionmatrix to describe the evolution of triplets in temporal networks. To identify the importance of higher-order interactions inthe evolution of networks, we compare both artificial and real-world data to a model based on pairwise interactions only.The significant differences between the computed matrix and the calculated matrix from the fitted parameters demonstratethat non-pairwise interactions exist for various real-world systems in space and time, such as our data sets. Furthermore,this also reveals that different patterns of higher-order interaction are involved in different real-world situations.To test our approach, we then use these transition matrices as the basis of a link prediction algorithm. We investigate ouralgorithm’s performance on four temporal networks, comparing our approach against ten other link prediction methods.Our results show that higher-order interactions in both space and time play a crucial role in the evolution of networks as wefind our method, along with two other methods based on non-local interactions, give the best overall performance. Theresults also confirm the concept that the higher-order interaction patterns, i.e., triplet dynamics, can help us understandand predict the evolution of different real-world systems.
Rivers R, Evans T, 2020, How do we avoid imposing the present on the past when modelling spatial interactions?, Documenta Praehistorica, Vol: 47, Pages: 462-475, ISSN: 1318-6701
Theoretical archaeological modelling for describing spatial interactions often adopts contemporary socioeconomic ideas whose C20th language gets translated into historical behaviour with the simplest of lexicons. This can lead to the impression that the past is like the present. Our intention in this paper is that, when this happens, to strip out as much of the contemporary context as we can, to bring modelling back to basic epistemic propositions. We suggest that although the underlying ontology may be specific to contemporary society the epistemology has much greater generality, leading to essentially the same conclusions without the carapace of intricate economics.
Hilton B, Sood AP, Evans TS, 2020, Predictive limitations of spatial interaction models: a non-Gaussian analysis, Scientific Reports, ISSN: 2045-2322
We present a method to compare spatial interaction models against data basedon well known statistical measures which are appropriate for such models anddata. We illustrate our approach using a widely used example: commuting data,specifically from the US Census 2000. We find that the radiation model performssignificantly worse than an appropriately chosen simple gravity model. Variousconclusions are made regarding the development and use of spatial interactionmodels, including: that spatial interaction models fit badly to data in anabsolute sense, that therefore the risk of over-fitting is small and addingadditional fitted parameters improves the predictive power of models, and thatappropriate choices of input data can improve model fit.
Evans TS, Calmon L, Vasiliauskaite V, 2020, Longest path in the price model, Scientific Reports, Vol: 10, Pages: 1-9, ISSN: 2045-2322
The Price model, the directed version of the Barab\'{a}si-Albert model,produces a growing directed acyclic graph. We look at variants of the model inwhich directed edges are added to the new vertex in one of two ways: usingcumulative advantage (preferential attachment) choosing vertices in proportionto their degree, or with random attachment in which vertices are chosenuniformly at random. In such networks, the longest path is well defined and insome cases is known to be a better approximation to geodesics than the shortestpath. We define a reverse greedy path and show both analytically andnumerically that this scales with the logarithm of the size of the network witha coefficient given by the number of edges added using random attachment. Thisis a lower bound on the length of the longest path to any given vertex and weshow numerically that the longest path also scales with the logarithm of thesize of the network but with a larger coefficient that has some weak dependenceon the parameters of the model.
Falkenberg M, Lee J-H, Amano S-I, et al., 2020, Identifying time dependence in network growth, Physical Review & Research International, Vol: 2, Pages: 023352 – 1-023352 – 17, ISSN: 2231-1815
Identifying power-law scaling in real networks—indicative of preferential attachment—has proved controversial. Critics argue that measuring the temporal evolution of a network directly is better than measuring the degree distribution when looking for preferential attachment. However, many of the established methods do not account for any potential time dependence in the attachment kernels of growing networks, or methods assume that node degree is the key observable determining network evolution. In this paper, we argue that these assumptions may lead to misleading conclusions about the evolution of growing networks. We illustrate this by introducing a simple adaptation of the Barabási-Albert model, the “k2 model,” where new nodes attach to nodes in the existing network in proportion to the number of nodes one or two steps from the target node. The k2 model results in time dependent degree distributions and attachment kernels, despite initially appearing to grow as linear preferential attachment, and without the need to include explicit time dependence in key network parameters (such as the average out-degree). We show that similar effects are seen in several real world networks where constant network growth rules do not describe their evolution. This implies that measurements of specific degree distributions in real networks are likely to change over time.
Ciacci A, Falkenberg M, Manani KA, et al., 2020, Understanding the transition from paroxysmal to persistent atrial fibrillation, Physical Review Research, Vol: 2, Pages: 023311-023311
Atrial fibrillation (AF) is the most common cardiac arrhytmia, characterisedby the chaotic motion of electrical wavefronts in the atria. In clinicalpractice, AF is classified under two primary categories: paroxysmal AF, shortintermittent episodes separated by periods of normal electrical activity, andpersistent AF, longer uninterrupted episodes of chaotic electrical activity.However, the precise reasons why AF in a given patient is paroxysmal orpersistent is poorly understood. Recently, we have introduced the percolationbased Christensen-Manani-Peters (CMP) model of AF which naturally exhibits bothparoxysmal and persistent AF, but precisely how these differences emerge in themodel is unclear. In this paper, we dissect the CMP model to identify the causeof these different AF classifications. Starting from a mean-field model wherewe describe AF as a simple birth-death process, we add layers of complexity tothe model and show that persistent AF arises from the formation of temporallystable structural re-entrant circuits that form from the interaction ofwavefront collisions during paroxysmal AF. These results are compatible withrecent findings suggesting that the formation of re-entrant drivers in fibroticborder zones perpetuates persistent AF.
Vasiliauskaite V, Evans TS, 2020, Making communities show respect for order, Applied Network Science, Vol: 5, Pages: 1-24, ISSN: 2364-8228
In this work we give a community detection algorithm in which the communities both respects the intrinsic order of a directed acyclic graph and also finds similar nodes. We take inspiration from classic similarity measures of bibliometrics, used to assess how similar two publications are, based on their relative citation patterns. We study the algorithm’s performance and antichain properties in artificial models and in real networks, such as citation graphs and food webs. We show how well this partitioning algorithm distinguishes and groups together nodes of the same origin (in a citation network, the origin is a topic or a research field). We make the comparison between our partitioning algorithm and standard hierarchical layering tools as well as community detection methods. We show that our algorithm produces different communities from standard layering algorithms.
Wilkinson J, Emms T, Evans TS, 2019, Dynamical analysis of spatial interaction models, Publisher: arXiv
We develop a novel dynamical method to examine spatial interaction models(SIMs). For each SIM, we use our dynamical framework to model emigrationpatterns. We look at the resulting population distributions to see if they arerealistic or not. We use the US census data from 2010 and various spatialstatistics to access the success or failure of each model. While we looked atover eighty different SIMs, we will focus here on two examples: the productionconstrained gravity model and the Radiation model. The results suggest that allthese models fail to produce realistic population distributions and we identifythe flaws within existing models. This leads us to suggest that we shoulddefine site attractiveness in terms of a second short range SIM leading to anew spatial interaction model - the Two-Trip model - which offers significantimprovements when examined via our method. We also note that our Two-Tripadaptation can be used in any spatial modelling contexts, not just emigration.
Chen B, Lin Z, Evans T, 2019, The Wikipedia Network of Mathematicians
This is data used in the paper "Analysis of the Wikipedia Network of Mathematicians". The data is taken from three snapshots of Wikipedia, taken in 2013, 2017 and 2018. It contains the raw Wikipedia data used as our source as well the results of our processing. Includes are edgelists, networks of the largest comopnent in graphml format, and tables of data on the nodes (the mathematicians). We have also included an appendix for the EPJ version of the paper, mathematiciansEPJappendix.pdf. However a complete version of this work is also at arXiv:1902.07622
Yao Q, Evans TS, Christensen K, 2019, How the network properties of shareholders vary with investor type and country, PLoS One, Vol: 14, Pages: 1-19, ISSN: 1932-6203
We construct two examples of shareholder networks in which shareholders are connected if they have shares in the same company. We do this for the shareholders in Turkish companies and we compare this against the network formed from the shareholdings in Dutch companies. We analyse the properties of these two networks in terms of the different types of shareholder. We create a suitable randomised version of these networks to enable us to find significant features in our networks. For that we find the roles played by different types of shareholder in these networks, and also show how these roles differ in the two countries we study.
Vasiliauskaite V, Evans TS, 2019, Social success of perfumes, PLoS ONE, Vol: 14, ISSN: 1932-6203
We study data on perfumes and their odour descriptors-notes-to understand how note compositions, called accords, influence successful fragrance formulas. We obtain accords which tend to be present in perfumes that receive significantly more customer ratings. Our findings show that the most popular notes and the most over-represented accords are different to those that have the strongest effect to the perfume ratings. We also used network centrality to understand which notes have the highest potential to enhance note compositions. We find that large degree notes, such as musk and vanilla as well as generically-named notes, e.g. floral notes, are amongst the notes that enhance accords the most. This work presents a framework which would be a timely tool for perfumers to explore a multidimensional space of scent compositions.
Patel VM, Panzarasa P, Ashrafian H, et al., 2019, Collaborative patterns, authorship practices and scientific success in biomedical research: a network analysis., Journal of the Royal Society of Medicine, Vol: 112, Pages: 245-257, ISSN: 1758-1095
OBJECTIVE: To investigate the relationship between biomedical researchers' collaborative and authorship practices and scientific success. DESIGN: Longitudinal quantitative analysis of individual researchers' careers over a nine-year period. SETTING: A leading biomedical research institution in the United Kingdom. PARTICIPANTS: Five hundred and twenty-five biomedical researchers who were in employment on 31 December 2009. MAIN OUTCOME MEASURES: We constructed the co-authorship network in which nodes are the researchers, and links are established between any two researchers if they co-authored one or more articles. For each researcher, we recorded the position held in the co-authorship network and in the bylines of all articles published in each three-year interval and calculated the number of citations these articles accrued until January 2013. We estimated maximum likelihood negative binomial panel regression models. RESULTS: Our analysis suggests that collaboration sustained success, yet excessive co-authorship did not. Last positions in non-alphabetised bylines were beneficial for higher academic ranks but not for junior ones. A professor could witness a 20.57% increase in the expected citation count if last-listed non-alphabetically in one additional publication; yet, a lecturer suffered from a 13.04% reduction. First positions in alphabetised bylines were positively associated with performance for junior academics only. A lecturer could experience a 8.78% increase in the expected citation count if first-listed alphabetically in one additional publication. While junior researchers amplified success when brokering among otherwise disconnected collaborators, senior researchers prospered from socially cohesive networks, rich in third-party relationships. CONCLUSIONS: These results help biomedical scientists shape successful careers and research institutions develop effective assessment and recruitment policies that will ultimately sustain the quality of biomedical r
Chen B, Lin Z, Evans TS, 2019, Analysis of the Wikipedia network of mathematicians, Publisher: arXiv
We look at the network of mathematicians defined by the hyperlinks betweentheir biographies on Wikipedia. We show how to extract this information usingthree snapshots of the Wikipedia data, taken in 2013, 2017 and 2018. Weillustrate how such Wikipedia data can be used by performing a centralityanalysis. These measures show that Hilbert and Newton are the most importantmathematicians. We use our example to illustrate the strengths and weakness ofcentrality measures and to show how to provide estimates of the robustness ofcentrality measurements. In part, we do this by comparison to results from twoother sources: an earlier study of biographies on the MacTutor website and asmall informal survey of the opinion of mathematics and physics students atImperial College London.
Kitromilidis M, Evans TS, 2018, Community detection with metadata in a network of biographies of western art painters, Publisher: arXiv
In this work we look at the structure of the influences between Western artpainters as revealed by their biographies on Wikipedia. We use a modifiedversion of modularity maximisation with metadata to detect a partition ofartists into communities based on their artistic genre and school in which theybelong. We then use this community structure to discuss how influential artistsreached beyond their own communities and had a lasting impact on others, byproposing modifications on standard centrality measures.
Clough JR, Evans TS, 2017, Embedding graphs in Lorentzian spacetime, PLOS ONE, Vol: 12, ISSN: 1932-6203
Geometric approaches to network analysis combine simply defined models with great descriptive power. In this work we provide a method for embedding directed acyclic graphs (DAG) into Minkowski spacetime using Multidimensional scaling (MDS). First we generalise the classical MDS algorithm, defined only for metrics with a Riemannian signature, to manifolds of any metric signature. We then use this general method to develop an algorithm which exploits the causal structure of a DAG to assign space and time coordinates in a Minkowski spacetime to each vertex. As in the causal set approach to quantum gravity, causal connections in the discrete graph correspond to timelike separation in the continuous spacetime. The method is demonstrated by calculating embeddings for simple models of causal sets and random DAGs, as well as real citation networks. We find that the citation networks we test yield significantly more accurate embeddings that random DAGs of the same size. Finally we suggest a number of applications in citation analysis such as paper recommendation, identifying missing citations and fitting citation models to data using this geometric approach.
Evans TS, Rivers RJ, 2017, Was Thebes necessary? Contingency in spatial modeling, Frontiers in Digital Humanities, Vol: 4, ISSN: 2297-2668
When data are poor, we resort to theory modeling. This is a two-step process. We have first to identify the appropriate type of model for the system under consideration and then to tailor it to the specifics of the case. To understand settlement formation, which is the concern of this article, this involves choosing not only input parameter values such as site separations but also input functions that characterizes the ease of travel between sites. Although the generic behavior of the model is understood, the details are not. Different choices will necessarily lead to different outputs (for identical inputs). We can only proceed if choices that are “close” give outcomes that are similar. Where there are local differences, it suggests that there was no compelling reason for one outcome rather than the other. If these differences are important for the historic record, we may interpret this as sensitivity to contingency. We re-examine the rise of Greek city-states as first formulated by Rihll and Wilson in 1979, initially using the same “retail” gravity model. We suggest that, although cities like Athens owe their position to a combination of geography and proximity to other sites, the rise of Thebes is the most contingent, whose success reflects social forces outside the grasp of simple network modeling.
Clough JR, Evans TS, 2015, What is the dimension of citation space?, Physica A, 448 (2016) 235-247
Citation networks represent the flow of information between agents. They areconstrained in time and so form directed acyclic graphs which have a causalstructure. Here we provide novel quantitative methods to characterise thatstructure by adapting methods used in the causal set approach to quantumgravity by considering the networks to be embedded in a Minkowski spacetime andmeasuring its dimension using Myrheim-Meyer and Midpoint-scaling estimates. Weillustrate these methods on citation networks from the arXiv, supreme courtjudgements from the USA, and patents and find that otherwise similar citationnetworks have measurably different dimensions. We suggest that thesedifferences can be interpreted in terms of the level of diversity or narrownessin citation behaviour.
Goldberg SR, Anthony H, Evans TS, 2015, Modelling citation networks, SCIENTOMETRICS, Vol: 105, Pages: 1577-1604, ISSN: 0138-9130
- Author Web Link
- Cite
- Citations: 27
Goldberg SR, Anthony H, Evans TS, 2015, Modelling citation networks, Scientometrics, ISSN: 1588-2861
Clough JR, Gollings J, Loach TV, et al., 2015, Transitive reduction of citation networks, Journal of Complex Networks, Vol: 3, Pages: 189-203, ISSN: 2051-1310
In many complex networks, the vertices are ordered in time, and edges represent causal connections. We propose methods of analysing such directed acyclic graphs taking into account the constraints of causality and highlighting the causal structure. We illustrate our approach using citation networks formed from academic papers, patents and US Supreme Court verdicts. We show how transitive reduction (TR) reveals fundamental differences in the citation practices of different areas, how it highlights particularly interesting work, and how it can correct for the effect that the age of a document has on its citation count. Finally, we transitively reduce null models of citation networks with similar degree distributions and show the difference in degree distributions after TR to illustrate the lack of causal structure in such models.
Clough JR, Evans TS, 2015, Time & Citation Networks, 15th International Conference of the International-Society-for-Scientometrics-and-Informetrics (ISSI) on Scientometrics and Informetrics, Publisher: INT SOC SCIENTOMETRICS & INFORMETRICS-ISSI, Pages: 1073-1078, ISSN: 2175-1935
Loach TV, Evans TS, 2015, Ranking Journals Using Altmetrics, 15th International Conference of the International-Society-for-Scientometrics-and-Informetrics (ISSI) on Scientometrics and Informetrics, Publisher: INT SOC SCIENTOMETRICS & INFORMETRICS-ISSI, Pages: 89-94, ISSN: 2175-1935
- Author Web Link
- Cite
- Citations: 2
Goldberg SR, Anthony H, Evans TS, 2015, Do We Need Global and Local Knowledge of the Citation Network?, 15th International Conference of the International-Society-for-Scientometrics-and-Informetrics (ISSI) on Scientometrics and Informetrics, Publisher: INT SOC SCIENTOMETRICS & INFORMETRICS-ISSI, Pages: 282-283, ISSN: 2175-1935
Evans T, Lambiotte R, 2014, LineGraphCreator
This is code to implement our weighted line graphs, i.e. graphs whose nodes are the edges of the original graph which aslo capture the correct dynamical features of the original network. Weighted line graphs provide an alternative, valuable representation of the system's topology, and have important applications in community detection. The usual node partition of a line graph naturally leads to an edge partition of the original graph. This identification allows us to use traditional partitioning methods in order to address the long-standing problem of the detection of overlapping communities.Here we provide our simple C++ line graph code which takes in a graph as an edge list and outputs different types of line graph as another edge list. An executable suitable for most Windows machines is included as is basic documentation. This code been used successfully on a graph which produced 5.5e8 stubs in its line graph, though a special machine was used for this as it needs more than 4Gb of RAM memory. On a 4Gb machine a line graph with 4.5e7 stubs was created.We also have java based code which is part of a much bigger package.Discussions, papers and slides from talks:-Paper: Line Graphs, Link Partitions and Overlapping Communities, Phys.Rev.E 80 (2009) 016105 [arXiv:0903.2181].Conference Paper: Overlapping Communities, Link Partitions and Line Graphs, a very slightly altered version forECCS09.Slides from talk What am I? Finding Communities in Networks Using Line Graphs given at University of Warwick Complexity Forum, 28thOctober 2009.Slides from talk Overlapping Communities, Edge Partitions and Line Graphs given at ECCS09 (University of Warwick, 22nd September 2009).Paper: Edge Partitions and Overlapping Communities in Complex Networks, Eur. Phys. J. B 2010, 77, 265–272 [arXiv:0912.4389]. This covers in more detail the case where one is interested in the different line graphs of a weighted graph.Input used for the Les Miserable network and the correpsonding outputs
Evans T, 2014, The Connected Past London 2014
A collection of material associated with The Connected Past London 2014, a one and a half day multi-disciplinary meeting held at Imperial College on the 8th and 9th of September, 2014 and attended by nearly fifty researchers. It aims to explore how concepts and techniques from network- and complexity science can be used to study archaeological and historical data. It is part of a series of meetings organised by The Connected Past team.Slides from most (but not all) talks are provided. Most talks were also recorded but the videos are yet to be made available.
Evans TS, Rivers RJ, 2014, New approaches to Archaic Greek Settlement Structure, Les Nouvelles de l'archéologie, Vol: 135, Pages: 21-27, ISSN: 0242-7702
Recent developments in network theory have led to the creation of new Spatial Interaction Models (SIMs) and a reappraisal of existing models. Although not directed at the archaeology community, these models generalise the familiar gravitational models and Proximal Point Analysis (PPA) used by archaeologists for many years to help explain the archaeological record. However, a problem arises in archaeology that, with the increasing suite of plausible models that now exist, it is unclear how to choose one model over another. This can lead to the criticism that, if we hunt hard enough, we may be doing no more than finding a model which can be manipulated to conform to our preconceptions. In recent articles we have begun to address this criticism (Evans 2014, in press) with particular reference to the maritime networks of the MBA Aegean (Rivers 2014, in press). Different historical periods require different approaches and in this paper we continue this analysis by re-examining the onset of centralisation in mainland Greek city states of the 9th and 8th centuries BCE. Pioneering work on this archaic settlement structure was performed in 1987 by Rihll and Wilson (Rihll & Wilson 1987, 2: 5-32; 1991: 59-95), adapting a 'retail' model devised originally for urban planning. One alternative approach is given by a recent cost-benefit model termed ariadne, developed by ourselves (Evans, Knappett & Rivers 2009, 7: 451-79; Knappett, Evans & Rivers 2008, 82: 1009-84; 2011, 85: 1008-23), initially designed for Bronze Age maritime networks. A comparison of these models and other simpler SIMs for archaic settlements highlights the problems of modelling archaeological data. In particular we examine what constitutes model 'robustness' and the way in which different models handle 'contingency' when handling periods of rapid change.
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.