{'fraction_non_alphanumeric': 0.039031339031339034, 'fraction_numerical': 0.01527065527065527, 'mean_word_length': 4.630574270131537, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Community detection for interaction networks

In many applications, it is common practice to obtain a network from interaction counts by thresholding each pairwise count at a prescribed value. Our analysis calls attention to the dependence of certain methods, notably Newman--Girvan modularity, on the choice of threshold. Essentially, the threshold either separates the network into clusters automatically, making the algorithm's job trivial, or erases all structure in the data, rendering clustering impossible. By fitting the original interaction counts as given, we show that minor modifications to classical statistical methods outperform the prevailing approaches for community detection from interaction datasets. We also introduce a new hidden Markov model for inferring community structures that vary over time. We demonstrate each of these features on three real datasets: the karate club dataset, voting data from the U.S.\ Senate (2001--2003), and temporal voting data for the U.S. Supreme Court (1990--2004).

network datasets presents conceptual and computational issues that often limit the avail-ple, but commonly encountered, setting. Many "network datasets" are derived from much richer datasets that involve interactions among a group of individuals. In this case, the interaction data contain much more information than a boolean indicator of a relationship between each pair of individuals; they may also contain a count for the number of interactions over a given period, or a frequency of interaction, or some other covariate information. The karate club dataset (Zachary, 1977) is a canonical example. Here the full dataset is a two-way table of interaction counts between all individuals in a karate club. Most analyses of this dataset, however, work with the projected array of boolean indicators, with a 1 indicating that the corresponding pair of individuals had at least one interaction and a 0 indicating otherwise. Innocuous as it appears, we demonstrate the sensitivity of prior methods to the choice of threshold in the karate club dataset (Section 6.1) and two other datasets of voting behavior in the U.S. Senate and U.S. Supreme Court (Sections 6.2 and 6.3). Karrer et al. (2008) have previously studied robustness of certain algorithmic methods by measuring the variation of information with respect to random perturbations in network structure. Their measure appears to work well in discerning those networks which possess a strong community structure, but it does not address the more preliminary issue of robustness to the network sampling mechanism. This latter issue is rarely raised in network applications, but here we demonstrate the strong dependence (and therefore lack of robustness) of modularity-based approaches on the sampling procedure. Though different than the variation of information criterion, variation in the sampling mechanism is a very real obstacle faced by methods fit to thresholded network data. The sensitivity of the prevailing Newman-Girvan modularity to the choice of threshold (Figures 6.2 and 6.3, Table 1) underscores a key point of Karrer et al. (2008, p. 2), "If a small change in the network-an edge added here, another deleted there-can completely change the outcome of our community finding calculations then, we argue, the communities found should not be considered trustworthy." We further explore the extent to which the act of projecting interaction data to a network can be avoided altogether by simply modeling the interaction table as is, eliminating any concern over how the projection was chosen. With this, we show that readily available statistical methods outperform the prevailing network methods in each of our three data examples. As a particularly illuminating example, we show that a simple two parameter Poisson model for interaction counts exactly recovers the known community structure in the karate club network, while the degree-corrected stochastic blockmodel (Karrer and Newman, 2011) requires thirty-six parameters and still incorrectly specifies one individual; see Section 6.1. In modeling the data as it comes, we avail ourselves to many techniques from classical statistics, allowing us to easily interpret model output and arming our approach with considerable flexibility to handle a range of clustering problems. We demonstrate this latter point with a real data example for cluster detection in temporally varying networks; see Section 6.3.

Motivating examples
We frame our discussion around three real data examples from the social and political science literature: the karate club (Zachary, 1977), senate voting (Crane, 2015a), and supreme court voting † datasets. The karate club dataset is the canonical example for community detection in networks. The senate dataset was introduced by Crane (2015a) in the context of clustering from categorical data sequences, and here we introduce it in the realm of network analysis. The supreme court dataset consists of all U.S. Supreme Court (USSC or 'the Court') decisions during a fifteen year span of the Rehnquist Court (1990Court ( -2004; we use it to illustrate the potential for certain partition-valued Markov chains in modeling temporal clustering as well as to highlight the issues faced by other approaches in the presence of time-varying data. Each of these examples highlights a different feature of community detection, as we outline in Section 2.4.

Karate club dataset
Zachary's (Zachary, 1977) karate club dataset records the number of social interactions of thirty-four members in a karate club that experienced a split between its two leaders. †accessed at http://scdb.wustl.edu/index.php Because the resulting split of the members into two groups is well understood, the socalled karate club dataset is the canonical example for community detection in network data. Zachary (1977, Figs. 2 & 3) records both the interaction counts and the unweighted network with edges representing those pairs of individuals with a positive interaction count.
The resulting dataset is a square array with 34 rows and columns corresponding to the thirty-four members of the karate club.

Senate dataset
Crane (2015a,b) analyzed voting alignments for every bill in the 107th U.S. Senate (2001Senate ( -2003 by treating the outcome of each bill as an independent, identically distributed (i.i.d.) draw from a partition model for categorical responses. In this context, the clustering should reflect the political allegiances of the 100 senators.
By considering each vote outcome separately, those prior analyses manage to simultaneously incorporate two-way, three-way, and higher-order interactions among senators.
Here we summarize the voting alignments more simply in terms of two-way interaction counts, i.e., A ij = (N ij , V ij ) records the number of votes V ij on which senators i and j agreed out of N ij bills on which they both voted. Our approach simplifies the dataset considerably while yielding the same insights; however, the same is not true for other leading methods when fit to the projected network.
Rather dramatically, the senate dataset demonstrates the fickle nature of projecting interaction counts to an unweighted network. Over the course of the 107th U.S. Senate term, every pair of senators voted in agreement at least once, in fact hundreds of times. In this context, it is more natural to threshold based on the proportion V ij /N ij of time senators i and j agreed; however, the many possible choices of this cutoff value leave considerable influence in the hands of the data analyst. Our analysis in Figure 6.2 and Table 1 point out the lack of robustness of a leading method, Newman-Girvan modularity (Bickel and Chen, 2009;Newman and Girvan, 2004), to this choice of cutoff.

Supreme Court dataset
The Supreme Court interaction dataset has the same form as the Senate dataset, with the added feature of a temporal collection of interaction arrays over the years 1990-2004. On each of about 80 cases per year, the nine Supreme Court justices rule for one of the two sides. Justices declare no official political or ideological allegiances, but their philosophy and personal views are well documented and we expect the clustering to reflect this separation. The interaction array for a given term t records the number of times the justices voted in agreement, i.e., keeping track of how many times justices i and j agreed (V t ij ) and how many cases they both ruled (N t ij ) during term t. The dataset records these data for the judicial terms t = 1990, . . . , 2004. The collection (A t ) t=1990,...,2004 records these interaction arrays over time, and we are interested in detecting changes to the Court's ideological alignment during this period.
Models that allow for temporally varying communities in networks are important for detecting regime change in political and social science datasets. This represents an underdeveloped area with only a few attempts at establishing a viable framework (Huh and Fienberg, 2008;Snijders, 2006). Using recently developed theory from the literature on partition-valued Markov chains (Crane, 2011(Crane, , 2014, we model community dynamics in the above supreme court dataset with a hidden Markov chain on partitions. Although the Court's membership is not constant over the period we study, special properties of the chosen Markov model nullify these issues, producing sound inferences; see Section 6.3.

Summary of analysis
Each of the above examples illustrates a different aspect of modeling interaction data. The karate club analysis puts our methods on equal footing with prior approaches by showing that it performs as well (and in fact a bit better) than many prevailing techniques. The senate dataset allows us to further explore the effect of projecting data on interaction counts to a network without edge weights. The time period we study for the Supreme Court (1990Court ( -2004 has been examined previously in legal studies (Toobin, 2008) and also quantitative political science (Sirovich, 2003), but here we introduce it as an example of how to detect changes in network clustering over time. For this, we bring over some recent developments in the theory of partition-valued Markov chains (Crane, 2011).
Without the need for degree-correction or other sophisticated techniques, we show that straightforward modifications of classical statistical methods fit to the observed data outperform the community detection methods put forth by Bickel andChen (2009) andNewman (2011). To a large extent, many of our models are not at all new-our hidden Markov model for community detection in temporally varying networks is a novel contribution-but they do entail some subtle considerations of network data that have not been given much attention. Perhaps most significant is our thorough testing of the oftenoverlooked effect of sampling on network analysis, which provides a cautionary tale about misinterpreting inferences from certain state-of-the-art methods. At the very least, our analysis reiterates that Occam's razor-the simplest explanation is often best-applies just as well to network modeling.

Interaction data
All of the above datasets arise by repeated interactions among a population of individuals. We acknowledge the extensive literature on modeling relational data in economics, social and biological sciences, e.g., (Bergmann et al., 2003;Lazzarini et al., 2001); however, many of these methods deal explicitly with normal data (Li and Loken, 2002) and other data forms (Hoff, 2005(Hoff, , 2008. Other methods, such as latent space models (Hoff et al., 2002), seem amenable to network analysis, but we do not pursue these here. If at all possible, we favor the simplest model that makes sense for the given application, reaping the benefits of clarity when interpreting the inferred clustering.

General setup
All of the datasets above have the form of an array generated by repeated interactions within a population. We observe data for a finite sample S from a finite or countable In networks applications, it is common to reduce the information in A to an adjacency (The senate and supreme court datasets have A ij = (N ij , V ij ), for which the proportion t(A ij ) = V ij /N ij is a natural thresholding quantity.) From now on, we use the term network data to generically refer to interaction data. We refer to the adjacency array A * c as the projected network, which has vertex set S and edge set E ⊆ S ×S satisfying (i, j) ∈ E if and only if A * ij,c = 1.

Interpreting the data
Simple data generating models typically lead to interpretable inferences and clear insights for relational data, which commonly arise in applications with pairwise measurements on the observed sample. As mentioned above, the clarity of this interpretation can be obscured by the act of projecting A → A * c to an unweighted network. In Crane and Dempsey (2015), we advised against thresholding on logical grounds, but our analysis here demonstrates its drawbacks empirically.
We emphasize these consequences because thresholding is a common approach to obtain a projected network from interaction data in social sciences, where the network A * obtained by putting A * ij,c = 1 {Aij>c} has the interpretation of a social network where i and j are friends if they have interacted more than c times within some prespecified period of time. In principle, the distribution of this projection can be determined, but there are some subtleties introduced by the fact that the cutoff value is often chosen after looking at the data. We see the effect of this throughout Section 6.
As we will see, in the karate club dataset, the standard projection with cutoff c = 0 leads to an inferred clustering with one wrongly classified individual under the Newman-Girvan (NG) modularity (Newman and Girvan, 2004), while the projection with cutoff c = 1 leads to the correct clustering under NG modularity. It may seem harmless enough in this simple setting of the karate club, but adverse effects of network sampling on inferences are well documented (Crane and Dempsey, 2015;Lee and Jeong, 2006;Willinger et al., 2009) and one cannot be sure that inferences from sampled networks are truly reflective of the real world generating process. Table 1 demonstrates this lack of robustness of NG modularity for the senate voting data. In this case, we see that the projection algorithm is more responsible for detecting the true clustering than the algorithm: either the cutoff value is well chosen, in which case the projection effectively separates the nodes into clusters without the algorithm's help, or the cutoff destroys the structure in the data, leaving the algorithm hopeless in discovering latent structure.

Modeling the interaction array
For the datasets we consider, we need not open ourselves up to the above edge sampling issue. Instead, we opt to work with the full interaction array A = (A ij ) i,j=1,...,n in all our analyses. There are many ways to model these data without projecting to A * c , and our choice naturally depends on the features of each application. We encounter two situations in our examples: either A represents interactions among individuals over some period of time, or A represents a fixed number of interactions with each interaction having a type, e.g., agree, disagree, or undetermined in the senate and supreme court datasets. We discuss each in turn.

Interaction count data
Consider the case where A = (A ij ) i,j=1,2,... consists of a single interaction count, A ij ∈ N for every i, j = 1, 2, . . .. In the most generic setting, we let Λ = (λ ij ) i,j=1,...,n be a matrix of non-negative intensities λ ij ≥ 0. Given Λ, we assume A results from a Poisson point . For a given interaction array (a ij ) 1≤i,j≤n , we have (Note that in the symmetric setting, A ij = A ji , we consider only the counts (A {i,j} ) 1≤i<j≤n .) We refer to this model as the Poisson stochastic blockmodel below.
For community detection, we assume the population clusters according to a partition B = {B 1 , B 2 , . . .}, and we can allow the intensities Λ to depend on B in a similar fashion to the stochastic blockmodel. In this way, we define λ ij = Λ(B(i), B(j)), where B(i) is the block of B that contains i. Karrer and Newman (2011) introduce both the stochastic blockmodel and its degree-corrected version in terms of Poisson counts, just as we have here. However, they note that this is a matter of mathematical convenience, and it seems they have not taken full advantage of the added power of this approach as a model for the interaction counts directly.
For logical reasons, it may make sense to simplify the parameter space of the Poisson stochastic blockmodel further by specifying the intensity of all within-cluster interactions by a single parameter, and likewise for all between-cluster interactions. The justification for this depends on the given application. For example, if we a priori expect the interaction behaviors within different clusters to be similar, then it makes sense to choose the simplest available model by putting λ ij = λ in if i and j are in the same block of B and λ ij = λ out otherwise. This gives the resulting clustering a clear interpretation in terms of the specified model and avoids potential issues of overfitting.
Even in the absence of any intuition for the cluster behavior, the interest of elegance and parsimony suggest that it is best to cut down on additional parameters whenever possible, especially since the clustering B is our main interest. As a rule of thumb, McCullagh and Yang (2008) suggest at most 5 parameters, and in our analysis we never need more than 2. This is a stark contrast to the approach of the degree-corrected stochastic blockmodel, which in general has on the order of n + k 2 parameters for a sample of size n and partition B with k clusters.
As we demonstrate in Section 6.1, the Poisson stochastic blockmodel with two parameters (λ in , λ out ) fit to the interaction counts recovers the correct clustering in the karate club dataset without the need for degree-correction (Karrer and Newman, 2011) or other constraints (Bickel and Chen, 2009). The best known performance of these latter approaches incorrectly classifies one individual.

Interactions with types
In the Senate and Supreme Court datasets, the interaction array A = (A ij ) 1≤i,j≤n includes more information than simply the number of interactions between senators or judges. Here we interpret interactions in the context of bills voted (resp. cases ruled) on by the U.S.
Senate (resp. U.S. Supreme Court), and we define an interaction between senators (resp. judges) i and j as a bill (resp., case) on which the two senators (resp., judges) both voted (resp., ruled). Each interaction, therefore, has a type agree and disagree, and we observe a pair A ij = (N ij , V ij ) with N ij the number of interactions between i and j and V ij is the number of times they agreed.
It is natural to assume that "non-interactions," i.e., bills or cases for which at least one of i and j was absent, occur completely at random and independently of the observed interactions. Prior analyses of the Senate and the Supreme Court make these assumptions without any apparent ill effects; we expect the same here as such instances are rare relative to the overall number of interactions. Given N = (N ij ) 1≤i,j≤n , therefore, we model V = (V ij ) 1≤i,j≤n as independent Binomial random variables with success probabilities In general, the probability of a given observation A = (a ij ) 1≤i,j≤n based on N = (n ij ) 1≤i,j≤n and (p ij ) 1≤i,j≤n is (4.2) We incorporate clustering into the model just as for the above Poisson stochastic blockmodel by regarding P : B × B → [0, 1] as function on pairs of blocks and putting p ij = P (B(i), B(j)). We call this the Binomial stochastic blockmodel.
In the senate dataset below, A is symmetric and we fit the simplified Binomial stochastic blockmodel with two parameters p in , p out ∈ [0, 1] and In this case, the distribution in (4.2) simplifies to pr(A = (a ij ) 1≤i,j≤n ; (n ij ) 1≤i,j≤n , B, p in , p out ) = (4.3) where B(i, j) = 1 if i and j are in the same block of B and B(i, j) = 0 otherwise. We also note that the choice to view all within cluster edges (via p in ) and all between cluster edges (via p out ) interchangeably is a logical choice based on our prior understanding of the U.S. Senate and Supreme Court. We discuss this further in Sections 6.2 and 6.3.
Generally, partitions with a small number of clusters relative to the sample size are most informative, and until recently there were no known partition-valued Markov chains with suitable properties for this application. Using the Ewens cut-and-paste chain (Crane, 2011(Crane, , 2014, we specify parameters α > 0, k ≥ 2 (the maximum number of clusters in each B t ) and we model a partition sequence (B t ) t=0,1,... with transition probabilities where π, π are partitions of [n], #π is the number of non-empty clusters of π, #b is the cardinality of cluster b ∈ π, k ↓j = k(k −1) · · · (k −j +1), and α ↑j = α(α+1) · · · (α+j − 1). This family of transition probabilities is reversible with respect to the Ewens-Pitman distribution with parameter (−α, kα):  (2003) and Thurstone and Degan (1951), are restricted to short periods of time during which the Court's membership remained constant.
Reversibility is also a natural property since, although the arrow of time invariably moves toward the future, there is no logical mandate against analyzing the data in the reverse direction. Moreover, since we seek to detect regime change, it is important that the model does not bias the sequence in any way. Without knowledge to the contrary, we assume that each B t obeys the same marginal distribution, i.e., the chain evolves in equilibrium. In this way, detected changes in (B t ) t=1990,...,2004 reflect meaningful information in the data instead of arbitrary defects in the model.

Cluster analysis
All our analyses below proceed by optimizing an objective function, i.e., likelihood, posterior, or modularity measure, over the space of partitions of [n]. Where scalar parameters, generically denoted θ, are present, we can often compute unbiased, or asymptotically unbiased, estimates in closed form, which we profile out when searching for the optimal clustering. Given an observed interaction array A = a, we write g(B; θ, a) as the generic objective function and we seek to solve Similarly for temporal clustering, we seek the sequence (B t ) t=0,1,...,T with the largest posterior probability. This latter activity is, in general, quite computationally challenging; however, we leverage properties of the chosen model to mitigate these issues. Using the stationarity of the hidden Markov chain for (B t ) t=0,1,...,T , we build up our estimated temporal clustering sequence sequentially. We begin with the initial state B 0 , which we equip with prior as in (4.5) with k = 2 and α set to 1-sensitivity analysis shows that our estimates are robust to this choice of α-and we take the posterior mode based on the observed interactions in A 0 as our estimateB 0 . To estimate B t+1 , given A t+1 and (B t , . . . ,B 0 ), we use the conditional distribution in (4.4) from stateB t as our prior and again take our estimateB t+1 as the posterior mode. Therefore, our estimate for (B t ) t=0,1,...,T amounts to a slightly modified version of the search algorithm below. A search over possible perturbations of the inferred sequence (B t ) t=0,1,... obtained in this way does not find any improvements.

Randomized search algorithms
When the sample size is moderate to large, the space of partitions is too big to search exhaustively during cluster detection. To optimize the objective function (5.1), we use the following randomized search algorithm which has been proven to efficiently search the space of partitions with a bounded number of blocks (Crane and Lalley, 2013) and has been used effectively in previous clustering applications (Crane, 2015a,b). For Newman-Girvens modularity, we employ the label-switching algorithm from Bickel and Chen (2009). The benefit of our algorithm over previous randomized algorithms, e.g., the split-and-merge algorithm used by Booth et al. (2008), is that we can restrict ours to only search over partitions with a maximum number of clusters, making the search much more efficient.
Our search algorithms iterate between local-and global-move Markov chains on the space of partitions. In all our applications in this paper, we fix the maximum number of clusters k. (Note that in the case of the hidden Markov model above, k here is the same value as in (4.4). They both correspond to the maximum number of clusters in B.) To ensure the global moves do not suggest partitions with more than k clusters, our algorithm proposes moves according to the transition probabilities in (4.4) with parameterα > 0 that is logically unrelated to the parameter α > 0 in the model. Importantly, k is only an upper bound on the number of clusters, so our choice of k does not mandate exactly k clusters as, e.g., k-means (Lloyd, 1982) and Gaussian mixture models (Banfield and Raftery, 1993).

Global search: cut-and-paste algorithm
Forα > 0 and k = 1, 2, . . ., the Ewens cut-and-paste chain with parameter (α, k) evolves on partitions of [n] with at most k blocks according to the transition probabilities in (4.4).
Here we describe how to efficiently generate transitions in this chain according to the cutand-paste procedure. Let π = {b 1 , . . . , b r }, r = 1, . . . , k, be the current state of the chain.
The next state is obtained as follows: The most attractive feature of the cut-and-paste chain is that it assigns strictly positive probability to any transition in the search space (and therefore moves around the space quickly). This intuition is supported by rigorous proof that it converges to its stationary distribution in O(log n) steps (Crane and Lalley, 2013), where n is the number of vertices.

Local search: cocktail algorithm
Forα > 0 and k = 1, 2, . . ., the cocktail algorithm evolves on partitions by updating one element at a time. Let π be the current state of the chain. First, an element u ∈ [n] is sampled uniformly at random and removed from π to obtain π [n]\u . Given π [n]\u , the removed element u is reinserted into π [n]\u according to the seating rule of the (−α, kα)-Chinese restaurant process: At each step, this chain is distributed according to (4.5) and, therefore, is confined to partitions with at most k blocks.
By iterating between the local and global chains, our search algorithm explores the partition space for local and global maxima. To effectively use this algorithm, we take a step in the global chain followed by a prespecified number of moves in the cocktail algorithm. We accept all moves in the global chain, and we accept moves in the cocktail chain according to the Metropolis-Hastings algorithm. This choice reflects our observation that local maxima often occur only a few steps away from partitions with low likelihood, and so rejecting global moves can be counter-productive to search. The efficiency of this method is apparent in our application for the senate dataset (Section 6.2), where we use it to search over all partitions of 100 senators into at most two blocks, starting in a randomly chosen starting state. This space consists of 2 99 ≈ 6.3 × 10 29 partitions, but our algorithm converges quickly to the right answer on a laptop computer.

Karate club
We fit the Poisson stochastic blockmodel to the full interaction array from the karate club dataset. To best compare with previous methods, we found the best fit with at most two clusters and two parameters λ in , λ out > 0 for within-and between-cluster intensities. Our inferred clustering in Figure 1(iii) (based on maximum likelihood for (4.1)) is correct according to the analysis in Zachary (1977). Under our model the likelihood for this correct clustering is −348.26 with estimated intensities (λ in ,λ out ) = (0.615, 0.066), versus −349.81 with (λ in ,λ out ) = (0.618, 0.066) for the clustering found by the degree-corrected stochastic blockmodel and Newman-Girvan modularity in Figure 1(i). We point out that our analysis does not contradict the findings of Karrer and Newman (2011), who report that the Poisson stochastic blockmodel without degree correction "fails to split the network into the known factions." That conclusion is based on fitting the generic Poisson stochastic blockmodel with different within-cluster intensities λ in,1 , λ in,2 > 0 to the projected network data. Given this flexibility, it is not surprising that the clustering divides the group into high-and low-degree individuals, as that inference also has a reasonable and clear interpretation in terms of the given model. In our view, it is not fair to conclude that the Poisson stochastic blockmodel failed in this instance, as Karrer and Newman claim. By separating the highly connected individuals into a single cluster, the detected clustering does accurately extract a low resolution overview of the network. That this does not coincide with the desired "true" clustering suggests only that the specified model was not set up to detect two clusters of similar size and characteristics. The network reported by Zachary has the feature that the two clusters exhibit similar characteristics, and our choice of λ in,1 = λ in,2 reflects our interest in detecting the best such clustering. This constraint is also consistent with our prior understanding of the karate club dataset, for which we have no a priori reason to expect within-cluster social interactions of different clusters to be substantially different. Our constraint, therefore, allows us to pool information from the two clusters, obtaining the correct split.
As Karrer and Newman (2011) report, the degree-corrected model returns a better clustering than the Poisson stochastic blockmodel with three parameters λ in,1 , λ in,2 , λ out > 0 but only after introducing a new degree-correction parameter for each of the thirty-four individuals in the network. Instead of decreasing the number of parameters to two and recovering the correct clustering, the degree-corrected model increases the number of parameters to thirty-six and still incorrectly classifies one individual.

Fitting the projected network
While our analysis of the full interaction data (the multigraph in Figure 1(iii)) recovers the correct clustering as reported by Zachary (1977), A closer look at the data explains the discrepancy. The misclassified individual is connected to the most highly connected vertices in both clusters, i.e., one interaction with the highest degree vertex in the left cluster (black squares) and two interaction with the high-  projected networks is much more pronounced on the senate dataset, as we now show.

Senate voting
While studying clustering methods from categorical data, Crane (2015a) analyzed voting data from the 107th U.S. Senate. The U.S. Senate consists of 100 elected individuals, each of whom vote yea or nay on a series of amendments. Using a three-parameter extension of the Ewens-Pitman two-parameter partition model (Ewens, 1972;Perman et al., 1992), Crane (2015a) detected a partition into two equally sized clusters, but with one Democrat and one Republican defecting into the opposing cluster. Here the interaction array A contains information about votes of different types, as we discussed in Section 4.2. We fit the    but Figure 6.2(ii) illustrates that this is due entirely to the choice of projection. Upon projecting to the network in panel (ii), we could determine the clusters by visual inspection, without any need to run an algorithm.
While not explicitly discussed by Bickel and Chen (2009), Newman-Girvan modularity can be used on the weighted matrix T such that T ij = t(A ij ) = V ij /N ij . In the case of the senate, the true clustering does maximize NG modularity based on the weighted matrix T , but there are several other local optima with the same modularity. In this case, NG modularity cannot confirm nor deny the true clustering.

Temporal clustering in the Supreme Court
For inferring temporally-varying community structure, we consider the collection of in-  (Irons, 2006;Toobin, 2008) point out a shift in his judicial philosophy, from initially conservative to more liberal in 1993. Prior quantitative analyses of the Court detect this change in ideology, e.g., by the ideal points method of Martin and Quinn (2002). Those analyses generally incorporate much more information about Supreme Court jurisprudence, such as details about specific cases, but our inferred clusterings in Table 2 obtain the same inference with only the interaction array data (A t ) t=1990,...,2004 .
As an algorithmic method, Newman-Girvan modularity is not properly equipped to handle dependence over time. To illustrate the benefit of smoothing temporal irregularities with the hidden Markov chain, we fit the Newman-Girvan modularity independently to projection data from each term. Although each term has a window of percentile cutoffs for which the algorithm detects the true clustering, these windows move substantially from term to term, and visual inspection of the figure says that no single choice of threshold yields the correct clustering for every term.

Concluding remarks
If considered within the proper context, classical methods may have potential in network applications, as they can be readily built upon for more advanced statistical inference. Our analysis of temporal variation ideological clusters within the U.S. Supreme Court embodies a healthy cross-fertilization with ideas in the applied and theoretical probability literature.
Combining this with the straightforward Binomial stochastic blockmodel of Section 4.2, we correctly detect David Souter's ideological shift after his third term. By comparison, the Newman-Girvan modularity, or any algorithmic method we know of, cannot adequately deal with temporal variation in the underlying clustering. In picturesque fashion, Figure   6.3 points out that no single choice of cutoff yields the true latent clusters for all years in the supreme court dataset. Proceeding from first principles, we have found that straightforward modifications of standard statistical methods perform just as well as prevailing clustering algorithms and blockmodel approaches for detecting communities in interaction datasets. At some level, our analysis reiterates the common sense notion that throwing away data adversely affects inference. At a deeper level, it is a call to think deeply about the role sampling plays in any network inference, an issue that has been raised by some (Crane and Dempsey, 2015;Lee and Jeong, 2006;Willinger et al., 2009) but is largely ignored in the methodology literature. If nothing else, our investigation calls special attention to the precarious behavior of the Newman-Girvan modularity with respect to the mechanism by which network data is sampled from interaction counts.