The goal of this work is to help social scientists, such as historians and sociologists, create meaningful clusters from social networks they study. In contrast to the belief that most data is easily available on the Web, as of today, most social scientists spend a long time collecting data to construct social networks based on documents or surveys. Many projects involve a long data generation process, searching archives, interviewing participants, analyzing documents, and generating medium-sized networks (50-500 vertices), followed by careful and detailed analysis of all the relationships. Before the start of the cluster analysis a great deal of effort goes into analysing other data and gathering knowledge (which we call prior knowledge in the rest of the paper).
Social scientists study in great details the network entities (most of the time people), and the social ties they weave together, as it is the unit brick with which they can make historical or social hypothesis and conclusions. When the network is small, less than 30-50 nodes, it is possible to remember most of the relations and persons and visualization directly helps to show groups, hubs, disconnected entities, outliers, and other interpretable motifs.
However, when the network grows larger, with hundred entities or millions of them, it becomes impossible to perform the visual analysis only at the entity level. The graph has to be summarized, and typically the social scientist wants to organize it in social communities. A large number of algorithms are available today to compute clusters of entities from a graph, with the assumption that the computed clusters represent faithfully the social communities. However, most social scientists are not familiar with all of the available algorithms and are challenged to choose which algorithm to run, with which parameters, and how to reconcile the computed clusters with their prior knowledge. Furthermore, the clusters computed by the algorithms do not always align with the concept of community from the social scientists.
Typically, social scientists select an analysis tool based on their familiarity with the tool and the level of local or online support they can access. Therefore, they most often use popular systems such as R [37] , Gephi [16] , Python with NetworkX [32], or Pajek [33] . To compute clusters, they follow a strained process: they select and run algorithms provided in the tool and then try to make sense of the results. When they are not satisfied or unsure, they iteratively tweak the parameters of the algorithms at hand, run them again and hope to get results more aligned with their prior knowledge (see the diagram on the left in Fig. 2 ). This analysis process is unsatisfactory for three main reasons:
1. it forces them to try a sometimes large number of black-box algorithms one by one, tweaking parameters that often do not make sense to them; 2. even when a parameter makes sense to them, such as the number of clusters to compute, k in k-means clustering, they have no clue of what value would generate good results, and are left with trial and error; 3. even if they could painstakingly evaluate the results of all clustering algorithms according to their prior knowledge, no existing system allows users to do so easily, leading users to give up and blindly accept the results of one of the first algorithms they try. Those complaints have been heard repetitively during the decades our team has worked with social scientists.
Moreover, clustering is an ill-defined problem: for one dataset, there is no ground-truth, and several partitions can be considered good according to the metric chosen to evaluate the result [26] . In a Social Sciences setting, this means, for example, that the same social network could be clustered to find families, friend groups, or business relationships. One partition is not better than the other: it depends on what is the purpose of the analysis. This problem increases the need for interactive tools, which lets the user specify which type of partition he expects for his analysis.
To address those issues we propose a novel paradigm, called PKclustering, which allows social scientists to iteratively construct and validate clusters using both their prior knowledge and consensus among clustering algorithms. A prototype system illustrates that paradigm.
Our new paradigm includes three main steps (see Fig. 2 ) (1) Prior Knowledge specification. Users introduce their prior knowledge of the domain by defining partial clusters. The tool then runs all available clustering algorithms.
(2) Consolidation of the expanded Prior Knowledge clusters. Users review the list of algorithms, ranked according to how well they match the prior knowledge. They compare results and consensus, then accept or ignore suggestions to expand the prior knowledge clusters (3) Consolidation of extra clusters. The tool suggests extra clusters on unassigned nodes. The user reviews consensus on each proposed cluster, then accepts or rejects suggestions.
The output of the process is, using a direct quote from a social scientist providing feedback on the prototype: "a clustering that is supported by algorithms and validated, fully or partially, by social scientists according to their prior knowledge".
According to the need to combine data mining with visualizations [41] , and inspired by the idea of letting the user collaborate with the machine to reach specific goals [20] , this paradigm follows a mixedinitiative Visual Analytics process, which provides social researchers high-level control over the clustering process. The user actions inform the system about the relevant items to take into account to guide the underlying model to compute the solution [13] . Mixed initiative may be interpreted as the separate use of automation first (e.g. for sentiment analysis) followed by the visual and interactive exploration of the augmented data, e.g. [10] .
In our case, users focus on the results that expand on their prior knowledge, filter-out the most implausible results, change focus when they realize that several clustering algorithms are consensual, despite not matching the prior knowledge, hinting at other possible meaningful structures. More typically, the mixed initiative allows social scientists to seed the clustering process with a small set of well-known entities that will be quickly and robustly expanded into meaningful clusters. The details of the process are presented in Sect. 3.1. Contrary to a current trend [31] , we do not aim to improve the interpretability of algorithms but to improve the interpretation of the results of black-box algorithms in light of prior knowledge, provided by the user.
Every day, we use complex mechanisms that we do not fully under-stand, like motorbikes, cars or electric vehicles using various kinds of engines, shifts, and gears, but we are still able to choose which one best fit our needs according to their external utility and not by understanding their complex internal machinery. In addition, it is usually more important to social scientists to find an algorithm that provides useful results than to understand why another algorithm failed to do so. The main contributions of this article are: 1. a new interactive clustering paradigm; 2. a prototype (shown in Fig. 1 ) implementing PK-clustering with 13 clustering algorithms of different families applied with different parameters configurations; 3. two case studies.
Our paradigm relies on several families of clustering methods and the visualization and exploration of their results. We first describe a brief overview of clustering for graphs, as well as semi-supervised methods, then several works in the literature related to visualization with a focus on groups in networks and ensemble cluster visualization.
One property of social networks is their community structure [17] , which means that nodes are not connected randomly but tend to form tightly connected groups, known as communities or clusters, with a high density of edges compared to the rest of the graph. Nodes in the same community often share common properties or roles in the network. In a social network setting, a community can mean a lot of things like families, workgroups, or groups of friends. There is abundant literature on clustering methods to find these communities for social networks and new algorithms are created each year. The majority of the research is made only on topological algorithms, i.e. algorithms which use only the structure of the network to find clusters. [15] proposes a description and a classification of these various algorithms, which can be separated as divise algorithms, modularity-based methods, spectral algorithms, statistical inference methods, dynamic algorithm, or others.
Even if the majority of studies are based on simple graphs, real-word phenomena are often best modeled with bipartite graphs, also known as 2-mode networks. It is the case for social scientists, who often build their networks from raw documents containing mentions of people. In that case, it is more straightforward to use the persons as one set of nodes, the documents as the other one, and linking an individual to a document if he is mentioned in it. This is one of the reasons some research is made on bipartite graph community detection [1] .
Moreover, recent new approaches try to use the attributes [50] of the nodes and the dynamic aspect of the networks [35] to find more relevant communities. Some toolkits offer a large number of algorithms; for example, the Community Discovery Library (CDLIB) [36] implements more than 30 clustering methods with variations inspired by 67 references.
In semi-supervised clustering the user integrates the data mining task with side information that helps the clustering task to provide better results in terms of minimizing the error made in assigning the correct cluster to each data of interest. Semi-supervised clustering can be divided into constraint-based clustering and seed-based clustering.
In constraint-based clustering, the most common form of constraints used are: must-link (ML) and cannot-link (CL) constraints [4, 47] . ML(x, y) indicates that two datum, x and y, belonging to the data set must be grouped in the same cluster, while CL(x, y) means that x and y must belong to different clusters.
In seed-based clustering, a small set of seeds is provided to help the clustering process. Several works in the literature addressing seedbased clustering have been proposed, such as: K-Means (SSKM) [2] , seed-based Fuzzy-CMeans (SSFCM) [5] , seed-based hierarchical clustering (HISSCLU) [6] , seed-based Density-Based Clustering (SSDB-SCAN) [29] , and graph-based clustering [47] . Problems are related to the topology of the graph or the computational capability. According to [40] , seeding, and then expanding is a common scheme to discover Swant and Prabukumar propose a review of graph-based semisupervised learning in the specific domain of hyperspectral images [39] . The graph is constructed with nodes and edges, where nodes are specified by samples that may be labeled. The edges are used to specify the similarity among the samples. The graph technique classifies unlabelled samples according to the weighted distance from the labeled samples. The process involves two stages: the construction of the graph adjacency matrix, and the computation of graph weights.
Jianu et al. [24] evaluate four techniques for displaying group information overlaid on node-link diagrams: node coloring, GMap, BubbleSets, and LineSets, and show that BubbleSets is the best alternative for tasks involving group membership assessment. But, visually encoding group information over basic node-link diagrams incurs an accuracy penalty of about 25 percent in solving network tasks. Another finding is that the use of GMap of prominent group labels improves memorability [24] . The same four techniques have been evaluated by Saket et al. [38] , defining a new set of tasks that assess group-level comprehension.
Holten proposes edge bundling on compound graphs. He bundles together adjacency edges, making explicit group relationships at the cost of losing the detailed relationships [19] . Buchmüller et al. proposes a technique for visualizing moving groups of entities over space and time [9] . In their work they provide a visual interpretation of a MotionRug, highlighting the vertical variation in position over time/space. A good example of manual grouping and tagging is SandBox, which allows users to organize bits of information and their provenance in order to conduct an analysis of competing hypotheses [49] . A state of the art (STAR) on the visualization of group structures in graphs is proposed by Vehlow et al. [45] . They also proposed SurVis, an interactive online tool that collects works presented in the STAR [43] .
An ensemble in the context of machine learning can be defined as a system that is constructed with a set of individual models working in parallel whose outputs are combined with a decision fusion strategy to produce a single answer for a given problem [48] . Several strategies exist for combining multiple partition of items in a clustering setting [42] . Concerning visualization research, Kumpf et al. consider ensemble visualization as a sub-field of uncertainty visualization, for which some surveys exist [7, 30] . They propose an interactive visual interface that enables simultaneous visualization of the variation in composition of identified clusters, variability in cluster membership for individual ensemble members and uncertainty in the spatial locations of identified trends [28] . They aim at identifying ensemble members that can be considered similar and propose three different compact representation of clustering memberships for each member.
The community detection problem in graphs has been studied in a lot of different settings. We can classify it this way from the user perspective:
• Standard clustering: one algorithm is picked with a set of parameters and the user check if the results are consistent with his prior knowledge, which is not represented in the process.
• Ensemble clustering: many algorithms run with potentially many parameters, and a final partition is obtained by trying to merge optimally the partitions. At the end of the process, one clustering is given to the user who has to check if it is consistent with the prior knowledge, not represented either.
• Semi-supervised clustering: the user provides the prior knowledge and lets the algorithm propose a final solution using this information in its computation. The results should be good by design, regarding the knowledge of the user.
The aim of our proposed framework is to combine these three approaches, to integrate the user in the analysis loop and allow him to have a better impact on the final community detection result.
We present a new approach, inspired by the three types of clustering methods described in Sect. 2.5: Standard clustering, Ensemble clustering and Semi-supervised clustering. It consists in running a set of algorithms, then proposes those that best match the prior knowledge provided by the domain expert. A Mixed Initiative interface helps the user to review and compare the results of selected algorithms, and consolidate a satisfactory and consensual partition.
PK-clustering is not tied to any specific graph representation technique and could be used to augment any of them. Our prototype being implemented in the PAOHVis tool [44] it illustrates how users can view their networks as PAOH (Parallel Aggregated Ordered Hypergraph) or traditional Node Link diagrams. PK-clustering relies heavily on having a list of nodes, so the PAOH representation is naturally adapted to pk-clustering, and will be used in the figures.
After a general overview of the process we describe each step in more details, illustrated with screen samples of the analysis of a small fictitious network.
PK-clustering is a paradigm where the user and the system take turn to construct and validate clusters. The process involves three main steps (see Fig. 2 ) each with several activities. The blue boxes describe the user activities while the yellow boxes describe the system activities. After loading the dataset, the process is as follows:
(1) Prior Knowledge specification.
1. The domain experts interactively specify the PK (prior knowledge) by defining groups, i.e. naming groups and assigning entities to them. Typically, an expert would assign a few items (1-3) to a few groups (2-5), thus creating a set of partial clusters. 2. All available clustering algorithms are run. Algorithm parameters may also be varied automatically (e.g. number of clusters), resulting in additional results. Depending on the type of algorithm, topology and/or data attributes are used. The specified PK is used by the semi-supervised algorithms, which are the only ones able to use it. (2) Consolidation of the expanded Prior Knowledge clusters.
3. Users review the ranked list of algorithms. They can see if the algorithm results match the PK completely, partially or not at all. Information about the number of clusters generated by each algorithm is also provided. Users select the set of N algorithms they think are the most appropriate. 4. The consensus between the selected algorithms is computed and visualized next to the graph visualization (in the PAOHVis display in our prototype) 5. First, users review and compare the suggestions made by the algorithms to expand the PK-groups into larger clusters, and examine consensus between algorithms. 6. Then they accept, ignore or change the cluster assignments. This consolidation phase is crucial, as users take into account their knowledge of the data, the graph visualization (shown in the same display), and the results of the clustering algorithms to make their choices.
(3) Consolidation of extra clusters. 7. The system proposes extra clusters using nodes that have not being consolidated yet and remain unassigned. Users can select any algorithm and see the extra clusters it suggests. 8. For each proposed cluster users can see if other algorithms have found similar clusters and then consolidate again by accepting, ignoring or changing the suggestions for all nodes in the proposed cluster. This step is repeated with other clusters until the user is satisfied. At any point users can go back, select different algorithms, or even change the PK specification to add new partial clusters. Users can also opt not to specify any PK partial clusters at all, and accept all consensual suggestions without reviewing them in details. This gives users control over how much they want to be involved in the process. Similarly, users are not required to assign every single node to a cluster.
By specifying the PK in the first phase, i.e. before running the algorithms, users avoid being influenced by the first clustering results they encounter. The process leads users to algorithms whose results match prior knowledge, but it also allows them to review results that contradict their prior knowledge.
We believe that PK-clustering addresses the important problems identified in the introduction: it helps users decide which algorithm(s) to use, facilitates the review of the results taking into consideration both the consensus between algorithms and the knowledge users have of their data. We will now review each step in more details. 
We ask users to represent prior knowledge as a set of groups. Each group contains the node(s) that the expert is confident belong to the defined group. In the case of Fig. 3 , each of the two prior knowledge groups contains two nodes, and it specifies that the user is expecting to see at least two clusters, with the first two people in a blue cluster A, and the other two in a red cluster B. This representation expresses mustlink and cannot-link constraints described in Sect. 2.2 in a simple visual and compact form. It is not required to specify all binary constraints because the information is derived from the prior knowledge groups.
Our prototype includes 9 algorithms taken from three families:
Attribute based algorithms. Graph nodes can have intrinsic or computed attributes that can be used for grouping. For example, gender, family name and age. Some community detection algorithms use such attributes alone or together with the topology to partition the graph. The clustering algorithms consider attributes according to their type: Categorical attributes (e.g., male / female): finds matching attributes and merges if necessary (e.g., need to merge 2 categories to match better). Numerical attribute (e.g., income): in order to match the clusters the algorithm seeks for intervals. Such intervals can be adjusted for propagating clusters. Algorithms in this family can also use multiple attributes together.
Topology based algorithms. Most of the clustering algorithms consider only the graph topology [3] and try to optimize a topological measure such as modularity [8] . Those algorithms only use the connections between the people to find groups. Their aim is to find groups of nodes such that the density of edges is higher between the nodes of one group than between the group and the rest of the graph.
Propagation / Learning based algorithms. Semi-supervised machine-learning algorithms learn from an incomplete labeling of data and use it to classify the rest of the data. They represent a class of Machine Learning methods, also called label propagation methods, which can take into account users' Prior Knowledge groups in its computation of the clusters. By definition, this type of algorithm will always provide a perfect match with the Prior Knowledge. If the Prior Knowledge makes no sense, this type of algorithm will still give a community structure following this input.
Our prototype implements 2 attribute based algorithms (one for numerical attributes and the other for categorical attributes), 6 topology based algorithms and 2 propagation based. In addition, since we often deal with hypergraphs we also implemented 2 bipartite node clustering algorithms: Spectral-co-Clustering [11] and Bipartite Modularity Optimisation. Since the majority of community detection algorithms are for unipartite graphs, we perform a projection into a one-mode network [51] . Basically, each pair of nodes which are in the same hyperedge are connected together in the resulting graph, with a weight being the number of shared hyperedges. [18] .
Some algorithms require parameters to be specified. We do not ask the user to specify values for such parameters but when possible infer it from PK-groups. For instance, instead of using an arbitrary default number for the parameter k, i.e the number of expected clusters, we run the algorithm several times with a few values of k, with the minimum value being the number of specified PK-groups. Once all the algorithms finish the computation, we try to match the resulting partitions with the PK to assess the quality of the results.
Once a clustering is computed, we want to know how well it is compatible to the PK, and if possible, match every PK-group with a specific cluster. We use the edit distance to measure this matching, as its computation allows us to directly link each PK-group to a specific cluster. Given two partitions, the edit distance is the number of single transitions to transform the first partition into the second one. For example, the edit distance between the two partitions of 4 nodes P 1 = {{1, 2, 3}, {4}} and P 2 = {{1, 2}, {3, 4}} is 1 because moving the node 3 from the first to the second set of P 1 would transform it into P 2 . A clustering can be seen as a partition since every node has a label, but the PK can only be seen as a partial partition because only some nodes are labeled. We say that the edit distance between the PK and a clustering is 0 if every group of the PK is a subset of an exclusive cluster, i.e. if every person of a PK-group is retrieved in the same cluster, with no overlaps. Thus, we define the edit distance as the number of node transitions between the groups of the PK to get to the state where each group is a subset of an exclusive cluster.
To compute the edit distance, and therefore the matching, we first build a bipartite graph: each meta-node of the first set corresponds to a group of the PK, and each meta-node of the second set to a cluster. We then link them if they share a node, with weight being the number of shared nodes. Computing the edit distance and producing a matching between the PK-groups and the clusters is then equivalent to the assignment problem, where the goal is to find a maximum-weight matching in the graph, in which the sum of weights of the edges is maximum [27] .
Once this matching is computed, the total sum of the weights minus the sum of the weight of the matching is equivalent to the number of transitions needed to transform the first partition into the second one (or the PK into a sub-partition where each set is an exclusive subset of the sets of the second partition), i.e. the edit distance.
For example, given a clustering of 12 nodes N = 1, 2, . . . , 12, the clusters C 1 = [1, 2, 3, 4], C 2 = [7, 9, 10, 12] and C 3 = [5, 6, 8, 11] and a PK composed of 3 groups PK 1 = [1, 2], PK 2 = [5] and PK 3 = [3, 7] , the maximum-weight matching is given by the edges (PK 1 ,C 1 ), (PK 2 ,C 3 ) and (PK 3 ,C 2 ). This is illustrated in Fig. 4 . The edges of the matching correspond to the matching between the PK-groups and the clusters. The edit distance is then equal to the sum of all the weights of the bipartite graph minus the sum of the weights of the maximum matching (in red), thus equaling 5 − 4 = 1. In other words, we only have to move the node 3 from PK3 to PK1, for every PK-group to be a subset of a unique cluster, with no overlap.
In the end, we hope to find matches linking every PK-group to one specific cluster, with no overlaps. This is not always the case and sometimes two or more PK-groups are subsets of the same cluster. In that case, it is not possible to link all theses PK-groups to the same cluster since we want one unique cluster for each group. Thus, we say that the algorithm failed to match the prior knowledge and we do not summarize it visually.
Using the edit distance measure, the algorithms can be ranked. We also introduce a parsimony criteria when dealing with computed clusters: an algorithm that produces results matching the prior knowledge can be better than another one if it produces fewer clusters overall. Thus, a simpler algorithm with the same score is preferred.
To complement the parsimony rule, we also consider that the family of propagation/learning based clustering algorithms is more complex than the two previous families (attribute or topological based clustering). If a simple and a complex algorithm match the prior knowledge, the simpler one should be presented first. For example, if grouping by the attribute "profession" provides a perfect match, then it is ranked higher than a machine-learning method achieving the same perfect match.
Once the clustering algorithms have been matched with the PK, users can review the list of algorithms, ranked by how well their results match the PK. Fig. 5 shows two modalities to visualize the ranked list (individual nodes, and aggregate representation). We will describe in details the first modality, which shows individual nodes as small colored circles (also used on the left of Fig. 1) :
Each row is an algorithm, and the algorithms are grouped by family. On the right of the name of the algorithm we can see a representation of the clusters that best match each of the PK-groups. In Fig. 5 we first see the cluster which best matches the blue PK-group, and then the cluster which best matches the red PK-group. In each cluster we see colored dots for each person than matches, and dark gray dots with a X for no match. Additional nodes in the cluster are represented as a white dots with a number next to it. On the right most we see how many other clusters (if any) have been found by the algorithm -also represented as white dots with a number next to it.
So for example, the second algorithm fluid k3 has a blue cluster that matches the blue PK-group plus 1 extra node, a red cluster that matches the red PK-group plus 5 nodes, and one extra cluster . We see that the top four algorithm match the PK perfectly, while the next one fluid k4 have a partial match. At the bottom, an algorithm has no match.
The alternate modality of representing the matches (shown at the bottom of Fig. 5 ) uses bars to aggregate the nodes and show the proportion of matching, non-matching and other nodes in each cluster . This is more useful when dealing with bigger graphs, because it allows the user to see the results in a more compact way.
Once users have reviewed the list of algorithms they can review results of a single algorithm, or review and compare the results of all the selected algorithms. By default only the top algorithms are selected for inspection, but users can select any set of algorithms according to different criteria: the amount of matching (i.e. they can choose to look at algorithms with no match to challenge their prior knowledge). the algorithm type (the user may prefer an attribute based algorithm, rather than one based on topology); the size of the matched clusters; or the number and size of other clusters found by the algorithm.
By clicking on an algorithm name the results of that algorithm are displayed in the PAOHVis view (see Fig. 6 ). This is particularly useful if one algorithm stands out as being superior.
Names are grouped by the proposed clusters. Clusters that match the prior knowledge are at the top, colored by their respective colors. Black borders around labels highlight nodes that belong to the PK, making them easy to find. All the other (non PK) clusters are initially regrouped in a single group labeled Others. A click on the Others label expands the group into the additional clusters defined by the selected algorithm. By double clicking on the groups labels, the user can rename the clusters. A menu allows users to change the current algorithm being displayed.
From the ranked list of algorithms users can select a set of algorithms and click the large green button to review and compare the selected algorithms in the PAOHVis view (see Fig. 6 and also Fig. 1 for overall context). By default, the PAOHVis view groups the names using the clusters of the 1st algorithm, but on the left of the names now appears complementary information about the results of all the other algorithms. On the far left, the consensus distribution appears as a horizontal stacked bar chart. The size of the segments of each bar correspond to the number of algorithms that associate the specific node to the cluster having the same color of the segment.
On the right of the stacked bar chart, the individual algorithms results are characterized by diamonds, one for each node and algorithm. When the node is classified in one of the clusters matching a PK-group the diamond is colored with the color of that group. The leftmost column shows the prior knowledge (with square icons). To focus users on the PK clusters in this phase nothing is displayed if a node was classified in a cluster which is not related to any PK-group. Icons and names of PK nodes have a black border. For each node, the horizontal pattern of colored diamonds quickly tell users if there is agreement among the algorithms. If all algorithms agree the line of diamonds is of a single color. Conversely, if they disagree diamonds will vary in color. If a node don't match any PK-group then no icon is displayed.
In Fig. 6 PK louvain is selected as the base algorithm for the grouping of names in the list. We see that there is very good consensus on the red cluster, but in the blue cluster only 4 out of 7 algorithms see Joseph as belonging to it. Others see him as belonging to the red cluster. In Others, 4 algorithms consistently disagree by assigning 3 more nodes to the blue cluster. There are clearly many ways to cluster data, and users have to decide what is more meaningful based on their deep knowledge of the people in the network, e.g. by re-reading documents, before validating clusters.
Next, using their knowledge and the consensus of the algorithms, users validate clusters that expand the prior knowledge groups. We call the validated data consolidated knowledge. It is kept in an additional column on the right of the algorithms, left of the names. The tool provides several ways to consolidate knowledge:
Partial Copy. By clicking on one of the icons or dragging the cursor down on a set of icons, users validate the suggestion(s) of an algorithm, adding colored squares in the consolidation column. Once this validation is done, the squares do not change color anymore and represent the user's final decision (unless changed manually again). Fig. 7 shows how a user selects a set of diamonds in the column PK fluid k4. They are connected by a yellow line, which appears while dragging over the icons. When done the status of the nodes in the Consolidated Knowledge column (rightmost) will change to square. Consensus slider. Users can set the consensus slider to a certain value (for example 4) to automatically select all nodes that have been classified in the same cluster by at least 4 algorithms to that cluster. While the slider is being manipulated circles appear in the consolidated column. Then users can validate the suggestions. In summary, diamonds represent suggestions from one algorithm, circles temporary choices, and squares represents the knowledge validated by the user.
Direct tagging. At any time, users can manually force the association of one node to the cluster by right clicking on the node in the consolidated knowledge column and selecting an option from a popup menu. If the user assigns no cluster to the node, no shape is displayed in the consolidated knowledge column, which is needed when no clear decision can be made.
If at the end of this PK consolidation many nodes remain unassigned more work needs to be done, otherwise the work is done.
The last step of PK-clustering aims to find new clusters for the nodes that have not been validated yet, based on the consensus of the selected algorithms. The suggestions are made from the point of view of one clustering algorithm that the user can change along the process. First, the user selects one algorithm in the Paohvis view and the nodes are grouped by the clusters found by the algorithm. The PK-clusters are displayed at the top, followed by Others, which contains everyone else. When users click on Others, the other clusters are displayed ordered by consensus. Since the number of clusters can be high, all new clusters appear in gray to avoid the rainbow effect. A secondary matching process matches the clusters of the current algorithm with those of all the other algorithms, one by one (similar to the matching process described in Sect. 3.4) . Once the matching is done, the consensus of one cluster is computed as the sum of the cardinalities of the intersections between When users hover over one cluster name, a new color is given to that cluster (e.g., green) and new green diamonds appear for each algorithm that match the cluster and for each node that is assigned to the cluster. This is shown in Fig. 8 . Users can therefore see if the selected cluster is consensual, and with which algorithms. The top part of Fig. 8 shows the mouse pointer before hovering on the cluster 2. The bottom part shows that hovering the mouse pointer over the cluster 2, it changes to green and several green diamonds appear along three columns.
The evaluation of the best cluster for a node can be done using multiple encodings. Fig. 9 shows that the suggested clusters appear into the consensus bar chart, in the set of algorithm output and when hovering over the node. A click on the color will validate the node into the cluster having that color. If users are satisfied with the association proposed by the current algorithm, they can validate it by clicking on the cluster name. This will create a new group, so the user can classify the nodes into this new group, as seen before (Sect. 3.9): using the consensus slider, copying an algorithm result, or through manual labeling. This process is repeated for the other clusters until there are no unlabeled nodes or the user is satisfied with the partial clustering. An example of a fully consolidated dataset is shown in Fig. 10 .
We describe two case studies using PK-clustering using realistic scenarios where the clustering has no ground-truth solution but has consequences, scientific or practical. We also report on the user feedback we received when presenting PK-clustering.
We asked our historian colleague her prior knowledge on her network about the trades of Marie Boucher [12] , composed of two main families: Antheaume and Boucher. Family ties were important for merchants, but could not scale above a certain level. Marie Boucher expanded her trade network far beyond that limit. She then had to connect to bankers, investors, and foreign traders, far outside her family and yet connected to it indirectly. As hinted in her article, Dufournaud believes that the network can be split in three clusters: one related to the Boucher family, one to the Antheaume family, and the third to the Boucher & Antheaume company. Using standard visualization tools, she can see different connection patterns over time periods, but she would prefer to validate her hypothesis using more formal measures and computational methods.
To do so, she decided to specify her hypotheses as Prior Knowledge and submit them to our tool. Fig. 1 (top left) shows that she created three groups as PK: Marie Boucher for the Boucher family, Hubert Antheaume for the Antheaume family, and the Boucher & Antheaume corporation alone for the company.
After the ensemble clustering is done, Fig. 1 indicates that 9 algorithms produced a perfect match out of the 13. The first result shown (left) is an attribute based algorithm that uses the time attribute in its computation; it generated a perfect match. This is of high interest because it means that the hypotheses are very consensual among all the 9 algorithms, and furthermore, they are explainable by the time alone, that plays a major role in the community structure of this network.
In the PAOH view, she starts by consolidating the 3 PK-groups using the amount of consensus among the algorithms as well as the graph representation, and her own knowledge of the persons. At the end of this step, the Boucher, Antheaume, and Boucher & Antheaume groups are consolidated, but there are still several persons not labeled on the consolidated knowledge. She decides to review in more detail the clustering results using the ilouvain time algorithm because of its reliance on the time attribute, and also because its results seem good in the matching view. After clicking on the virtual group Others, the four other clusters computed by ilouvain time appear. Our user then investigates the node grouping proposed by the algorithm by hovering the mouse on the names of these new groups. She selects one of the clusters which seems relevant to her and consolidates it.
The final validated partition of the dataset is represented in Fig. 1  (right) . The persons are colored and grouped by the consolidated knowledge. We can see that the final grouping makes sense in the PAOH visualisation on the right. Only one person is not part of any group: Jacques Souchay. It is not unusual in historical sources to have persons mentioned without any information on them.
Our historian colleague can now publish a follow-up article to validate her hypotheses, showing the final groups, explaining that they are related to time, that several algorithms agreed on the initial groups. Furthermore, she can publish the dataset and explain how to reproduce the analysis online, increasing trust with regard to her claims.
In the second cases study we took the role of Alice, a VAST Steering Committee (SC) member, who participates in a SC meeting to validate the Program Committee proposed by the VAST paper chairs for the next conference. One of the many problems that all conference organizers face is to balance the members of the Program Committee according to several criteria. The InfoVis Steering Committee Policies FAQ states that the composition of the Program Committee should consider explicitly how to achieve an appropriate and diverse mix of [21] :
• academic lineages • research topics • job (academia, industry) • geography (in rough proportion to the research activity in major regions) • gender Most of these criteria are well understood, except academic lineage which is not clearly defined. Alice will use the "Visualization Publications Data" (VisPubData [22] ) to find-out if she can objectify this concept of lineage to check the diversity of the proposed Program Committee accordingly.
Using PK-clustering, Alice loads the VisPubData, filtered to only contain articles from the VAST conference, between 2009-2018. Only prolific authors can be members of the program committee, but highly filtering the co-authorship network would change its structure and disconnect it. Thus, PK-clustering uses the unfiltered network with 1383 nodes to run the clustering and perform the matching (Step 1 of the process). But only 113 authors with more than 4 articles will be consolidated (Steps 2 and 3).
Alice then starts the PK-clustering process. She enters her prior knowledge, which is partial and based on two strategies: her knowledge of some areas of VAST, and the name of well-known researchers who have developed their own lineage. She runs the algorithms (Fig. 12) and 5 algorithms produce a perfect match, acknowledging her knowledge of some areas of VAST. She then shows the results to other members of the SC who will help her consolidating the lineage clusters.
Her initial PK clusters are quickly consolidated, using Internet search to validate some less known authors. She then decides to create as many additional clusters and lineage groups as she can. For some authors, she decides to override the consensus of the algorithms. For example, she decides, and her colleagues agree, that Gennady and Natalia Andrienko are in their own lineage group and not in D. Keim's (Fig. 13) . The history of VAST in Europe, very much centered around D. Keim and the VisMaster project [46] , has strongly influenced the network structure and some knowledge is required to untangle it.
Using the PK louvain algorithm as starting point, Alice creates new groups and achieves a consensus among the experts on a plausible set of lineages for VAST. She then checks with the list proposed by the Using partitioning clustering (although with outliers) forces the algorithms or experts to make strong decisions related to lineages. But using a soft clustering (or overlapping partitions), while providing a more nuanced view of lineages, would not be as simple to interpret as coloring spreadsheet lines and sorting them; in the end, the final selection only uses the lineage criteria among many others. Still, we believe PK-clustering can provide a partial but concrete answer to the problem of defining what the scientific lineages are.
Although we could not conduct face to face meetings with historians and sociologists due to the COVID19 lockdown, we showed the system to three practitioners and asked their feedback through videoconferencing systems, sharing our screen and sharing video demonstrations.
They all acknowledged the pitfalls of existing systems providing clustering algorithms as black boxes with strange names and mysterious parameters. They also agreed that the current process for clustering a social network was cumbersome when they wanted to validate the groups and compare the results of different algorithms. None of the popular and usable systems provide easy ways to compare the results of the clusterings that they compute. Usually, the analyst needs to try a few algorithms, remembering the groups that seemed good in some of the algorithms, sometimes printing the clustered networks to keep track of the different options. Still, they all acknowledged that usually, they stop trying more than 2-3 algorithms because of lack of time and support from the tools. Evaluation of clusterings is long and tedious.
They were intrigued by the idea of entering the prior knowledge to the system, but acknowledged that it was easy to understand and natural for them to think in terms of well known entities belonging to groups. They felt uneasy thinking that this prior knowledge could bias the results of the clustering and of the analysis. However, after a short discussion, they also agreed that the traditional process of picking in a more or less informed way two or three algorithms to perform a clustering was also probably priming them and adding other biases. Still, they said that they would need to explain the process clearly in their publications and that some reviewers could also stress the risks.
They all agreed that the process suggested was clear and made sense, but they also felt it was complicated and that they would need time to master it. They said that it was more complicated than pressing a button, but that the extra work was worth it.
One historian who spends a lot of time analyzing her social networks and finding information about all the people was shocked by the idea that you could want to use an algorithm that did not match fully the prior knowledge. For us, it depends if the prior knowledge is given as constraints or preferences, but we did not want to introduce these notions in the user interface so analysts are free to interpret the prior knowledge as one or the other.
They also found some issues with our current system. It was not managing disconnected networks at all when we showed the demo, and they stressed the fact that real networks always have disconnected components. They were also asking about structural transformations, such as filtering by attribute or by node type. We do not support these functions at this stage, but they can be done through other standard network systems.
They were also interested in getting explanations about the algorithms, why some would pick the right groups and others would not. Our system is not meant to provide explanations, it works with black box algorithms. We wished we could help them but that would be another project. Still, when an attribute-based algorithm matches the prior knowledge, we believe that attribute-based explanations are understandable, e.g., groups based on periods of time, or on income.
Overall, we will continue to collaborate with these researchers and improve our tool to help them create higher-level views of their networks using their prior knowledge and offer them several clustering algorithms that they would never have time to test and validate on their networks without our tool.
As presented in Sect. 2.5, the existing paradigms to create meaningful clusters in social networks considers three options: standard clustering, ensemble clustering, and semi-supervised clustering. Our proposed PK-clustering paradigm combines the three options in order to give more power to users in the analysis loop, and allow them to have more say in the final result. Proponents of automatic methods may argue that PK-clustering gives users too much influence on the final result as they can change the cluster assignments at will. On the other hand we know that social scientists are rarely satisfied with current clustering methods, in part because they run on graph data that do not fully mirror the knowledge they have of the social network. Moreover, traditional methods push users to believe the results of the first algorithms and parameter selection they try (often chosen randomly). Thus, PK-clustering provides a more systematic approach, letting the users think at each phase and reflect on what is going on. Instead of passively accepting what the algorithms propose, the user must provide initial hypotheses, limiting the chance of being primed by an algorithm, and explicitly validate the cluster assignment of a node, adopting a critical position to the automated results, yet with a fast interaction to accept many good suggestions quickly. Such decision may be conditioned by looking at the consensus of the clustering methods; the user might decide not to follow the consensus and assign a node to a different cluster. Another consequence of this approach is that the user participates to the process of assigning, as social scientists requires. Even if the algorithms works as a black-box model, the result of different algorithms allow the user to better understand the alternative views. It also allows users to review results that may challenge their prior knowledge.
Many more clustering algorithms exist and could be added. For example, classical multidimensional clustering algorithms that operate on node attributes. Moreover, expanding the exploration of parameter spaces for ensemble clustering algorithms seems needed. Another limitation of the current prototype is that some algorithms do not work well with disconnected components of the graph. Unfortunately, social scientists datasets typically have many disconnected components. This issue can be mitigated by separating components into a set of connected components, run the algorithms on them, and merge the results. Our prototype runs both with node-link and PAOH representations. But, it is better tuned to the PAOH representation because of its highly readable nodes list and table format which makes the review of consensus easier. Better coordination of the table with node link diagrams and other network visualizations is needed. Finally, annotations may be needed to document the decision process and provide an audit trail, with justifications being provided when consensual algorithm suggestions are dismissed.
Performance of PK-clustering strongly depends on the clustering algorithms. We implemented quick algorithms for the computation to be relatively fast. We did a benchmark of the performance on the two datasets of the case studies with a laptop equipped with an Intel Core i7-8550U CPU 1.80GHz 8 and 16 Gigabytes of memory. For the full Marie Boucher social network described in Sect. 4.1, composed of 189 nodes and 58 hyperedges (1000 edges after the unipartite projection) it took 0.6 seconds to run the 13 implemented algorithms and produce the matching. For the graph of Sect. 4.2 about the VisPubData of the VAST conference, made of 1383 nodes and 512 hyperedges (4554 edges after projection) it took 11.37 seconds to run 12 algorithms (the Label Propagation algorithm was removed because it was computationally too expensive in this case). The two datasets are representative of the many medium size datasets historians and social scientists carefully curate (i.e. 50-500 nodes, e.g. [10] ). A cut-off automatically removes algorithms that take too much resources and have still not produced a clustering after 10 seconds of computation, like it was the case for the Label Propagation algorithm on the VAST publication dataset.
In order to improve the computational scalability we can implement progressive techniques to deal with larger sizes [14] . The current user interface design for PK-clustering would allow the ranked list of algorithms to be progressively updated, and users to review a few individual algorithms first while other algorithms are still running. Of course, visual scalability is also an issue with larger datasets, as the list of people also grows. PAOHvis allows groups (like clusters) to be aggregated or expanded, so we expect that users would expand clusters one by one to review and consolidate them, while also being able to review the connections between proposed clusters. Pixel visualizations [25] would facilitate the review of consensus in other nodes and clusters. Classic techniques like zooming or fisheye views [23, 34] would help as long as names remain readable, which is critical to our users.
In this article, we introduced a new paradigm, called PK-clustering, to help social scientists create meaningful clusters in social networks. The paradigm is composed of three phases: 1) the user specifies the prior knowledge on data by associating a subset of nodes to groups; 2) a clustering ensemble method runs and suggests the user an expanded prior knowledge proposing new associations of nodes; 3) the user consolidates extra clusters created by the system after the phase 2.
The interaction follows a mixed-initiative process, because the activities are initiated by the user or the system according to the specific phase. This approach is more complex than a traditional clustering process when the user press a button and get the results, but provides the user more freedom in the choices and more meaningful results. Moreover, with simple actions (such as moving a slider, or dragging over icons), the user is able to interactively perform complex tasks on many nodes at once. The output of PK-clustering is -using a direct quote from a social scientist providing feedback on the prototype: "a clustering that is supported by algorithms and validated, fully or partially, by social scientists according to their prior knowledge". Two case studies illustrated the benefits of pk-clustering.
Clustering and social network analysis remains a challenging task, typically without ground truth to formally evaluate the results. We believe that PK-clustering opens new doors for exploration. The next frontier will be the analysis of dynamic social networks, that are often used in social science, and our approach will need to take into account the evolution of the communities over time. ported in part by a grant from he DataIA Institute (project HistorIA) and the European project IVAN.