pith. sign in

arxiv: 1907.09417 · v1 · pith:MRHWXP4Enew · submitted 2019-07-22 · 💻 cs.SI · physics.soc-ph

Trusses and Trapezes: Easily-Interpreted Communities in Social Networks

Jonathan D. Cohen This is my paper

Pith reviewed 2026-05-24 17:35 UTC · model grok-4.3

classification 💻 cs.SI physics.soc-ph
keywords trusstrapezecommunity detectionsocial networksbipartite graphs4-cycletriangleweighted graphs
0
0 comments X

The pith

Trusses based on triangles and trapezes based on 4-cycles identify easily-interpreted communities in social networks with polynomial-time computation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents the truss as a triangle-based relaxation of the clique for finding clusters of actors that is easy to interpret and computationally attractive. It introduces the trapeze as the corresponding 4-cycle-based structure, along with weighted extensions of both and refinements called strong and summit versions. These structures are motivated by natural observations of social cohesion, apply to bipartite graphs, accommodate edge weights without added complexity, and allow easy community determination across graphs of varying density. A sympathetic reader would care because the methods guarantee polynomial-time computation while relating to standard graph structures and addressing limitations of stricter clique-based approaches.

Core claim

The truss, a relaxation of the clique based on triangles, serves to identify clusters of actors in a way that is easy to interpret and is computationally attractive. This paper introduces the 4-cycle-based relative to the truss, called the trapeze, presents a weighted extension of both the truss and trapeze, and offers the refinements of strong trusses and trapezes and summit trusses and trapezes. Use of trapezes permits the application to bipartite graphs, while the weighted versions permit variation of support due to natural edge weights without increasing computational complexity. Finally, strong and summit versions make for easy determination of communities across graphs of varying密度.

What carries the argument

The truss (triangle-based relaxation of cliques) and trapeze (4-cycle-based relative), with weighted, strong, and summit variants, that identify communities while preserving polynomial-time computation.

If this is right

  • Use of trapezes permits the application to bipartite graphs.
  • Weighted versions permit variation of support due to natural edge weights without increasing computational complexity.
  • Strong and summit versions make for easy determination of communities across graphs of varying density.
  • Each structure offers guaranteed computation in polynomial time.
  • Each is motivated by a natural observation of social cohesion and related to other standard structures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • These structures could be applied to user-item interaction networks to test community recovery in bipartite settings.
  • The polynomial-time guarantee might enable community detection on networks too large for clique enumeration methods.
  • Weighted trusses and trapezes could be combined with existing edge-weighting schemes from other graph algorithms to handle heterogeneous data.
  • Summit variants might help compare community structure stability when network density changes over time.

Load-bearing premise

That the trapeze and its variants identify clusters in a way that is easy to interpret and motivated by natural social cohesion.

What would settle it

A concrete social network dataset where trapeze or truss communities fail to align with observed cohesive groups or require more than polynomial time to enumerate.

Figures

Figures reproduced from arXiv: 1907.09417 by Jonathan D. Cohen.

Figure 1
Figure 1. Figure 1: (b). It has four 4-trusses, only one of which is a clique [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 17
Figure 17. Figure 17: Strong Weighted Summit Trusses Among Subreddits Joined by Common Post Authors. Trusses are indicated by color, vertex labels indicate support of truss and name of subreddit. A Larger Real Trapeze Example Brightkite was once a location-based social networking service provider where users shared their locations via check-ins. Some of the (anonymized) data has since been made available (Cho, et al., 2011). T… view at source ↗
read the original abstract

The truss, a relaxation of the clique based on triangles, serves to identify clusters of actors in a way that is easy to interpret and is computationally attractive. This paper introduces the 4-cycle-based relative to the truss, called the trapeze, presents a weighted extension of both the truss and trapeze, and offers the refinements of strong trusses and trapezes and summit trusses and trapezes. Use of trapezes permits the application to bipartite graphs, while the weighted versions permit variation of support due to natural edge weights without increasing computational complexity. Finally, strong and summit versions make for easy determination of communities across graphs of varying density. Each of these structures offers guaranteed computation in polynomial time, is motivated by a natural observation of social cohesion, and is related nicely to other standard structures.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper introduces the truss (a triangle-based relaxation of cliques) and the trapeze (a 4-cycle-based analogue) as community structures in social networks, along with weighted, strong, and summit variants. It claims these are polynomial-time computable, motivated by natural social cohesion observations, related to standard structures, and enable application to bipartite graphs and graphs of varying density without added complexity.

Significance. If the algorithmic claims and structural relations hold, the trapeze extension to bipartite graphs and the weighted variants (without complexity increase) represent constructive contributions to community detection. The strong/summit refinements for density variation are a clear strength, as is the explicit focus on interpretability and polynomial-time guarantees.

minor comments (3)
  1. Abstract: the phrasing 'related nicely to other standard structures' is vague; the manuscript should explicitly name the related structures (e.g., k-truss, core decomposition) in the introduction or definitions section.
  2. The manuscript should include a dedicated section or subsection with the explicit algorithms or pseudocode establishing the polynomial-time claims for truss and trapeze computation, even if the derivations are straightforward.
  3. Notation: ensure consistent use of symbols for weighted vs. unweighted variants across definitions to avoid reader confusion when comparing strong and summit versions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the paper, recognition of the significance of the trapeze extension to bipartite graphs, weighted variants, and strong/summit refinements, and the recommendation of minor revision. The referee's description accurately reflects the manuscript's contributions on polynomial-time computability, interpretability, and relations to standard structures.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces truss and trapeze structures (plus variants) purely as definitions: truss as a triangle-based clique relaxation, trapeze as its 4-cycle analogue for bipartite graphs, with weighted/strong/summit extensions. These are motivated by informal social-cohesion observations and asserted to be polynomial-time computable, but no derivation chain, equations, predictions, or first-principles results are present that reduce to fitted inputs or self-referential constructions. No self-citations appear as load-bearing premises. The work is constructive and definitional rather than predictive, so the central claims remain independent of their own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, axioms, or invented entities; structures are presented as definitional extensions motivated by social observations without further breakdown.

pith-pipeline@v0.9.0 · 5659 in / 976 out tokens · 40291 ms · 2026-05-24T17:35:16.402736+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Many of the operations performed on social network graphs seek to identify cohesive communities of actors, represented by subgraphs within the larger network, for further analysis

    the network of relationships, and the structural nature of graphs provides easy automated analysis. Many of the operations performed on social network graphs seek to identify cohesive communities of actors, represented by subgraphs within the larger network, for further analysis. The communities are interesting in their own right and help to illuminate th...

    work page 2001

  2. [2]

    seedbeds, within which cohesive subsets can precipitate out

    is a generalization of the clique, and consists of a group of vertices such that each pair of members is separated by no more than a distance n. With this nomenclature, a clique is a 1-clique. The n-clique suffers from quite a few problems: For n > 2, the group is likely to be too diffuse to be of interest. Also, the problem of enumerating n-cliques is no...

    work page 1973

  3. [3]

    is an example of a dynamical systems method in which community structure is determined by collecting information from adjacent vertices. Spectral methods, based on eigenvectors of matrices associated with the graph, detect communities through a hierarchy of clusters by repeated bipartition, each informed by blocks induced by thresholding elements of eigen...

    work page 2003

  4. [4]

    supported

    constructs communities by finding small cliques and joining adjacent ones (those sharing all but one vertex). Basing the construction on finding cliques makes the process rather expensive, but is mitigated somewhat by restricting the cliques to small size. A review and comparison of popular overlapping community detection methods is Cohen: Trusses and Tra...

    work page 2013

  5. [5]

    The graph is of frequent associations between 62 dolphins in a community living off Doubtful Sound, New Zealand, taken from Lusseau, et al. (2003). The graph contains a single (maximal) 3-truss, shown in Figure 1(b). It has four 4-trusses, only one of which is a clique. Figure 1(d) shows there are two 5-trusses, one of which is a clique of order 5, the ot...

    work page 2003

  6. [6]

    This is clearly a tight group, but not a clique

    The Right-most 5-Truss of Figure 1(d). This is clearly a tight group, but not a clique. Another example is offered by Figure 3, in which the nodes represent political books, and edges between them indicate frequent co-purchases from Amazon.com. This data comes from Krebs (2004). Each book was examined (by Krebs) and judged to be liberal, conservative, or ...

    work page 2004

  7. [7]

    (2014), call this a truss community

    The figure shows that the single truss can be viewed as the union of four smaller groups, joined by a few 7 When maximal, Huang, et al. (2014), call this a truss community. Their definition was based on a weaker definition of a truss, which did not require a truss to be a single component subgraph. Cohen: Trusses and Trapezes: Easily-Interpreted Communiti...

    work page 2014

  8. [8]

    stronger

    A Single 2-Trapeze that is also Three Strong Trapezes. The colors indicate the strong trapeze membership. This also contains two 4-trusses. Cohen: Trusses and Trapezes: Easily-Interpreted Communities in Social Networks 16 Weighted Trusses It often happens that one would like to give some edges more weight than others. Factors that might drive weighting in...

    work page 2012

  9. [9]

    Trusses are indicated by colors; light green edges are not in the trusses

    Weighted Strong Trusses in Graph of Agreements Between United States Supreme Court Justices (2012-2013). Trusses are indicated by colors; light green edges are not in the trusses. Edges were given a weight equal to the percentage of time that the judges agreed in 5-4 decisions. Triangle weight was minimum of edge weights taken as integers in {0, 1, …, 100...

    work page 2012

  10. [10]

    local” support, we can produce the clusters shown in Figure 9(f); these are the strong “summit

    Before going on, we should note that another type of weighted truss was defined by Zheng, et al (2017), in which they define the weight of a truss as the smallest weight Cohen: Trusses and Trapezes: Easily-Interpreted Communities in Social Networks 19 of an edge in the truss, and offer methods to determine, for a specified value of 𝑘 and a specified integ...

    work page 2017

  11. [11]

    (a) Graph, (b) 3-trusses, (c) 5-trusses, (d) 8-trusses, (e) 17-trusses, (f) summit trusses

    Subgraph of Facebook friendships drawn from McAuley and Leskovec (2012) showing strong trusses. (a) Graph, (b) 3-trusses, (c) 5-trusses, (d) 8-trusses, (e) 17-trusses, (f) summit trusses. Cohen: Trusses and Trapezes: Easily-Interpreted Communities in Social Networks 21 For motivation, we can consider a graph laid out in two horizontal dimensions, and imag...

    work page 2012

  12. [12]

    MinBucket,

    refer to as “MinBucket,” in which triangles are constructed from their minimum-degree vertex. One variation proceeds this way: each edge is examined in turn and recorded (in a “bucket”) under the adjacent vertex whose degree is lowest (ties are decided in any consistent fashion). For each such bucket, each possible pair of edges in that bucket is consider...

    work page 2014

  13. [13]

    dendrogram

    find_k_classes(graph G): 𝑘←2; ∀𝑒∈𝐸(𝐺),𝑠(𝑒)←sup(𝑒); sort edges in ascending order of 𝑠; while ( 𝐸(𝐺)≠∅ ) { Φ2←∅; while ( ∃𝑒 ∋𝑠(𝑒)≤𝑘−2 ) { let 𝑒=(𝑢,𝑣) be edge with lowest 𝑠(𝑒); assume, w.l.o.g., deg (𝑢)≤deg (𝑣); for ( 𝑤∈neighbors(𝑢) ) { if ( (𝑣,𝑤)∈𝐸(𝐺) ) { 𝑠D(𝑢,𝑤)F←𝑠D(𝑢,𝑤)F−1; 𝑠D(𝑣,𝑤)F←𝑠D(𝑣,𝑤)F−1; reorder (𝑢,𝑤) and (𝑣,𝑤) by new 𝑠(𝑒); }; }; Φ2←Φ2∪{𝑒}; 𝐺←𝐺−𝑒 ...

    work page 2012

  14. [14]

    Circles are edge vertices, triads are represented as triangles, and peripheries are shown as rounded rectangles

    The Edge-Triad-Periphery Graph for the Graph of Figure 12 with Unproductive Vertices Removed. Circles are edge vertices, triads are represented as triangles, and peripheries are shown as rounded rectangles. From Figure 14, we see that there are four rectangles, each made with a different periphery. We also see that edges 6, 7, 8, and 9 are in two of them ...

    work page 2001

  15. [15]

    Trusses are indicated by color, vertex labels indicate support of truss and name of subreddit

    Strong Weighted Summit Trusses Among Subreddits Joined by Common Post Authors. Trusses are indicated by color, vertex labels indicate support of truss and name of subreddit. A Larger Real Trapeze Example Brightkite was once a location-based social networking service provider where users shared their locations via check-ins. Some of the (anonymized) data h...

    work page 2011

  16. [16]

    Dashed lines indicate independent friendship relations

    Three Strong Trapezes Sharing Single Locations in a Brightkite Check-ins Graph Connecting Users to Locations. Dashed lines indicate independent friendship relations. Colors indicate strong trapeze membership. The solid black line is a location check-in that is not in any of the trapezes. Note that the time of check-ins was not considered. Experiments were...

    work page 2014

  17. [17]

    A graph-theoretic definition of a sociometric clique,

    and for a bulk synchronous parallel computation model such as Pragel (Grzegorz, et al., 2010), in which computing nodes represent edges in the graph, and at each cycle computing nodes can receive information from their neighbors (who represent adjacent edges). Rossi (2014) describes fast, compact computation and general parallel implementation. Conclusion...

    work page arXiv 2010

  18. [18]

    Fast unfolding of communities in large networks

    Why do simple algorithms for triangle enumeration work in the real world?. In Proceedings of the 5th conference on Innovations in theoretical computer science (ITCS '14). ACM, New York, NY, USA, 225-234. Blondel, V. D., Guillaume, J. L., Lambiotte, R., and Lefebvre, E., 2008, “Fast unfolding of communities in large networks.” Journal of statistical mechan...

    work page 2008

  19. [19]

    Finding community structure in very large networks

    Data at https://snap.stanford.edu/data/loc-brightkite.html. Clauset, Aaron, Newman, Mark E.J., and Moore, Cristopher, 2004, “Finding community structure in very large networks.” Physical review E 70.6 (2004): 066111. Cohen, J. D., 2009, "Graph Twiddling in a MapReduce World," Computing in Science and Eng., vol. 11, no. 4, 2009, pp. 29–41. And supplement: ...

    work page 2004

  20. [20]

    Algorithms for graph partitioning on the planted partition model

    Condon, Anne, and Richard M. Karp, 2001, “Algorithms for graph partitioning on the planted partition model.” Random Structures and Algorithms 18.2 (2001): 116-140. Danon, L., Diaz-Guilera, A., Duch, J., & Arenas, A., 2005, “Comparing community structure identification.” Journal of Statistical Mechanics: Theory and Experiment, 2005(09), P09008. Cohen: Trus...

    work page 2001

  21. [21]

    Querying k-truss community in large and dynamic graphs,

    Huang, X., Cheng, H., Qin, L., Tian, W., and Yu, J. X., 2014, “Querying k-truss community in large and dynamic graphs,” In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (SIGMOD '14). ACM, New York, NY, USA, 1311-1322. Krebs, V., 2004, Copurchases of Political Books from Amazon, http://www-personal.umich.edu/~mejn/netdat...

    work page doi:10.1371/journal.pone.0018961 2014

  22. [22]

    McCulloh, Ian, Armstrong, Helen, and Johnson, Anthony, 2013, Social Network Analysis with Applications, Wiley,

    work page 2013

  23. [23]

    Cliques, clubs, and clans,

    Mokken, R.J., 1979, “Cliques, clubs, and clans,” Quality and Quantity, Vol. 13, 1979, pp. 161-173. Moody, J., 2001, “Peer influence groups: identifying dense clusters in large networks,” Social Networks, Vol. 23, 2001, pp. 261-283. Cohen: Trusses and Trapezes: Easily-Interpreted Communities in Social Networks 53 Palla, G., Derényi, I., Farkas, I., and Vic...

    work page 1979

  24. [24]

    The cohesiveness of blocks in social networks: node connectivity and conditional density,

    White, D. R., and Harary, F., 2001, “The cohesiveness of blocks in social networks: node connectivity and conditional density,” Sociological Methodology, Vol. 31 (2001), pp. 305-359. Xie, J., Kelley, S., and Szymanski, B. K., 2013, “Overlapping community detection in networks: The state-of-the-art and comparative study.” ACM Computing Surveys (csur) 45.4 (2013):

    work page 2001

  25. [25]

    Extracting analyzing and visualizing triangle k-core motifs within networks

    Zhang, Y., and Parthasarathy, S., 2012, “Extracting analyzing and visualizing triangle k-core motifs within networks.” 2012 IEEE 28th International Conference on Data Engineering. IEEE,

    work page 2012

  26. [26]

    Finding weighted k-truss communities in large networks,

    Zheng, Zibin, Ye, Fanghua, Li, Rong-Hua, Ling, Guohui, and Jin, Tan, “Finding weighted k-truss communities in large networks,” Information Sciences, Vol. 417, 2017, Pages 344-360, ISSN 0020-0255

    work page 2017