# A Set-Theoretic Approach to Modeling Network Structure
## 3 Network Properties
### Communities  
Many networks, especially those that represent social connections, are spotted with \"clusters\" of more densely connected nodes. These clusters of triangular links, which are often called **communities**, arise from the social phenomenon called **triadic closure**[14]. It is known that, in many social contexts, if \(x\) is connected to \(y\) and \(y\) is connected to \(z\), then \(x\) is likely to be connected to \(z\). Even though triadic closure is not really a closure operator, its principle has been identified on many repeated occasions [11,15]. (As normally encountered, triadic closure is not idempotent. Applied literally, the triadic closure of any network would be the complete graph/network on its \(n\) nodes).  
Figure 5: The interior \(\mathcal{I}\) of \(\mathcal{N}_{3}\), the 363 node co-authorship network of Newman [12].  
However, we know of no formal definition as to what really constitutes a \"community\".  
There have been numerous efforts to identify communities in a network [16]. Several work on the principle of \"bisection\" in which removal of certain links separates the network into \(n\) distinct communities [10]. A common problem is that usually \(n\) must be designated in advance. Others iteratively partition the network, often using the Fiedler eigenvector [17]. Here, the question is when to stop the iteration.  
A portion of the network that is dense with triangles may be regarded as a community. A connected sub-network of triangles is called a **k-truss**[18]. A connected subset of triangles could be tree-structured, so it is common to specify that a _k-truss_ is a connected collection of links with a _k_count_\(>1\), where the _k_count_ of a link \(\{x,z\}\) is \(|\{x\}.\eta\cap\{z\}.\eta|\) as in Pseudocode II. If _k_count_\(=2\), the Karate network of Figure 1 has just one 2-truss, consisting of links connecting the nodes \(\{1,2,3,4,5,6,7,8,9,11,14,30,31,33,34\}\) or just less than half the network. It has two 3-trusses connecting the nodes \(\{1,2,3,4,8,14\}\) and [9; 24; 33; 34]. The small network of Figure 3 has two 2-trusses of links connecting the nodes \(\{\)a, e, d, g, h, l, m, p, q, r, s\(\}\) and \(\{\)b, f, j, k, o\(\}\) and four small 3-trusses, which are \(\{\)b, j\(\}\), \(\{\)d, g, l, m\(\}\), \(\{\)p, q\(\}\) and \(\{\)r, s\(\}\). There are 23 2-trusses in the [PERSON] network and each is large; however, there are only three 8-trusses. They are \(\{\)[PERSON], [PERSON]\(\}\), [[PERSON], [PERSON]] and [[PERSON], [PERSON], [PERSON], [PERSON], [PERSON]]; however, [PERSON], [PERSON], [PERSON], [PERSON], and [PERSON] are not elements of the interior and thus not shown in Figure 5.  
The larger values of the principal eigenvector of \(A_{n\times n}\) (the adjacency matrix of the network) can indicate well-connected nodes, and often communities [3]. Nodes 1, 3, 33 and 34 of \(\mathcal{N}_{1}\), the Karate network of Figure 1, dominate its principal eigenvector. The principal eigenvector of \(\mathcal{N}_{2}\), the small network of Figure 3, are given in Table 2. Here, nodes \(d,e,m,r\) stand out. Higher values in this eigenvector appear to correlate with higher node degree. The nodes _[PERSON]_, _[PERSON]_ and _[PERSON]_ (in \(\{\) Jeong\(\}.\beta\)) are most prominent in the eigenvector of the Newman network.  
All of these methods have been proposed to denote \"communities\". We would suggest that the \(\beta\)-sets attached to \(\mathcal{I}\) also denote \"communities\".