I/O Efficient Early Bursting Cohesive Subgraph Discovery in Massive Temporal Networks

Temporal networks are an effective way to encode temporal information into graph data losslessly.Finding the bursting cohesive subgraph(BCS),which accumulates its cohesiveness at the fastest rate,is an important problem in temporal networks.The BCS has a large number of applications,such as representing emergency events in social media,traffic congestion in road networks and epidemic outbreak in communities.Nevertheless,existing methods demand the BCS lasting for a time interval,which neglects the timeliness of the BCS.In this paper,we design an early bursting cohesive subgraph(EBCS)model based on the k-core to enable identifying the burstiness as soon as possible.To find the EBCS,we first construct a time weight graph(TWG)to measure the bursting level by integrating the topological and temporal information.Then,we propose a global search algorithm,called GS-EBCS,which can find the exact EBCS by iteratively removing nodes from the TWG.Further,we propose a local search algorithm,named LS-EBCS,to find the EBCS by first expanding from a seed node until obtaining a candidate k-core and then refining the k-core to the result subgraph in an optimal time complexity.Subsequently,considering the situation that the massive temporal networks cannot be completely put into the memory,we first design an I/O method to build the TWG and then develop I/O efficient global search and local search algorithms,namely I/O-GS and I/O-LS respectively,to find the EBCS under the semi-external model.Extensive experiments,conducted on four real temporal networks,demonstrate the efficiency and effectiveness of our proposed algorithms.For example,on the DBLP dataset,I/O-LS and LS-EBCS have comparable running time,while the maximum memory usage of I/O-LS is only 6.5 MB,which is much smaller than that of LS-EBCS taking 308.7 MB.

Are our phylomorphospace plots so terribly tangled?An investigation of disorder in data simulated under adaptive and nonadaptive models

Contemporary methods for visualizing phenotypic evolution,such as phylomorphospaces,often reveal patter ns which depart strongly from a naive expectation of con siste ntly divergent branchi ng and expansion.Instead,branches regularly crisscross as convergence,reversals,or other forms of homoplasy occur,forming patterns described as"birds'nests","flies in vials",or less elegantly,"a mess".In other words,the phenotypic tree of life often appears highly tangled.Various explanations are given for this,such as differential degrees of developmental constraint,adaptation,or lack of adaptation.However,null expectations for the magnitude of disorder or"tangling"have never been established,so it is unclear which or even whether various evolutionary factors are required to explain messy patter ns of evolution.I simulated evolution along phyloge nies under a number of varying parameters(number of taxa and number of traits)and models(Brownian motion,Ornstein-Uhlenbeck(OU)-based,early burst,and character displacement(CD) and quantified disorder using 2 measures.All models produce substantial amounts of disorder.Disorder increases with tree size and the number of phenotypic traits.OU models produced the largest amounts of disorder-adaptive peaks influence lineages to evolve within restricted areas,with concomitant in creases in crossing of branches and density of evolution.Large early cha nges in trait values can be important in minimizing disorder.CD consistently produced trees with low(but not absent)disorder.Overall,neither constraints nor a lack of adaptation is required to explain messy phylomorphospaces-both stochastic and deterministic processes can act to produce the tantalizingly tangled phenotypic tree of life.