{'fraction_non_alphanumeric': 0.052991359510007656, 'fraction_numerical': 0.016624740238433775, 'mean_word_length': 3.859686420409248, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Irreducible Spine(s) of Undirected Networks

Using closure concepts, we show that within every undirected network, or graph, there is a unique irreducible subgraph which we call its"spine". The chordless cycles which comprise this irreducible core effectively characterize the connectivity structure of the network as a whole. In particular, it is shown that the center of the network, whether defined by distance or betweenness centrality, is effectively contained in this spine. By counting the number of cycles of length 3<= k<= max_length, we can also create a kind of signature that can be used to identify the network. Performance is analyzed, and the concepts we develop are illurstrated by means of a relatively small running sample network of about 400 nodes.


Introduction
It is hard to describe the structure of large networks. If the network has fewer than 100 nodes, then we can hope to draw it as a graph and visually comprehend it [6]. But, with more than 100 nodes this becomes increasingly difficult.
Simply counting the number n of nodes and number e of edges, or connections, provides essential basic information. Other combinatorial measures include counting the number of triangles, the number of edges incident to a node v, and the total number of nodes such that δ(v) = k, where δ(v) denotes the degree of a node v, or the number of edges incident to v. There exist data representations that effectively keep these kinds of counts, even in rapidly changing dynamic networks [12].
More sophisticated methods involve treating the defining adjacency matrix as if it were a linear transformation and employing an eigen analysis [14]. All these techniques convey information about a network. In this paper, we present a rather different approach.
First in Section 2 we reduce the network to an irreducible core, which is shown to be unique (upto isomorphism) for any network. Then in Section 3 we show that the irreducible core is comprised exclusively of chordless cycles of length k, or k-cycles. The center of the network, whether defined in terms of distance, or betweenness centrality [3], can always be found in this spine. In addition, the distribution of these k-cycles, 3 ≤ k ≤ max length, can provide a "signature" for the network.
Finally, we indicate how spine can be used to estimate other parameters of the network, such as diameter and number of triangles.

Irreducible Networks
For this paper we regard a network N as an undirected graph on a set N of n nodes with a set E of e edges, or connections. Many of these results can be applied to directed networks as well, but we will not explore these possibilities here. The neighborhood of a set Y of nodes are those nodes not in Y with an edge connecting them to at least one node in Y . We denote such a neighborhood by Proof. If not, we may assume without loss of generality that z is adjacent to y in σ. But, then σ(x, z), x ∈ {y}.η implies that {z}.ϕ ⊆ {y}.ϕ. (Also proven in [16].) ⊓ ⊔ In other words, z can be removed from N with the certainty that if there was a path from some node x to y through z, there will still exist a path of equal length from x to y after z's removal. Such subsumed nodes can be iteratively removed from N without changing connectivity. This iterative reduction process we denote by ω.
Operationally, it is easiest to search the neighborhood {y}.η of each node y, and test whether {z}.η ⊆ {y}.ρ as shown in the code fragment of Figure 1 no more subsumable nodes. Let y.β denote the set of nodes subsumed directly, or indirectly, by y. In a sense these subsumed nodes belong to y. Let τ (y) denote |y.β|. Since every node subsumes itself, τ (y) ≥ 1. In our implementation of this code, we also increment τ (y) by τ (z) every time node z is subsumed by y. So, τ (y) = |y.β|. Consequently, y∈N .ω τ (y) = n = |N |.
Before considering the behavior of ω, we want to establish a few formal properties of the reduced network. Proposition 2. Let N be a finite network and let I = N .ω be a reduced version, then I is irreducible.
Proof. Suppose {y} in I is not closed. Then ∃z ∈ {y}.ϕ η implying z.ρ ⊆ {y}.ρ or that z is subsumed by y contradicting termination of the reduction code.
⊓ ⊔ Two graphs, or networks, N = (N, E) and N ′ = (N ′ , E ′ ) are said to be isomorphic, or N ∼ = N ′ , if there exists a bijection, i : N → N ′ such that for all x, y ∈ N , (i(x), i(y)) ∈ E ′ if and only if (x, y) ∈ E. That is, the mapping i precisely preserves the edge structure, or equivalently its neighborhood structure. Thus, i(y) ∈ i(x).η ′ if and only if y ∈ x.η. 1 The order in which nodes, or more accurately the singleton subsets, of N are encountered can alter which points are subsumed and subsequently deleted. Nevertheless, we show below that the reduced graph I = N .ω will be unique, upto isomorphism. Proof. Let y 0 ∈ I, y 0 ∈ I ′ . Then y 0 is subsumed by some point y 1 in I ′ and y 1 ∈ I else because y 0 .ρ ⊆ y 1 .ρ implies y 0 ∈ {y 1 }.ϕ so I would not be irreducible. Similarly, since y 1 ∈ I ′ and y 1 ∈ I, there exists y 2 ∈ I such that y 1 is subsumed by y 2 . Now we have two possible cases; either y 2 = y 0 , or not. Suppose y 2 = y 0 (which is most often the case), then y 0 .ρ ⊆ y 1 .ρ and y 1 .ρ ⊆ y 0 .ρ or y 0 .η = y 1 .η. Hence i(y 0 ) = y 1 is part of the desired isometry, i. Now suppose y 2 = y 0 . There exists y 3 = y 1 ∈ I ′ such that y 2 .ρ ⊆ y 3 .ρ, and so forth. Since I is finite this construction must halt with some y n . The points {y 0 , y 1 , y 2 , . . . y n } constitute a complete graph Y n with {y i }.ρ = Y n .ρ, for i ∈ [0, n]. In any reduction all y i ∈ Y n reduce to a single point. All possibilities lead to mutually isomorphic maps.

⊓ ⊔
We call this unique subgraph, the irreducible spine of N . In [12], Lin, Soulignac and Szwarcfiter, speak of a "dismantling of a graph G as a graph H obtained by removing one dominated vertex of G, until no more dominated vertices remain"; and similarly conclude that "all dismantlings of G are isomorphic". This is precisely the process we have been describing. For the remainder of this paper we will use a single example to illustrate our approach to describing network structure. In [14] Mark Newman describes a 379 node network in which each node corresponds to an individual engaged in network research, with an edge between nodes if the two individuals have co-authored a paper. The reader is encouraged to view an annotated version at www.umich.edu/~mejn/centrality. 2 As described in [16], we used the code of Figure 1 to reduce the 379 Newman collaboration network to the 65 node irreducible spine shown in Figure 3. In our implementation, we keep a count of the number of nodes directly, or indirectly, subsumed by an irreducible node y. (These counts are displayed in following figures). In addition, we keep a list of the node identifiers of every subsumed node, so we can reconstruct a close approximation of the original network. Thus, this irreducible sub-network I ⊆ N can be regarded as a true surrogate of N itself. For simplicity, we have replaced the actual author names with identifying integers; for example the uppermost node, 1:23, denotes D. Stauffer. Here 1 is the identifier, 23 = τ (1) denotes the number of individuals in the community subsumed by 1. 3 By indicating the numbers of individuals/nodes subsumed by a node in the reduced version, we suggest the density of the original graph in this neighborhood. To further help the reader orient this reduced network with the original, we observe that 14:18 denotes M. Newman, 23:6 denotes H. Jeong, 25:41 denotes A.-L. Barabasi, 53:8 denotes Y. Moreno and 60:14 denotes J. Kurths.
We must emphasize that we are concerned strictly with the structure of a network, not its content. We have chosen this collaboration network solely because it is fairly familiar and well known. In no way do we want to suggest that the irreducible sub-network of this section, or the chordless k-cycles described in the following section necessarily contribute to an interpretation of the significance of the collaboration. N should be regarded simply as an arbitrary, but relatively complex, network.
What is the computational cost of reducing such a network to its irreducible spine? The dominant cost is the loop in Figure 1 over all n nodes of N . So, it is at least O(n). Then we have the embedded loop for each z in y.nbhd. First, we assume that the degree δ(y) of each node is bounded (typically the case in large networks), thus its behavior will still be linear. In our implementation, all sets are represented by bit strings, with each bit denoting an element; set operators are thus logical bit operations. There is no need to loop over the elements of a set. Consequently, set operations such as union, intersection, or containment testing, are O(1). In this case, the entire loop will still be O(n).
However, the loop of Figure 1 must be iterated until no more nodes are subsumed. It is not hard to create networks in which only one node is subsumed on each iteration; Figure 4 is a simple example, if nodes are encountered in subscript order. So worst case behavior is O(n 2 ). The analysis above assumed that the degree of all nodes was bounded. Suppose not; suppose δ(y) → n = |N |. In this case the node y will subsume many nodes, thereby bounding the number of necessary iterations. We have no formal proof for this last assertion, but it appears to be true.
Using their H-graph structure, Lin, Soulignac and Szwarcfiter, show that the cost to dismantle a network is O(n + αm) where α denotes the arboricity of N [12]. Experimentally, our reduction, ω, of the Newman collaboration graph to its irreducible spine shown in Figure 3 required 5 iterations, with the last over the remaining 65 nodes to verify irreducibility. Other reductions of 4,764, and 5,242, node networks to their 228, and 1,469, node irreducible spines respectively took 5 and 6 iterations. In practice, network reduction appears to be nearly linear.
A chord in a cycle is an edge/connection (y i , y j ) ∈ E where j = i ± 1 (or i = 1, j = k − 1). A cycle C is chordless if it has no chords. 4 It is the thesis of this paper that these chordless k-cycles provide a valuable characterization of the structure of a network. As a small example, consider Figure 5 from Granovetter's 1973 article on "weak ties" [8], which has been redrawn so as to emphasize the chordless 14-cycle. The nodes  (1) there exists a chordless k-cycle C, k ≥ 4 such that y ∈ C, or (2) there exist chordless k-cycles C 1 , C 2 each of length ≥ 4 with x ∈ C 1 z ∈ C 2 and y lies on a path from x to z.
⊓ ⊔ The points of those chordal subgraphs still remaining in Figure 5 such as the triangle < 15, 16, 17 >, are all elements of other chordless cycles as predicted by Proposition 4.

Centers and Centrality
A central quest in the analysis of social networks is the identification of its "important" nodes. In social networks, "importance" may be defined with respect to the path structure [5]. Let σ(s, t) denote a shortest path between s and t, and let d(s, t) denote its length, or distance between s and t. Those nodes C C = {y ∈ N } for which δ(y) = s =y d(s, y) is minimal have traditionally been called the center of N [9], they are "closest" to all other nodes. It is well known that this subset of nodes must be edge connected. One may assume that these nodes in the "center" of a network are "important" nodes.
Alternatively, one may consider those nodes which "connect" many other nodes, or clusters of nodes, to be the "important" ones. Let σ st (y) denote the number of shortest paths σ(s, t) containing y; then those nodes y for which σ st (y) is maximal are those nodes that are involved in the most connections. Let C B = {y ∈ N }, for which σ st (y) is maximal. This is sometime called "betweenness centrality" [3,5]. (Note: traditionally, centrality measures are normalized to range between 0 and 1, but we will not need this for this paper.) In the following sequence we want to show that nodes with minimal distance and maximal betweenness measures will be found in the irreducible spine I. This is non-trivial because it need not always be true. One problem is that, we may have several isomorphic spines, I 1 , . . . , I k , so we can only assert that C C ∩I j and C B ∩I j are non-empty for all 1 ≤ j ≤ k. Second, there exist pathological cases where the centers are disjoint from I. The network of Figure 4 is an example. If n = 8 then C C = C B = y 4 because 18 = δ(y 4 ) < δ(y 3 ) = δ(y 5 ) = 19, and 24 = σ st (y 4 ) > σ st (y 3 ) = σ st (y 5 ) = 23. But, y 4 ∈ I. The conditions of Proposition 7 will ensure this cannot happen. We can assume I is connected, else we are considering one of its connected components. Lemma 1. Let y ∈ I and let z "belong" to y, i.e. z ∈ y.β. There exists a shortest path sequence < y 0 , . . . , y k > such that (a) y 0 = y, Proof. This is a formal property of the subsumption process.

⊓ ⊔
This sequence need not correspond to the sequence in which nodes are actually subsumed.

⊓ ⊔
In this case, z may, or may not, also be in an alternate spine I ′ . Hence equality is possible in both (a) and (b).
Proof. We compare y ∈ I with any z ∈ y.β. The first assertion is just a corollary of propositions 5, where z ∈ y.η, and 6, where z ∈ y.η. The second assertion follows because the inequalities of Proposition 6 are all strict.

⊓ ⊔
The conditions of Proposition 7 (and Proposition 6) are sufficient to eliminate pathological situations such as Figure 4; but are by no means necesary. In practice, one really only needs that I be sufficiently large, and that its subsumed sub-graphs not be too unbalanced.

Estimation of Other Network Properties
The performance of many important network analysis programs is of order O(n k ), where k > 1. They execute much faster on a small network such as the irreducible spine rather than the network itself. Using I one can often approximate the value with considerable accuracy. We illustrate by calculating the diameter using Figure 3. Recall that the diameter of a network is the maximal shortest path between any two points. In [4], the cost to find a diameter using the Floyd-Warshall algorithm is O(n 3 ). This can be reduced to O(n 2 log n) by Johnson's algorithm, but we know of no better exact solutions. In Figure 3 we can do this by hand. 5 Readily, node 65, in the lower right hand corner is an extreme node. Expanding out by shortest paths, one finds that node 6 on the left edge is at distance 13, that is d(6, 65) = 13, and this is maximal in this irreducible spine. The center of this subgraph will be nodes at distance 6 or 7 from both extremes. These are nodes 35, 48 and 51, which are necessarily connected in I. Using Proposition 7 we can assume that at least one of these is in the actual center of N , and that C C is contained in its neighborhood.
We continue our estimation of the diameter by considering the subsumed portions of the network. What is the nature of the suppressed portions of the network?
Let y ∈ I, y.β is a chordal subgraph, where a subgraph is said to be chordal if it has no chordless cycles of length ≥ 4. Chordal graphs are mathematically quite interesting and have been well studied [2,10,13]. Succinctly, they can be regarded as tree-like assemblages of complete graphs; they can be generated by a simple context-free graph-grammar. In effect, they are pendant tree-like structures that are attached to the irreducible spine, I, at one (or two adjacent) nodes. Thus β is a set-valued operator that associates a pendant tree of complete graphs with y.
Readily, the diameter, diam n of a chordal graph on n points satisfies 1 ≤ diam n ≤ n − 1, with the lower bound occurring if {y}.β = K n , and upper bound when {y}.β is linear. In lieu of a better expectation, we will estimate the diameter of a pendant chordal graph {y}.β of n nodes to be n/2. (A much better expectation could be made if both the number of nodes, and number of edges, were recorded in the reduction process, ω. This would not be hard.) With this expected value, we can estimate the length of a maximal shortest path (u, v) in N through nodes 6 and 65 to be d(u, 6) + d(6, 65) + d(65, v) or 4/2 = 2 + 13 + 5 = 10/2, or d(u, v) = 20, where u ∈ {6}.β and v ∈ {65}.β.
A similar process can be used to count triangles in the network [17].

Network Signatures
If we count the cycles in the reduced Newman collaboration graph of Figure 3, we get the following enumeration. This distribution of chordless cycle lengths may serve as a kind of spectral analysis, or "signature" of the network. Much more research is needed to determine the value of these signatures for discriminating between networks. For example, at SocInfo 2012 in Lausanne, Switzerland, it was suggested that CC = k k × n k /|n|, where n k is the number of k cycles, might serve as a measure of connective complexity.
As we see, there are still 26 triangles in this reduction; such graphs are not "triangle-free". However, it is the 5 chordless cycles of maximum length that are of most interest. We might call them "major cycles". One of them is: < 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,  maximal length, while suppressing other aspects of this network.
The reduction process, ω, retains only nodes on, or between, chordless k-cycles, k ≥ 4 (Proposition 4). It eliminates the "chordal" subgraphs of N . It can be argued that by removing the chordal portions of a network N , ω is only deleting well understood sub-sections that can be reasonably well simulated and "re-attached" to the irreducible spine. Just retaining the size of these subsumed subgraphs permits calculation of certain global attributes, such as diameter and centrality, as described earlier.
Looking at Figure 7 we see a similar process taking place. The entire subgraph consisting of nodes {54, 55, . . . , 65} is another pendant portion which will be ignored if one concentrates solely on the longest k-cycles. The edge/connection (56, 60) ∈ E is retained, solely because it connects the two 4-cycles among nodes {60, . . . , 65} to the main body, as described in Proposition 4.
The 22-cycle shown in Figure 7 is only one of five longest chordless cycles; a second is shown in Figure 8. As can be seen, it involves other paths.