Source
Salter-Duke (2024), LIT-955, PhD thesis, Te Herenga Waka—Victoria University of Wellington, read in full in NOTE-814: Chapter 2 (definitions), Chapter 3 (algorithm and lemmas), Chapter 4 (community detection, §§4.4.1–4.4.3 and Fig. 4.31), Chapter 5 (images), Chapter 6.
What was actually shown
An edge-connectivity tangle of order k orients every cut of weight < k towards one side, so that no three small sides cover the graph and no big side is a single vertex. The author computed all such tangles, at the lowest orders that finished in under a day, on eleven real networks of 23 to 281 vertices, turned each tangle into a vertex set (vertices on the big side of every distinguishing separation, inheriting from lower orders), and compared the result with standard community methods by NMI and ARI.
- Weak or diffuse structure. Karate club, C. elegans neurons and college football have one tangle per order at every order reached, so no communities. B. subtilis PPI, jazz musicians and David Copperfield word pairs are left “largely undifferentiated”, with similarity “extremely low” against the reference comparison of Infomap with Louvain.
- Strong structure. On yeast PPI component A the order-2 tangle communities match edge-betweenness except for two one-vertex communities, with scores near the reference.
- The summary. Across eight networks, similarity to Infomap rises as the map-equation length falls, and similarity to Louvain rises as modularity rises (Fig. 4.31); lower orders match better.
- Trivial tangles. A vertex of degree ≥ θ, cut off by cuts of order < θ, is a tangle of order θ (§4.4.2); groups of one to three vertices appear “often” at the periphery. In images, pairs of corner pixels form tangles while one-pixel-wide lines cannot form one (§5.4).
What could have come out the other way: tangle communities could have matched one standard definition across all networks, or matched weakly structured networks as well as strongly structured ones. The author had hoped for the first and found neither.
What this does not say
- That tangles are wrong about cohesion. They are a precise notion, and the thesis tests its fit to how communities are used, not its coherence. Tangle–tree duality still makes the verdict exact for each order.
- That the trend holds at higher orders or larger graphs. Only low orders on small graphs were computable, and the author says the trend “may only apply” there.
- That the vertex sets are the tangles. A tangle is a set of oriented cuts. The communities depend on the assignment rule, which the author chose and calls one option among several.
- That the relation is measured. Eight points per panel, sized by order, with no fitted relation or uncertainty.
Connections
- QUESTION-035. Tangles are a candidate test of the “where does its
boundary lie” clause: one system means inseparable inside, and
separable outside, by cuts below an order k. The thesis shows the
verdict depends on k region by region, that it needs a further rule to
give a boundary as a vertex set, and that it passes single high-degree
vertices. That last is CLAIM-010’s permissiveness at the low end. No
answers:is declared: this tests a criterion and reports its failure modes; it does not answer the question. - CLAIM-157. The same shape, strength inside against strength across, with a threshold. The finding that each region has its own best order says a single global threshold will split some forms and miss others; CLAIM-157 sets its threshold per block, by the Occam factor, which is the kind of setting the thesis lacked. No relation is declared, as neither rests on the other.
- THEORY-268. On a connectome, misinformative macro transitions fall mostly between communities; here, tangles see communities only where the between-community cuts are cheap. Both locate the trouble at weak boundaries, by different measures. No relation is declared.