{'fraction_non_alphanumeric': 0.036504212945231714, 'fraction_numerical': 0.0090721945614707, 'mean_word_length': 4.187756115733267, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Analysis of the Neighborhood Pattern Similarity Measure for the Role Extraction Problem

In this paper we analyze an indirect approach, called the Neighborhood Pattern Similarity approach, to solve the so-called role extraction problem of a large-scale graph. The method is based on the preliminary construction of a node similarity matrix which allows in a second stage to group together, with an appropriate clustering technique, the nodes that are assigned to have the same role. The analysis builds on the notion of ideal graphs where all nodes with the same role, are also structurally equivalent.


Introduction
To analyze large networks and obtain relevant statistical properties, clustering nodes together into subgroups of densely connected nodes, called communities, is a popular approach. Various measures and algorithms have been developed to identify these community structures [32,17,35]. However, there are network structures that cannot be determined using community detection algorithms, such as bipartite and cyclic graph structures, which appear in human protein-protein interaction networks [31] and food web networks [19], respectively. General types of network structures are known as role structures, and the process of finding them is called the role extraction problem, or block modeling.
The role extraction problem determines a representation of a network by a smaller structured graph, called the reduced graph, role graph, or image graph, where nodes are grouped together into roles based upon their interactions with nodes in either the same role or different roles. This problem is a generalization of the community detection problem where each node in a community mainly interacts with other nodes within the same community and there are no, or very few, interactions between communities. There are many real world applications to which role extraction can be applied and from which characterizations of interactions that define roles can be taken, such as studying trade networks between countries [34]; evaluating the resilience of peer-to-peer networks [22]; ranking web pages in search engines [29]; studying human interaction by email correspondence [1]; modeling protein-protein interactions [23]; and analyzing food webs [19].
Previous research solved the role extraction problem using either direct or indirect approaches, where direct approaches cluster the network directly into roles [13,34,33], while indirect approaches construct a node similarity matrix of the data set and then cluster highly similar nodes together [3,24,11,9,2,10,27,26]. Both approaches have strengths and weakness for solving the role extraction problem. A strength of direct approaches is that it explicitly fits the data into a role structure. Unfortunately, there is no well-accepted measure to determine whether or not a role assignment fits the data, so a priori knowledge about the network is necessary or multiple role assignments must be tested to determine the best role structure for the data [13].
Indirect approaches do not require an assumption on the role assignment and may reveal complex network structures that the original data may not reveal. The main problem with indirect approaches is that there exist several different types of node similarity measures. In addition, many of these measure have been deemed unsuitable for the role extraction problem due to difficulties encountered when extracting role structures from certain types of graphs (e.g., regular graphs and normal graphs), loss of information (e.g., the origin, the destination, and the intermediate nodes involved in the transmission of the flow), or were more suited to detect community structures than role structures [6]. Fortunately, recent work has shown that the neighborhood pattern similarity measure can be used to solve the role extraction problem when using the indirect approach.
Browet and Van Dooren used the neighborhood pattern similarity measure to solve the role extraction problem and showed empirically that the measure was able to determine the role structure of complex networks [6]. In addition, they developed an algorithm to compute a low-rank approximation of the similarity matrix and showed empirically that their indirect approach can extract role structures within networks. Marchand improved upon their low-rank algorithm using Riemannian optimization techniques to develop a more efficient algorithm to compute the low-rank similarity matrix and showed (analytically and empirically) that there exists a relationship between the rank of the similarity matrix and the number of roles in the network [26].
In this paper, we analyze the neighborhood pattern similarity measure and show that, under certain assumptions, we can recover roles from a low-rank factorization of the similarity matrix due to the relationship between the rank of the similarity matrix and the number of roles. Also, we explore how perturbing the adjacency matrix affects the singular values (and rank) of the similarity matrix. Lastly, we unify special complex structures in networks (e.g., community, overlapping community, etc.) as role structures and show that the neighborhood pattern similarity measure can be used as well to find these structures in network topology.

Role Extraction Problem
Given a (un)weighted and directed network, the role extraction problem represents the network by its adjacency matrix and determines a representative role structure for the network. This role is determined by assuming that nodes can be grouped according to a suitable measure of equivalence. In this section, we state two measures of equivalence used for the role extraction problem and define the general form and state the constraints necessary to extract viable role structures. Most of the discussion and results that follow concern unweighted directed graphs. In Section 5, the expression of special graph structures as role structures includes generalizations to signed weighted directed graphs.

Measure of Equivalence and Definition of the Role Extraction Problem
A graph, denoted G(V, E), is a mathematical structure with two finite sets V and E, where the elements of the set V = {1, . . . , n} are called nodes and the elements of the set E = {(i, j) | i, j ∈ V } are called edges. If there exists an edge between nodes i and j, i.e., the pair (i, j) ∈ E, then nodes i and j are adjacent. The adjacency matrix is an n × n {0, 1}-matrix A, where if (i, j) ∈ E, then A i,j = 1; otherwise A i,j = 0. If the graph is weighted and (i, j) ∈ E, then the weighted adjacency matrix is denoted by W and W i,j is represented by its edge weight.
Given the adjacency matrix A, the role extraction problem finds a n × n permutation matrix P such that the edges in the permuted adjacency matrix A p := P T AP , which represents the relabeled graph, are mainly concentrated into blocks (see Figure 1). In order to form the relabeled graph, one needs to determine if the nodes are structurally or regularly equivalent. Figure 1: Block modeling : find the permutation P such that the relabeled adjacency matrix P T AP has an approximate block structure.
Two nodes are structurally equivalent if they have exactly the same children and the same parents [25]. In terms of block modeling, this means that all blocks in the permuted adjacency matrix must then either have only 0's or only 1's : if we denote by I and J two sets of nodes that each contain structurally equivalent nodes, then (i) the block (I, J) in P T AP is a "0" block if none of the nodes in I has any children in group J, or equivalently, if none of the nodes in J has any parents in group I, and (ii) it is a "1" block if all the nodes in group I has all the nodes in group J as children, or equivalently, if all the nodes in group J has all the nodes in group I as parents [13].
Structural equivalence usually extracts many small roles in networks [37,15,16]. Thus, an alternative equivalence relation, regular equivalence, was proposed to extract larger roles. Two nodes are regularly equivalent if, while they do not necessarily share the same neighbors, they have neighbors who are themselves structurally or regularly equivalent. Alternatively, this means that the blocks in the permuted adjacency matrix must contain at least one element per row and column (called a regular block). Note that structural equivalence implies regular equivalence, but regular equivalence does not imply structural equivalence.
Every group of regularly equivalent nodes of A can be represented by a single role in the role graph, which is a smaller assignment matrix B with a number of nodes that is the number of groups of regular equivalent nodes in A. Moreover, B I,J = 1 if the nodes in group I in the original graph A all point to the nodes in group J in A, and B I,J = 0 if none of the nodes in group I in A point to any of the nodes in group J in A. Additionally, Reichardt and White assumed that no two roles in the role graph B may be structurally equivalent because if they were, then both roles would interact with the same roles and we would be unable to distinguish between the two roles [34,33]. So, these two roles should be merged into one role. These ideas are used below to define an ideal form of adjacency matrix that facilitates the extraction of roles by its use to approximate the adjacency matrix of the given graph.
Earlier research in role extraction involved creating a cost function to minimize over both the role structure and role assignment of nodes in the graph based on a choice of equivalence relation [36,13,34,33]. That is, if B is the adjacency matrix of the role graph and σ is the assignment of each node to a role, then the problem can be stated as where Q A depends on the graph topology and chosen equivalence criterion. Note that (2.1) is a combinatorial optimization problem with respect to two groups of variables and is harder than the community detection problem, which is, in general, NP-hard [5,4]. The cost function Q A (B, σ) can either be constructed indirectly, based on a (dis)similarity measure between pairs of nodes, or directly, based on a measuring of the fit of clusters compared to an ideal clustering with perfect relations within and between clusters. We focus on an indirect approach to the role extraction problem and show how the similarity metric chosen for our approach can be used to first extract the optimal assignment function σ * of the role structures in a network. Once the groups of the assignment σ * have been identified, then in a second step, the role matrix B is easy to construct, provided we use a cost function that is "decoupled" in the elements of B, since each element B ij ∈ {0, 1} can then be chosen independently in order to maximize Q A (B, σ * ).

Role Models and Ideal Graphs
We are particularly interested in graphs with a permuted adjacency matrix A P := P T AP which has a special block form that can be represented in the factorized form where q is the number of roles in the role graph, z i := [1, . . . , 1] T ∈ R n i , n = n 1 + · · · + n q , and B is a q × q adjacency matrix (i.e., the role matrix) describing the roles in the original matrix A P . We assume that the graph does not have disconnected nodes (a zero row and corresponding zero column of the adjacency matrix A) because this would imply that Z has a zero row. We call such graphs ideal graphs because all of the nodes in each role are structurally equivalent. Such a decomposition is not unique. If, for instance, the k-th row and column of the matrix B contains only zeros , then clearly the row and column can be removed in the decomposition ZBZ T , which yields a smaller decomposition. For example, suppose the matrix B and the decomposition matrices are This implies that the original adjacency matrix also had a number of corresponding zero rows and columns. Therefore, we do not need to associate any role to the corresponding nodes. Non-uniqueness of the factorization also occurs when the matrix B has itself a decomposition with a smaller matrixB with fewer roles. Consider the 3 × 3 image matrix in the decomposition The roles 2 and 3 of the image matrix B are structurally equivalent and can be combined into a single role. This implies that B has the factorization as which can then be used to obtain the smaller decomposition whereẑ 2 has now n 2 + n 3 elements.
In order to introduce a form of uniqueness, we define the so-called minimal role matrices.
Definition 2.1. If A = ZBZ T is an adjacency matrix of a connected unweighted directed ideal graph then B is a minimal role matrix if no two rows of the compound matrix B B T are linear dependent.
Note that, unlike community detection, a factorization A = ZBZ T always exists by simply taking A = B and Z = I. In practice, this is of little interest since the point of role extraction is to identify structure in the graph with significantly fewer roles than nodes, i.e., a low-rank ideal adjacency matrix that approximates A well. As a result, we explore the relationship between the neighborhood pattern similarity measure, minimal ideal graphs, the rank of their adjacency matrices, the number of roles, and the rank of A.

Uniform distributions
Browet et al. showed empirically that the indirect method using the neighborhood pattern similarity measure worked well extracting the role structure from randomly generated Erdös-Rényi graphs [6]. The method works well on randomly generated Erdös-Rényi graphs because their expected value is a matrix of rank 1.
In an Erdös-Rényi graph, each node has a probability p to be present. Therefore the expected value of the adjacency matrix of such an n × n graph equals E(A) = p11 T , which is rank 1 and has Perron root np. Moreover, it has been shown that for large Erdös-Rényi graphs (these are undirected graphs with edges of equal probability p) the other eigenvalues of the adjacency matrix have an expected value that is much smaller than np [14]. Therefore, if we apply the same reasoning to a matrix A with role matrix B, then the expected value of the adjacency matrix would be where p in is the probability of an edge existing between corresponding roles and p out is the probability that an edge does not exist. Therefore, E(A) has rank at most q and if the remaining n − q eigenvalues are also small such as in the standard Erdös-Renyi case, then E(A) is a good approximation of A.

Analysis of the Rank of the Neighborhood Pattern Similarity Measure
In practice, computing the similarity matrix is expensive, especially for large networks. So, a low-rank approximation of the similarity matrix is preferable due to efficiency in storage and computational complexity, but we may lose information necessary to extract the role structure. In this section, we prove for, the ideal graph case, that there exists a relationship between the rank of neighborhood pattern similarity matrix and the number of roles in the network. In addition, we prove that the roles can be extracted correctly, even for a similarity matrix with rank less than the number of roles. Section 4 considers extracting the role structure of graphs whose similarity measure have a good low-rank approximation by examining the neighborhood of graphs around ideal graphs with low-rank similarity measures.

Neighborhood Pattern Similarity Measure
The neighborhood pattern similarity measure determines if two nodes are similar if they have similar neighborhood patterns [6,7,12]. A neighborhood pattern of length is defined as the number of incoming (I) and outgoing (O) edges starting from a source node [6]. For example, neighborhood patterns of length 1 are patterns where two nodes are similar if they have common parents, i.e., For neighborhood patterns of length 2, there are four possible neighborhood patterns and the number of common target nodes between every pair of source nodes for neighborhood patterns of length 2 is given by (see [6] for a more detailed proof of this) In general, the number of possible neighborhood patterns of length is 2 and the number of common target nodes is given by Therefore, the neighborhood pattern pairwise node similarity measure can be defined as the weighted sum of the number of common target nodes of the neighborhood patterns of any length, i.e., where β ∈ R is a scaling parameter that weights longer neighborhood patterns [6] (implying that as β increases it is expected to be more difficult to have two nodes similar to each other). Note that the similarity matrix S is a symmetric positive semi-definite matrix.

The Similarity Matrix Recurrence
In Browet's thesis [6], the following recurrence relation was proposed for computing a similarity matrix, where Γ A [X] := AXA T + A T XA is a linear mapping from R n×n to R n×n which moreover preserves symmetry, non-negativity and semi-definiteness of the argument X : where I n is the n × n identity matrix. This sequence was shown to converge to a bounded fixed point if and only if β 2 satisfies .
Since the initial matrix S 1 is symmetric, positive semi-definite and non-negative, and the mapping Γ A preserves these properties, it follows that all matrices S k are symmetric, positive semi-definite and non-negative.
Theorem 3.1. Consider the iteration (3.2) where β is chosen according to (3.4) to guarantee convergence to a bounded solution S ∞ . Then all matrices S k , including their limit S ∞ , have the same image as the compound matrix [A A T ], and the same rank r.
Proof. The iteration (3.2) can be rewritten as follows The first equation implies Im S 1 = Im A A T , where Im M denotes the image (or column space) of a matrix M . In the second equation, the middle matrix is positive definite since S k is semidefinite, and this implies that Im S k+1 = Im A A T . This also implies that the rank of all matrices S k , k ≥ 1 is equal to the rank of A A T . For the limit S ∞ , one has to be more careful, since the rank could drop. But the second equation also implies that (in the Loewner ordering) S k S 1 for all k and hence the rank must remain constant.

The Ideal Graph Case
For the role extraction problem, the idea of using a low-rank projection of a similarity measure for the construction of the indirect cost function was proposed by Browet and Van Dooren in [6,7]. However, they only provided empirical evidence of the relationship between the rank of the neighborhood pattern similarity measure and the number of roles in the network. In this section, we prove, for ideal graphs, a relationship between the rank factorization of the similarity matrix and the number of roles in the network. In addition, we prove that the rows of the left factor of the rank factorization of the similarity matrix have exactly q clusters of all parallel vectors.
Recall that adjacency matrix, A, of an ideal graph satisfies the decomposition where B is a minimal role matrix.
Corollary 3.1. When the matrix A is the adjacency matrix of an ideal graph with minimal role matrix B, then Im S k ⊆ Im P Z, and hence r := rank S k ≤ q := rank Z, where q is the number of roles.
Proof. This is a direct consequence of Theorem 3.1 since both A and A T have an image included in the image of P Z.
Since S k is symmetric and Im S k ⊆ ImP Z, we can write it as S k = (P Z)Ŝ K (P Z) T , whereŜ k := N −1 (P Z) T S k (P Z)N −1 0 (i.e.,Ŝ k is positive semi-definite) and N := Z T Z = diag{ z 1 2 2 , . . . , z q 2 2 } is a q × q diagonal matrix. We can then reformulate the iteration (3.2) as a recurrence for theŜ k matrices :Ŝ where N k := N + β 2 NŜ k−1 N . We then obtain the following result Corollary 3.2. When A is an adjacency matrix for an ideal graph with minimal role matrix B, then for all k, including k = ∞, it follows that ImŜ k = Im[B B T ], Im S k = Im P ZŜ k = Im P Z[B B T ], and hence r := rankŜ k = rank S k ≤ q := rank Z, where q is the number of roles.
Proof. The proof that ImŜ k = Im[B B T ] is very similar to the proof of Theorem 3.1. The fact that Im S k = Im P ZŜ k follows from the identity S k = (P Z)Ŝ k (P Z) T and the fact that both S k andŜ k are semi-definite. The rest easily follows. Now, we show that even when we have a factorization (2.2) with the minimal role matrix B, rank S k can be smaller than q, the number of roles. Let Nevertheless, we prove below that we can recover the different roles via clustering performed on the low-rank factorization of any matrix S k , even though its rank is smaller than the number of roles.
Theorem 3.2. Let A = (P Z)B(P Z) T be an ideal graph with B minimal. For any k, letŜ k 0 be defined as above with rank r ≤ q and low-rank factorizationŜ k = V k V T k where V k ∈ R q×r . The matrix S k has the low-rank factorization S k = (P ZV k )(P ZV k ) T and the rows of the matrix P ZV k have exactly q clusters of all parallel vectors.

Proof. Since all matricesŜ
are symmetric matrices with the same image, they also have the same kernel, which must be the kernel of B T B . Let v T j,k , j = 1, . . . , q be the rows of the matrix V k . Then v j,k = 0 for any j, since otherwise the j-th row of B and B T would be zero and this violates the minimality assumption. For the same reason, no two rows v T i,k and v T j,k of V k can be parallel, since otherwise the same two rows of B and B T would be parallel, which means that these roles would be structurally equivalent and this also violates the minimality assumption. If we now look at the (unpermuted) matrix ZV k then it has the form and each block z j v T j,k corresponds to a cluster of n j row vectors parallel to v T j,k . Since none of the vectors v j,k is zero or parallel to another row of V k , we have exactly q different clusters. This is of course not affected by the permutation P .
Remark 3.1. If B is not a minimal role matrix, then the correct number of roles of the compressed image matrixB can be detected by removing zero rows, or merging dependent rows, of V .
By Theorem 3.2, we can extract the role structure of the network from the low-rank factor of any S k of an ideal adjacency matrix. This is ideal for large networks because the similarity matrix recurrence (3.2) has O(n 3 ) computational complexity, while the computational complexity for the current low-rank algorithms is O(nr 2 ) [6,26]. While for any k in this ideal case the vectors, v j,k , j = 1, . . . , q, associated with each role are not parallel, there is value to not simply taking k some convenient small fixed value. As k increases the angles between the non-parallel vectors, v j,k , j = 1, . . . , q, increase thereby increasing the discrimination capabilities when a lowrank approximation of the similarity matrix of a non-ideal adjacency matrix is used to select the nearby ideal adjacency matrix used to extract the role structure. Remark 3.2. If for a given adjacency matrix A (not necessarily ideal) and a given assignment function σ, we use the cost function , then P and Z are completely defined by the assignment function σ. Therefore, once σ is fixed, the above function can be decoupled as the sum where (P T AP ) i,j is the (i, j) block of the permuted matrix A. Clearly this is minimized by choosing and B i,j = 0 otherwise. For a non-ideal adjacency matrix A this leaves the key question of using an approximate low-rank factorization of its associated similarity matrix to determine Z that, in part, defines a near-by ideal matrix for use in determining the role structure. The feasibility of such approximations yielding a useful Z and therefore B is considered in Section 4.

Perturbation Analysis
In this section, we analyze the singular values of the adjacency matrix A of a directed unweighted ideal graph and the effect perturbing A has on them and on the similarity matrix. The perturbed adjacency matrix is denoted as A + ∆, where ∆ is the perturbation (i.e., addition or subtraction) of some elements a i,j . The main questions to be addressed are: 1. Can we estimate the number q of "ideal" roles from the singular values of the perturbed graph ?
2. Is the dominant subspace of the perturbed matrices S k then still close to Im Z of the ideal adjacency matrix A so that we can find the correct grouping of nodes?
If we can answer these two questions affirmatively, then we can recover the correct grouping of nodes and their roles.

The Singular Values of the Ideal Graph Case
Let A = (P Z)B(P Z) T be the adjacency matrix of an directed unweighted ideal graph where B is a minimal role matrix. Then, Z can be represented by the factorization Z = U q N 1/2 where U T q U q = I q and N 1/2 := diag{ z 1 2 , . . . , z q 2 }, and we can writeS k := (P U q ) T S k (P U q ), whereS k is symmetric andS k 0. We can reformulate the iteration on the S k matrices as a recurrence for theS k matrices, i.e., whereB := N 1/2 BN 1/2 . Therefore ImS k = Im[BB T ], Im S k = Im P U qSk = Im P U q [BB T ]. Also, the nonzero singular values of A and S k are those of Σ(A) = Σ(B), since A = (P U q )N 1/2 BN 1/2 (P U q ) T and Σ(S k ) = Σ(S k ), since S k = (P U q )S k (P U q ) T , ∀k ≥ 1.

Remark 4.1.
It is informative to look at the case of ideal undirected graphs, since then A = A T and S 1 = 2A 2 . Moreover, all matrices S k then commute with A and the expression for the matrices S k simplifies to i , respectively, then the following relations hold : for all k, as long as the condition on β holds, since then k =1 [βλ . In Appendix A, we also prove that and that the ratio also grows with β as long as it satisfies the bound β < 1/λ (1) max . Therefore the ordering of the singular values λ (k) i is preserved for all k and the relative gap between dominant singular values and the small ones, is easier to identify for large k and for β close to its upper bound 1/λ (1) max . While these trends are specific to the undirected graph case, due to our empirical studies, we also use them for the directed graph case below.

The Singular Values of A for the Perturbed Graph Case
Due to the analysis above showing the relevant gap increasing with k, we concentrate on comparing the singular values of A with those of S 1 . Furthermore, if we write S 1 = XX T , where X := A A T , S 1 2 1 has the same nonzero singular values as X. Therefore, we analyze here the perturbations of the spectrum of A and X := A A T for an arbitrary perturbation ∆ of the ideal adjacency matrix A of a directed unweighted ideal graph. We analyze the case of an arbitrary perturbation of {0, 1} type and the special case of a Erdös-Renyi type perturbation. For simplicity, we assume that A and X have both the same rank q, which is the number of roles.
Since we can rewrite the ideal decomposition A = ZBZ T as the normalized factorization , it follows that we can construct an orthogonal transformation We . We also assume that the perturbation ∆ is sufficiently smaller than the norm of the ideal adjacency matrix A such that one can use classical perturbation analysis techniques.
It follows then from standard perturbation theory of the matrix that the q dominant singular values of A(∆) are ∆ 2 -close to those ofB and that the (q + 1)st singular value of A(∆) is strictly bounded by the norm of the submatrix ∆ 21∆22 (see e.g. [18]). Similarly, the q dominant singular values of , are then ∆ 2 -close to those of BB T and the (q + 1)-st singular value is strictly bounded by the norm of the submatrix ∆ 21∆22∆ T 12∆ T 22 [18].
Note that the singular values ofB := N 1 2 BN 1 2 can be expected to be large since the diagonal scaling N has large entries n i , the matrix B has only 0 and 1 entries and is nonsingular. A precise lower bound on the smallest singular value of B is not available but due to the 0, 1 structure it is expected to be O(1) with an acceptable gap to the size of a reasonable perturbation. In practice,B will have dimension small enough so its singular values can be computed with negligible additional cost to assess its quality in any role extraction algorithm.
Given an ideal adjacency matrix and a minimal B, we also consider an Erdös-Rényi perturbation model determined by two probabilities p in and p out [14]. Elements of A that are 1 change to 0 with probability p in and elements of A that are 0 change to 1 with probability p out . Given this Erdös-Rényi perturbation model, the expected value of ∆ is known : This then means that the norms of∆ 12 , ∆ 21 and∆ 22 , can be expected to be much smaller that the norm of ∆. Moreover, this suggests that we can estimate the q largest singular values of A + ∆ by those of which are very close to those ofB when p in and p out are small.
For example, for the Erdös-Rényi graph in Figure 3, there is a distinct gap between the 4th and 5th singular values for A, S 1/2 ∞ and S ∞ for the ideal graph case (i.e., rows (a) and (c)). This indicates that the rank of S ∞ is 4, which is the number of roles. For the perturbed graph case, the gap between the 4th and 5th singular values is smaller; however, the gap is larger in S ∞ than in A.
Also, note that for the perturbed case, the difference between the 4th and 5th singular values of S ∞ for the large graph is 10 4 , while it is 10 2 for the smaller graph. So perturbing small graphs has a larger effect on how well the similarity measure can detect the number of roles than perturbing large graphs. However, in practice we are more interested in extracting structure for large graphs so this is not a major concern. For both cases it is seen that using the similarity measure to detect the roles in the graph is preferable to using the adjacency matrix because the gap in the singular values is larger for S ∞ than it is for A. Notice that this is intimately related to the fact that we consider unweighted adjacency matrices since those are the ones where the Erdös-Rényi property applies.

Unification of Special Complex Structures as Role Structures
In this section, we unify special complex network structures as role structures and show why the neighborhood pattern similarity measure will extract these structures. We do this by examining the structure of the associated ideal adjacency matrix, A. As in the general discussions of earlier sections, in efficient role extraction algorithms, these ideal forms would be identified by considering low-rank approximations of the similarity matrices of non-ideal adjacency matrices.

Community Structures
A popular type of network structure is a community structure. Community structures are described as groups of nodes where there exists many connections between nodes in the same group and no (or few) connections between nodes in different groups [28]. For the role extraction problem, community structures can be viewed as role structures, where the role matrix B is an identity matrix of dimension equal to the number of roles. Therefore, community structures are a special case of role structures. Since we assume, in the ideal case, that the intrarole adjacency matrices are cliques, the graph with ideal community structure is unweighted and undirected with a symmetric adjacency matrix A. Note that matrix B is a minimal role matrix of the adjacency matrix A and that rank(B) = 3, which is the number of roles. Therefore, rank(S ∞ ) = 3 and we can recover the three communities.

Overlapping Community Structures
Another type of network structure is an overlapping community structure. Community structures emphasize the presence of dependencies inside a group and the absence of dependencies between groups. However, there may exist nodes that can be placed in multiple communities without significantly altering the value of the cost function being minimized. That is, given two separate communities A and B, a third group of nodes C may be included in either A or B if the cost function fails to determine a significance of one community over the other [30,33]. Therefore, it can be concluded that A and B are overlapping communities and C is the overlap (see Figure 4a).
Observe for the adjacency matrix (Figure 4b) that the overlapping community structure in Figure 4a can be represented by the 3 role structure in Figure 4c. That is, the overlap C can be  represented by its own role where its role has connections to other nodes within the same role and to nodes in roles A and B. Also, the nodes in roles A and B do not interact with each other and only interact with nodes within the same role or with nodes in role C. Lastly, the above role structure is a valid role structure since it satisfies the role constraint that no two roles are structurally equivalent. In general, a role structure is considered an overlapping community structure when two (or more) roles interact with another role (the overlap role) and with themselves. In addition, the overlap role interacts with the other two (or more) roles and with itself. Also, the matrix B will be a full rank minimal role matrix.

Bipartite Networks and Communities
A common network in many applications, such as biological networks, is a bipartite network. A bipartite network is a set of nodes decomposed into two disjoint sets (say, of dimensions n 1 and n 2 ) such that no two nodes within the same set are adjacent [28]. For an appropriate ordering of the nodes, the adjacency matrix A can then be partitioned as One easily checks that the similarity matrices S k are then block diagonal and of the form We are particularly interested in ideal bipartite networks where the communities are bipartite cliques (a clique with the edges within each part removed). Figure 5 is an example of a bipartite clique and its corresponding adjacency matrix. Observe that this bipartite clique has a very simple role structure (see Figure 5c). This bipartite clique has an ideal adjacency matrix, A = (P Z)B(P Z) T , with the minimal role matrix B B = 0 1 1 0 , and rank(B) = 2. It follows that the similarity matrices, S k with k ≥ 1, for this bipartite clique have rank(S k ) = 2 and we recover the two roles from the role matrix.
has three bipartite communities. Also, observe that B has 6 roles and is a minimal image matrix with rank(B) = 6. Therefore, rank(S k ) = 6 and we can recover the 6 role structure, i.e., 3 bipartite communities.
In general, a network with q bipartite communities has a 2q × 2q minimal role matrix B with 0 in the two q × q diagonal blocks and a q × q identity matrix in the two off-diagonal blocks. The q bipartite community network has 2q roles and since B is symmetric, rank(B) = rank(S k ) = 2q, which is equal to the number of roles. Therefore, the similarity matrix can be used to determine the role structure of bipartite communities. Since each community is based on a bipartite clique, as with communities in Section 5.1, this implies that the ideal adjacency matrix is symmetric.

Signed Networks
A signed unweighted directed graph is denoted G(V, E − , E + ), where E − ⊆ V × V are the negative edges, E + ⊆ V × V are the positive edges, and no edge can be both positive and negative (i.e., E − ∩ E + = ∅) [13]. The associated signed unweighted adjacency matrix is defined in terms of its elements A i,j by Networks with positive and negative edge weights include social analysis networks and recommender networks [36,13,28,35]. In such networks negative edges often denote a dislike towards a person, place or thing. Of interest here are the set of signed unweighted graphs that are "checkerboard".
Definition 5.1. A signed unweighted directed graph G with signed adjacency matrix A has a checkerboard pattern if there exists a diagonal sign matrix Q ∈ {0, ±1} n×n satisfying Q 2 = I such that |A| = QAQ. This is equivalent to there being a permutation matrix P such that P AP T can be partitioned into a 2 × 2 block structure where the two diagonal blocks contain only 0 and 1 elements and the two off-diagonal blocks contain only 0 and −1 elements.
A simple (partitioned) example of a checkerboard adjacency matrix, is where Q := diag(1, −I 2 , 1, −I 2 ) also indicates the checkerboard partitioning. Checkerboard matrices are related to so-called socially balanced networks, which were introduced by Heider in [20,21] and later analyzed by Cartwright and Haray in [8]. Further discussion of balanced networks and checkerboard graphs can be found in [36,13,35,26].
There is a simple relationship between the sequence of matrices S k defining the similarity matrix for a checkerboard signed adjacency matrix A and the sequence of matricesS k defining the similarity matrix of adjacency matrixÃ = |A|. Specifically, if QAQ = |A| =Ã for a diagonal sign matrix Q, satisfying Q 2 = I, it then follows from (3.2) thatS k = QS k Q = |S k |. This implies that the ranks and singular values of S k and |S k | are the same and that for the low-rank approximation one can as well consider the iteration matrices |S k | for the unsigned adjacency matrix |A|.
For checkerboard signed ideal adjacency matrices with the rank factorization A = ZBZ T where B ∈ {0, 1} q×q is a minimal role matrix and Z ∈ {0, 1, −1} q×q , i.e., the signs are placed in elements of Z, the unsigned graph |A| = QAQ also has (unsigned) ideal structure. This is easily seen by considering the relevant factorizations of A and |A|. Suppose A = ZBZ T , where B ∈ {0, 1} q×q is a minimal role matrix, and Z ∈ {0, 1, −1} n×q where each row has exactly one nonzero element. A diagonal sign matrix Q satisfying Q 2 = I is easily constructed using the signs of the single nonzero in each row of Z so that |A| = QAQ andZ = QZ has a single nonzero equal to 1 in each row. The unsigned ideal factorization of |A| is therefore |A| =ZBZ T .
Assuming A is checkerboard, i.e., a Q is known, the other direction is also easily deduced. If |A| = QAQ =ZBZ T is an unsigned ideal factorization with minimal B then A = Q|A|Q = QZBZ T Q T = ZBZ T where Z has a single nonzero equal to 1 or −1 in each row. So a checkerboard A has signed ideal form if and only if |A| has unsigned ideal form.
For (5.1) we have A = ZBZ T , |A| =ZBZ T , rank(A) = rank(B) = q = 3 and Since the vectors z i that define Z and the node-to-role mapping may contain both +1 and −1, B does not reflect the mixed sign checkerboard of A. If each role for which z i has both signs is split into two roles then a mixed sign checkerboard generalized role matrix,B, is defined with dimension no larger than 2q × 2q. For this A,B =ẐBẐ T has 5 signed roles witĥ

Weighted Graphs
In practice, many networks have edge weights in their graphs. Much of the theory developed above can be applied to a weighted matrix W that is symmetric and rank one, i.e. W = dd T . This is an example of a weighted adjacency matrix A W = W • A (where • denotes the elementwise matrix product) that can be rewritten as A W := DAD, where D = diag(d 1 , . . . , d n ) and A is the unweighted adjacency matrix. For such weighted graphs, the adjacency matrix of the ideal graph case becomes A W = DAD = (DP Z)B(DP Z) T , with B ∈ {0, 1} q×q . If we use the permuted weight matrix D P = P T DP and the corresponding scaled matrix Z D := D P Z, we obtain a decomposition of the same type as for the unweighted case and with the same matrix B : This shows that we should also be able to associate similarity matrices S D k to a weighted matrix A W . Since the effectiveness of the similarity matrices S k depends on the connection between adjacency matrices and Erdös-Rényi graphs, we want to maintain this connection in the scaled similarity matrices S D k , i.e. S D k = DS k D. One then finds that the corresponding recurrences for the matrices S D k are given by The singular values of the similarity matrices S D k = DS k D are clearly changing, but the rank of the similarity matrix is unchanged and the recovery of the roles is the same as for S k .
Remark 5.1. Notice that the adjacency matrix, A, of a checkerboard graph can also be considered as a weighted matrix D|A|D, where |A| is its (unsigned) adjacency matrix, and D is the diagonal sign matrix making it signed and checkerboard.

Conclusion and Future Work
In recent years, the role extraction problem has become popular as researchers have determined a general definition of roles and have developed algorithms to find role structures within networks. In this paper, we explored analytically why a recent indirect approach using the neighborhood pattern similarity measure is able extract role structures from networks, without using any a priori knowledge of the network.
For our analysis, we first focused on an ideal graph case with a minimal role matrix and showed how the role structure can be extracted from the low-rank factorization of the similarity by clustering the rows of the low-rank factor. We then analyzed the perturbed graph case and how adding or subtracting elements in the adjacency matrix changes the singular values of the adjacency matrix and the similarity matrix.
Lastly, we unified some special complex networks structures as role structures by constructing their image matrices and showing how these matrices are minimal. From our analysis of the similarity matrix, the indirect approach using the neighborhood pattern similarity measure is able to extract these structures from the network. The unification of these structures is important because it allows us to use one approach to extract any structure without any a prior knowledge of the network. For example, community detection algorithms assumed that the network can be grouped into communities. However, for some networks, there may exist overlapping community structures, which the algorithms would fail to find. This paper focused on the theoretical analysis of the neighborhood pattern similarity measure with respect to the role extraction problem. A forthcoming paper will explore the efficiency of this indirect approach compared to other indirect and direct graph partitioning and role extraction algorithms.