Representing higher-order dependencies in networks

Introduction

• In shipping data, a ship’s next port depends on its previous stop; HON separates Singapore|Tokyo from Singapore|Shanghai to preserve this distinction.The distinction matters for modeling species introductions because ships can transport species during intermediate stops via partial ballast-water exchanges.Source: Introduction · p. 2
• Prior network approaches assumed fixed second-order dependence or required application-specific algorithm changes, leaving no systematic variable-order representation agnostic to downstream analysis.The cited approaches address higher-order dependencies in processes or specific tasks, rather than providing a general network representation.Source: Introduction · pp. 2–3
• On shipping data, HON doubles accuracy for simulating a ship’s next movement and is higher by one magnitude for three-step simulation than a first-order network.The introduction reports these comparisons as evidence that HON better reflects real-world phenomena.Source: Introduction · p. 3
• HON adds higher-order nodes and edges only where needed and supports existing network-analysis methods without modification.The authors report that these methods produce considerably different and more accurate results on HON than on a first-order network.Source: Introduction · p. 3
• Real-world shipping, web-clickstream, and Weibo data include dependencies up to fifth order, and HON identifies all variable-order dependencies introduced in synthetic data.The introduction says first-order and fixed second-order networks cannot capture some of these dependencies, limiting downstream clustering and ranking analyses.Source: Introduction · p. 3

The higher-order network (HON) representation

• HON encodes variable-order dependencies in nodes representing entity sequences, enabling random walks to capture higher-order patterns while remaining compatible with existing network-analysis algorithms.Variable orders can coexist in one representation, with higher-order dependencies embedded only where necessary.Source: The higher-order network (HON)… · pp. 4–5

Higher-order dependencies in data revealed by HON

• In real data, shipping dependencies reach the fifth order, clickstream dependencies the third, while retweet data show only first-order dependencies.On synthetic data, HON identifies all 30 predefined higher-order dependencies among 400 first-order dependencies, finds no false dependencies beyond the fourth order even with maximum order five, and classifies the others as first-order.Source: Higher-order dependencies in data… · pp. 5–6

Improved accuracy on random walking

• With HON at maximum order five, one-step movement-simulation accuracy doubles that of the first-order network, and three-step simulation is one magnitude more accurate.HON captures higher-order movement patterns that first-order networks forget; the first-order network’s three-step accuracy is almost zero.Source: Improved accuracy on random walking · p. 7

Effects on clustering

• On HON, 45% of ports belong to multiple clusters, and 44 ports (1.7% of all) belong to as many as five clusters.HON captures indirect shipping pathways that first-order clustering ignores; for example, it separates Malta Freeport from Valletta, and MapEquation is unmodified.Source: Effects on clustering · p. 8

Effects on ranking

• With HON as input to PageRank, 26% of web pages change ranking by more than 10% in relative terms, and more than 90% lose PageRank scores.HON captures a loop between snow-photo pages that the first-order network misses; those pages gain 131% and 231% in PageRank scores, respectively.Source: Effects on ranking · pp. 8–9

Scalability of HON

• PageRank and MapEquation run almost two times faster on HON with maximum order two than on the fixed second-order network, and about the same speed with maximum order five.HON with maximum order two has about half as many edges as the fixed second-order network; even at maximum order five, HON has fewer edges while incorporating useful dependencies up to that order.Source: Scalability of HON · pp. 9–10

Discussion

• On global shipping data, HON doubled accuracy for simulating a ship’s next movement and improved three-step simulation accuracy by one magnitude over a first-order network.Its higher-order nodes and edges provide more detailed guidance for simulated movements.Source: Discussion · p. 10
• HON embeds higher-order dependencies only when necessary, making it more compact than fixed-order networks and allowing network-analysis algorithms to run faster.The discussion also notes that fixed second-order dependencies can be limiting.Source: Discussion · p. 10
• Using HON changes random-walk analyses: port clustering captures indirect species-introduction pathways and overlapping invasion sources, while web-page rankings incorporate higher-order browsing patterns.The discussion gives uploading multiple photos as an example of a browsing pattern affecting page rankings.Source: Discussion · p. 10
• HON is compatible with existing network-analysis methods, but split nodes may require postprocessing for interpretation, and parameter choices can affect the resulting network structure.The discussion points to Supplementary Material Note 3 for parameter discussions.Source: Discussion · p. 10
• Future work will extend HON applications to dynamic processes such as network anomaly detection and reduce the number of parameters required.The proposed application is dynamic network anomaly detection [48].Source: Discussion · p. 10

Materials and Methods

• HON construction has two steps: extract supported dependencies that alter next-step probabilities, then add higher-order nodes and rewire edges in the conventional network.The resulting data structure allows existing network-analysis methods to be applied without modification and is generalizable beyond the shipping-traffic example.Source: Materials and Methods · p. 11

Rule extraction

• Rule extraction incrementally extends paths when added history significantly changes next-step probabilities, retaining sufficiently supported rules while allowing different paths to have different dependency orders.Growth stops when minimum support is not met or the maximum order is exceeded.Source: Rule extraction · pp. 11–12

Network wiring

• Network wiring redirects edges to higher-order nodes to provide incoming edges while preserving the sum of edge weights, and points edges built from valid rules to the highest-order available nodes.Since extracted rules initially target first-order nodes, rewiring is repeated across orders to connect edges to the highest possible order.Source: Network wiring · pp. 12–13

Comparison with related methods

• Unlike VOM trees (22–24) used for prediction (49), HON targets network representation; fixed-order and application-specific alternatives do not provide variable-order dependencies for unmodified network tools.VOM trees may include probabilities unnecessary for network representation, lack conditional probabilities needed to connect different orders, and add edges through smoothing; fixed-order models grow exponentially with order, while cited higher-order network methods modify application-specific algorithms.Source: Comparison with related methods · p. 13

• The supplement includes an empirical comparison with the Variable-order Markov (VOM) model.Source: Supplementary Material · p. 13
• The supplement presents Algorithm 1 for rule extraction.Source: Supplementary Material · p. 14
• The supplement presents Algorithm 2 for network wiring.Source: Supplementary figures, tables, and… · p. 38

Representing dependencies

• A ship’s next step from Singapore depends on its arrival path, which HON represents with variable orders of dependencies from first to fourth order.The representation can extend to higher orders.Source: Figures and Tables · p. 18, Figure 1 · p. 18

Random-walking accuracy

• HON doubles next-step random-walking accuracy and improves accuracy by one magnitude over the next three steps versus a first-order network.The test holds the last three trajectory steps out, then compares three-step random walks with the ground truth.Source: Figure 2 · p. 19

Clustering ports

• HON clustering distinguishes Malta Freeport as an international port whose overlapping clusters indicate potential species-invasion sources, unlike first-order clustering.The clustering uses MapEquation; the first-order result does not distinguish Valletta from Malta Freeport.Source: Figure 3 · p. 20

PageRank changes

• 26% of web pages change PageRank by more than 10%, while more than 90% lose PageRank scores when using HON instead of a first-order network.Other pages show remarkable gains; the figure uses a log-log scale, where deviations from the diagonal indicate significant score changes.Source: Figures and Tables · p. 21, Figure 4 · p. 21

Clickstream rankings

• For clickstream data, HON represents repeated photo viewing and uploading as a loop, making those pages more likely to receive higher PageRank than under the first-order representation.The implicit PageRank random walkers are more likely to be trapped in the loop of higher-order nodes.Source: Figure 5 · p. 22

1 Data sets

• The LMIU shipping sample spans May 1, 2012–April 30, 2013, with 3,415,577 voyages by 65,591 ships across 4,108 ports and regions; minimum support is 10.The data were made available by Lloyd’s Maritime Intelligence Unit.Source: §1 · p. 24
• The clickstream sample covers December 4, 2012–February 3, 2013: 3,047,697 page views by 179,178 IP addresses across 45,257 pages, with crawler-like streams omitted and minimum support 5.The logs cover 50 company-owned news sites.Source: §1 · p. 24
• The 2012 Weibo retweet history records 23,755,810 retweets involving 1,776,950 users [50].The data records who retweeted whose messages and when.Source: §1 · p. 24
• Synthetic shipping trajectories comprise 10,000,000 movements by 100,000 ships, each moving 100 steps among 100 ports arranged as a wrapping 10×10 grid.Ships normally choose up, down, left, or right with equal probability.Source: §1 · p. 24
• To create variable-order dependencies, the synthetic data define 10 rules each at orders two, three, and four, including a second-order rule with 70% and 30% destination probabilities.In the example, a ship traveling from Shanghai to Singapore next goes to Los Angeles with 70% probability or Seattle with 30%.Source: §1 · p. 24
• The rule-extraction test sets maximum order to five to check for false rules beyond the defined fourth order, using minimum support five.The synthetic trajectories were created to verify the rule-extraction algorithm’s effectiveness.Source: §1 · pp. 24–25

Rule extraction

• Rule extraction counts subsequences, filters rare paths, estimates movement distributions, and recursively extends source histories when next-step distributions change significantly.The process starts from first order and adds an earlier entity to the source sequence when the probability distribution changes significantly.Source: §2 · p. 25
• The recursive rule test keeps the last source node with a significantly different next-movement distribution as Valid, retaining the prior Valid when an extension does not differ.Paths from Valid enter the rule set when extension reaches MaxOrder or cannot continue.Source: §2 · p. 25
• Kullback–Leibler divergence compares the next-step distributions at the extended and valid source nodes to determine whether an extension changes movement probabilities significantly.Source: §2 · p. 25
• The significance threshold is self-adjustable across nodes, favoring pruning higher-order nodes and retaining nodes with greater trajectory support when divergence is comparable.Source: §2 · p. 26
• The algorithm can be adapted to diffusion data by extracting only the newest entity subsequence, and data type determines whether higher-order dependencies occur and how high their orders reach.For data without higher-order dependencies, all extracted rules remain first-order, yielding a first-order network.Source: §2 · p. 26

Network wiring

• Network wiring processes rules in ascending order, converts them to edges, and rewires valid-rule edges toward the highest-order available target nodes.Source: §2 · p. 26

Minimum support

• Raising minimum support from 1 to 10 with maximum order fixed at 5 shrinks the network 20 times and increases random-walking simulation accuracy by 0.54%.Source: §3 · p. 27
• Increasing minimum support from 1 to 100 first raises then lowers accuracy, as low thresholds count noise while high thresholds omit infrequent true patterns.Source: §3 · p. 27
• The optimal minimum support varies across data types and can be identified by parameter sweeping.An appropriate threshold can improve representation accuracy while substantially reducing network size.Source: §3 · p. 27

Maximum order

• With minimum support fixed at 10, increasing maximum order from 1 to 5 steadily raises random-walking simulation accuracy, which converges at order 5; network size follows the same trend.Source: §3 · p. 27
• Most dependencies have lower orders, and setting a high maximum order does not significantly increase HON construction time because longer subsequences usually fail minimum support.A maximum order of five is sufficient for most applications.Source: §3 · p. 27

Example

• HON retains g|f,d because its distribution differs from g although g|f matches g; VOM instead retains g|f and prunes f|d, a necessary construction node.This example illustrates how the models’ different node-retention mechanisms produce mismatched results.Source: §4 · p. 28
• HON retains the nodes needed for d→f|d→g|f,d, preserving first-order links and adding higher-order canal edges that capture the d-to-h and e-to-i route patterns.The passage describes this wiring as matching the assumed ship trajectories through the canal.Source: §4 · p. 28
• HON compares higher orders against an initial first-order assumption, whereas VOM recursively prunes from higher to lower orders and may discard distinct higher-order dependencies.The example notes that pruning z|y,x,w despite its different distribution from z can underestimate dependency order.Source: §4 · p. 28
• The authors conclude that VOM cannot directly construct HON because it retains unnecessary nodes, prunes necessary nodes, and may leave out higher-order dependencies.HON’s rule-extraction process prepares the rules needed for its subsequent network wiring.Source: §4 · pp. 28–29

Numerical comparison

• The comparison used the same global shipping data, MaxOrder=5, MinSupport=10, KL divergence, and threshold for significant distribution differences.The authors omit VOM’s optional smoothing because it is not compulsory and consider smoothing undesirable for network representation.Source: §4 · pp. 27–29
• HON and VOM extracted considerably different rule sets beyond first order despite identical parameters, as reported in the rule-count comparison.The passage does not provide the table’s cell values, so no numerical counts are stated.Source: §4 · p. 29

Rule extraction

• HON extracts rules by counting subsequences that meet minimum support, comparing next-step distributions for increasingly extended histories, and stopping when support fails or maximum order is exceeded.The procedure compares the original source node’s next-step distribution with that of a source extended by an additional earlier entity.Source: Supplementary figures, tables, and… · p. 30

Network wiring

• HON wiring converts first-order rules into edges, adds higher-order nodes as needed, then rewires edges while preserving weights and directing valid-rule edges to the highest-order nodes.The figure illustrates this wiring process for global shipping data.Source: Figure S2 · p. 31, Supplementary figures, tables, and… · p. 31

Parameter sensitivity

• Increasing maximum order improves random-walk prediction accuracy, which converges near order 5; an appropriate minimum support can reduce network size and improve representation accuracy.Accuracy is the percentage of correct next-step predictions by a random walker.Source: Figure S3 · p. 32, Supplementary figures, tables, and… · p. 32

HON and VOM

• HON retains necessary nodes and first-order information while capturing higher-order dependencies; VOM prunes some necessary nodes and retains some unnecessary ones.HON grows rules from first order, whereas VOM prunes rules from the highest order.Source: Figure S4 · p. 33, Supplementary figures, tables, and… · p. 33

PageRank changes

• The supplementary table reports the top 15 PageRank gainers and losers when HON replaces a first-order network on clickstream data.The supplied passage does not provide the scores or their magnitudes.Source: Table S1 · p. 34, Supplementary figures, tables, and… · p. 34