PaperlayerView exact revision on arXiv

Source-linked AI summary

Detection of timescales in evolving complex systems

Richard K. Darst, Clara Granell, Alex Arenas, Sergio Gómez, Jari Saramäki, Santo Fortunato

arXiv:1604.00758v1physics.soc-phcs.SI

TL;DR

Understanding evolving complex systems requires intervals that reflect changes in their event landscape, not just activity rates. This paper selects intervals by maximizing similarity between consecutive event sets. Synthetic tests show that the intervals respond to changing event turnover, and the method is presented as a way to place boundaries for subsequent analyses.

  • Problem

    Fast, scalable methods are needed to gain insight into complex systems evolving on varying timescales.

    Source: §II · p. 5

  • Method

    The method automatically slices a system's evolution by locally maximizing Jaccard similarity between consecutive intervals' event sets.

    Source: A. Method for detecting evolutionary… · p. 2, §II · p. 5

  • Results

    On synthetic data, intervals are shorter during faster event change and longer during slower change, while similarity reflects the dynamics.

    Source: B. Validation on synthetic data · p. 3

  • Takeaways & Limitations

    The resulting boundaries can provide segmented data for further analysis while respecting underlying dynamics.

    Source: §II · p. 5

    For periodically repeating, noise-free data, the default preference for the longest timescale can yield an uninformative all-time similarity.

    Source: §1 · p. 8

Abstract

from arXiv · show

Most complex systems are intrinsically dynamic in nature. The evolution of a dynamic complex system is typically represented as a sequence of snapshots, where each snapshot describes the configuration of the system at a particular instant of time. Then, one may directly follow how the snapshots evolve in time, or aggregate the snapshots within some time intervals to form representative "slices" of the evolution of the system configuration. This is often done with constant intervals, whose duration is based on arguments on the nature of the system and of its dynamics. A more refined approach would be to consider the rate of activity in the system to perform a separation of timescales. However, an even better alternative would be to define dynamic intervals that match the evolution of the system's configuration. To this end, we propose a method that aims at detecting evolutionary changes in the configuration of a complex system, and generates intervals accordingly. We show that evolutionary timescales can be identified by looking for peaks in the similarity between the sets of events on consecutive time intervals of data. Tests on simple toy models reveal that the technique is able to detect evolutionary timescales of time-varying data both when the evolution is smooth as well as when it changes sharply. This is further corroborated by analyses of several real datasets. Our method is scalable to extremely large datasets and is computationally efficient. This allows a quick, parameter-free detection of multiple timescales in the evolution of a complex system.

A. Method for detecting evolutionary timescales

The method builds consecutive time slices by choosing each interval to maximize similarity between the event sets in adjacent slices. It seeks long intervals when event identities change slowly and short ones when they change quickly, without requiring input parameters.

A. Method for detecting evolutionary timescales

  • The method requires recurring events and a recording period long enough to capture system evolution.Its intervals are intended to depend on event identities, not event rate, and to shorten or lengthen with the pace of change.Source: A. Method for detecting evolutionary… · p. 2
  • Each next interval is chosen by locally maximizing the Jaccard similarity between its event set and the preceding interval's.The Jaccard index is the fraction of events shared by the two sets relative to their union; the interval increment is increased until the similarity peaks.Source: A. Method for detecting evolutionary… · p. 2
  • Initialization optimizes two intervals together, then discards the second so subsequent slices retain the same meaning.The paper describes this initialization as parameter-free.Source: A. Method for detecting evolutionary… · p. 2
  • For smooth change, the Jaccard peak balances added events shared with the prior slice against new events that enlarge the union.If an abrupt change occurs, a boundary is placed at the snapshot where the anomalous behavior begins.Source: A. Method for detecting evolutionary… · p. 2
  • The method processes data online, retaining only the preceding interval's events, and can scale linearly when intervals are small.The input consists of event-id and time tuples.Source: A. Method for detecting evolutionary… · pp. 2–3

B. Validation on synthetic data

Synthetic tests show that the slices respond to changes in event identities rather than overall event rate. They adapt to smooth changes and place boundaries at abrupt, whole-set changes.

B. Validation on synthetic data

  • Toy examples show that distinct event sets are separated into intervals, while faster evolution yields shorter intervals.Changing the repetition rate without changing the characteristic event set does not change the evolutionary slicing.Source: B. Validation on synthetic data · p. 3, Figure 1 · p. 3
  • On periodic synthetic data, intervals are short during fast event turnover and longer during slow turnover, while inter-interval similarity varies with that pace.The benchmark holds overall event rate constant.Source: B. Validation on synthetic data · p. 3
  • The authors show Shannon entropy within each interval and report that their method produces intervals containing roughly the same amount of information.Source: B. Validation on synthetic data · p. 3
  • At the imposed critical points t = 1200 and t = 1400, interval boundaries fall exactly at the whole-set changes and similarity drops sharply.These points represent instantaneous changes in the active event set.Source: B. Validation on synthetic data · p. 3

C. Analysis of real temporal data

Real-data analyses apply the slicing method to Enron email, Bluetooth proximity, and Twitter hashtag activity. The examples show detected intervals alongside known events or rapid changes in event composition.

C. Analysis of real temporal data

  • For Enron email, the method finds intervals generally spanning several weeks and often aligning with major scandal events.Compared with cpdetect, it reveals a basic weekly evolutionary timescale rather than only major change points; cpdetect requires a basic scale as input.Source: C. Analysis of real temporal data · p. 4, Figure 3 · p. 5
  • In MIT Reality Mining, the method finds an approximately weekly timescale and intervals correlated with some academic-calendar events.At the start and end of the academic year, minimal data volume precludes reliable timescales.Source: C. Analysis of real temporal data · p. 4, Figure 4 · p. 5
  • For Twitter discussion of the UEFA semifinals, intervals become especially short during matches, tracking rapid changes in hashtag topics.The analysis identifies rapid dynamics at the second-half start and game-winning goal.Source: C. Analysis of real temporal data · pp. 4–5

II. DISCUSSION

The method automatically slices system evolution into intervals that track changes in the event landscape. The resulting boundaries can support later analyses that preserve underlying dynamics.

II. DISCUSSION

  • The method automatically divides complex-system evolution into intervals that describe changes in the event landscape.These intervals let the system's evolution be studied through the resulting sequence of slices.Source: §II · p. 5
  • The method places snapshot boundaries at locations with high change rates or at sharp boundaries, unlike fixed divisions that may be suboptimal.The resulting slices can be passed to methods that aggregate them into higher-order structure while respecting underlying dynamics.Source: §II · p. 5
  • In the Champions League Twitter data, topic turnover accelerated around goals and was not simply explained by event rate.The caption identifies goals at 20:53, 21:12 and 21:55.Source: Figure 5 · p. 6

III. MATERIALS AND METHODS

The interval size Δt is searched from the raw data. The paper adopts exponentially spaced intervals as its search strategy.

III. MATERIALS AND METHODS

  • The value of Δt is searched from the raw data to identify an optimum interval.The shortest searched Δt is taken from the next event in the data.Source: §III · p. 6
  • A simple linear search and an event-driven search are both described as inefficient at long timescales.The passage also notes that a linear search suffices.Source: §III · p. 6
  • The adopted strategy searches exponentially spaced intervals.This is presented as the ideal approach among the described strategies.Source: §III · p. 6

A. Temporal benchmark

The temporal benchmark combines periodic changes in event identities with a uniform average event rate. It also tests a critical event that resets the system's event state.

A. Temporal benchmark

  • The benchmark has periodic activity changes while maintaining a uniform event rate.On average, pqN events are expressed at each time step.Source: A. Temporal benchmark · p. 6
  • The benchmark periodically varies the event-ID changeover rate, so event identities change faster at some times than others.The passage attributes longer and shorter intervals to these varying rates of identity change.Source: A. Temporal benchmark · p. 6
  • At a critical event tcrit, the model sets c(tcrit) = 1, producing a state uncorrelated with the previous time.The changeover occurs before the time step, matching placement of a new interval at tcrit under the half-open segment convention.Source: A. Temporal benchmark · p. 7
  • The benchmark uses N = 1000, τ = 500, p = 0.2, q = 0.2, c0 = 0, and c = 0.01.Source: A. Temporal benchmark · p. 7

B. Shannon Entropy

The section gives the Shannon entropy formula for a series of events and their corresponding probabilities.

B. Shannon Entropy

C. Enron temporal data

The Enron dataset contains bidirectional email communications involving approximately 150 senior managers, recorded with daily resolution.

C. Enron temporal data

  • The dataset covers approximately 150 Enron senior managers and their bidirectional email communications.Enron collapsed in 2001 after market manipulation was uncovered, leading to an accounting scandal.Source: C. Enron temporal data · p. 7
  • Each event is an unordered source-destination pair, with the input aggregated by day.A pair's weight is the number of emails sent that day.Source: C. Enron temporal data · p. 7
  • The dataset records email communications to and from each key person at daily resolution.Source: C. Enron temporal data · p. 7

D. Reality mining

This section describes how the method segments event data into adjacent intervals to detect timescales, and how defaults and implementation choices shape that process. It also covers controls for selecting additional timescales and a restart strategy for detecting critical events when similarity-based propagation produces intervals that are too long.

E. UCL hashtags

  • The UCL hashtag dataset covers 30 April–08 May 2015, treating each case-normalized hashtag co-occurring with #UCL, except #UCL itself, as an event.When multiple hashtags co-occur with #UCL, each counts as a separate event; hashtags are interpreted as UTF-8 Unicode.Source: E. UCL hashtags · p. 7

1. Data and timescales

  • By default, the method returns the longest timescale, so noiseless periodic data can yield one interval covering all time and hide within-period structure.A small amount of non-repeating random noise destroys this long-term similarity, allowing a shorter timescale to be detected; shorter-timescale options are available.Source: §1 · pp. 8–9

a. Data and interval representation

  • For each interval, the algorithm aggregates event tuples into either a set of event IDs or a weighted set whose weights sum event counts.The initial interval is selected by maximizing similarity across two adjacent candidate intervals; subsequent intervals are selected against the fixed preceding interval. Optionally merging the first two intervals can help with sharp transitions but changes the first interval's size distribution.Source: a. Data and interval representation · p. 9, a. Initial step: calculating the size… · p. 10

3. Similarity measures

  • Weighted Jaccard can resist rapid interval-size changes, while cosine similarity can score unequal-sized event sets as identical when their relative event-weight distributions match.Similarity scores range from 0 to 1; cosine is more flexible than weighted Jaccard about total event counts.Source: b. Weighted Jaccard · p. 9, §3 · p. 9, c. Cosine similarity · p. 10

4. The slicing process

  • The slicing algorithm uses a one-pass, linear-time process that chooses each next interval width to maximize similarity with the preceding interval.It selects the first width by comparing two candidate adjacent intervals, then fixes the preceding interval and repeats the optimization during propagation.Source: §4 · p. 10, b. Propagation step · p. 11

5. ∆t generation

  • The implemented logarithmic scan adapts to data scale, whereas linear scanning requires suitable step parameters and event-based scanning can be inefficient on large datasets.The authors describe logarithmic scanning as the only fully developed method for use; event-based scanning offers finer alignment with event times.Source: §5 · p. 11, a. Linear scan mode · p. 11, b. Logarithmic scan mode · p. 11

e. Criteria for stopping the ∆t generation

  • The scan continues until tested widths reach 25 times the latest optimum, balancing the risk of missing later peaks against computational efficiency.The multiplier can be lowered for better performance or raised to reduce the risk of missing future peaks.Source: e. Criteria for stopping the ∆t… · p. 12

6. Maximum finding

  • The standard maximum-finding strategy chooses the greatest width among tied maxima; greedy stopping is faster but can stop at a local maximum.When events are statistically self-similar across all time, similarity may keep increasing, making one interval covering all time an appropriate result.Source: a. Longest · p. 12, c. Greedy · p. 12, §6 · p. 12

d. Detecting other timescales

  • Longest and shortest peak finders seek the longest or shortest similar timescales, while greedy stops at the first decrease to select the first local maximum.The method assumes similarity first increases and then decreases; its peak finders do not detect multiple local maxima.Source: d. Detecting other timescales · p. 12
  • The peak factor balances longest and shortest searches by stopping when J(∆tmax) falls below the factor times J(∆t∗).It is implemented only for the “longest” and “shortest” maximum-finding methods.Source: d. Detecting other timescales · p. 12
  • Search controls can adjust the past-peak factor or set search bounds, but these options are not used by default because they require prior knowledge of likely timescales.A minimum search past ∆t = 0 can help avoid extreme fluctuations in J at small ∆t.Source: d. Detecting other timescales · p. 13

e. Critical event detection

  • Critical events cause similarity to remain low or rise without a peak, so propagation can keep extending intervals pointlessly and return intervals that are too long.At such abrupt changes in active events, the initial-step process is preferred over propagation.Source: e. Critical event detection · p. 13
  • Critical-event detection restarts segmentation with the initial-step process when the last-interval similarity exceeds 0.95 of peak similarity and the dataset has not ended.The previous interval is forgotten when a critical event occurs.Source: e. Critical event detection · p. 13

Appendix B: Dataset descriptions

The periodic toy model varies how quickly event identities change, while the Enron description defines the email events and dataset context used in the analysis.

1. Periodic toy model

  • As event identities change faster, detected intervals shorten; when they change more slowly, intervals lengthen.The toy model holds the expected event rate uniform while varying its changeover rate.Source: §1 · p. 13
  • The toy model emits recurring events from N = 1000 IDs, with p setting short-term repetition and c(t) governing long-term changes in active IDs.The model uses q to set the average active-ID fraction; its specified parameters are τ = 500, p = 0.2, q = 0.2, c0 = 0, and c = 0.01.Source: §1 · p. 13
  • At a critical event, setting c(tcrit) = 1 decorrelates the event state from its predecessor while leaving the event-ID universe unchanged.The model places a new interval at tcrit under its half-open interval convention.Source: §1 · p. 13

2. Enron

  • The Enron dataset contains communications involving approximately 150 senior managers and records major company changes during the period leading to the corporation’s collapse.Events are unordered sender–recipient pairs; the data are aggregated by day, with each event weighted by that day’s message count.Source: §2 · pp. 13–14

a. Comparison with the cpdetect method

The comparison finds that cpdetect change points coincide with lower similarity than randomized times, while noting that the two methods produce different kinds of output.

a. Comparison with the cpdetect method

  • cpdetect pre-aggregates data into one-week windows, limiting the accuracy of its change points; this method could provide its initial intervals.The weekly pre-aggregation is not required by the proposed method.Source: a. Comparison with the cpdetect method · p. 14
  • The test statistic is significant at p = 0.0033, indicating that similarity J correlates with the system’s evolutionary timescale.The statistic compares mean interpolated J at cpdetect change points with a distribution from 10^4 randomized point sequences.Source: a. Comparison with the cpdetect method · p. 14
  • The methods’ outputs are not directly comparable: cpdetect returns significant change points, whereas this method produces snapshots distributed across the period.The authors expect J to be below average at change points; low J can indicate change points, while maximizing J selects self-similar intervals.Source: a. Comparison with the cpdetect method · p. 14

3. Reality mining dataset

Reality Mining intervals vary with changes in event identities and align with several academic-calendar dates. In the UCL hashtag data, shorter intervals accompany faster topic turnover during matches and goal sequences.

3. Reality mining dataset

  • The Reality Mining data records ordered device-pair events from 91 subjects, with 1,881,152 readings spanning August 8, 2004, to July 14, 2005.The subjects’ devices recorded nearby devices through Bluetooth; the dataset covers only their personal-device readings, not full ego networks.Source: §3 · p. 14
  • Intervals are shorter during the first weeks of rapid social change and longer during the more stable remainder of the academic year.The slicing also detects Thanksgiving-related travel, boundaries around exam week, and the start of the holiday period.Source: §3 · p. 14
  • Detected segment boundaries align with the start of classes, spring break, and the last day of classes, despite many subjects being research staff.The listed dates are February 1, March 19, and May 12, respectively.Source: §3 · p. 15

4. UCL hashtags

  • During the May 5 and May 6 matches, intervals are more numerous than elsewhere, reflecting faster turnover in discussion topics.For the first game, shorter segments occur around the second-half start and goals; the account also notes stronger audience reaction after the game.Source: §4 · pp. 15–16
  • In the Barcelona–Bayern match, topics and intervals become more active and rapidly changing after the three late goals.The figure caption identifies goals at 22:17, 22:20, and 22:34 and notes an interval boundary at halftime.Source: §4 · p. 16, Figure 7 · p. 17
Loading 1604.00758v1…