Benjamin Renoust
email: benjamin.renoust@labri.fr

Guy Melanc
email: guy.melancon@labri.fr

Marie-Luce Viaud
email: mlviaud@ina.fr

Assessing group cohesion in homophily networks

The analysis and exploration of a social network depends on the type of relations at play. Borgatti had proposed a type taxonomy organizing relations in four possible categories. Homophily (similarity) relationships form an important category where relations occur when entities of the network link whenever they exhibit similar behaviors. Examples are networks of coauthor, where homophily between two persons follows from co-authorship; or network of actors having played under the supervision of the same movie director, for instance. Homophily is often embodied through a bipartite network where entities of a given type A (authors, movie directors) connect through entities of a different type B (papers, actors). A common strategy is then to project this bipartite graph onto a single-type network with entities of a same type A , possibly weighting edges based on how the type A entities interact with the type B entities underlying the edge. The resulting single-type network can then be studied using standard techniques such as community detection using edge density, or the computation of various centrality indices. This paper revisits this type of approach and introduces a homogeneity measure inspired form past work by Burt. Two entities of type B interact when they both induce a same edge between two entities of type A . The homogeneity of a subgroup thus depends on how intensely and how equally interactions occur between entities of type B giving rise to the subgroup. The measure thus differentiates between subgroups of type A exhibiting similar topologies depending on the interaction patterns of the underlying entities of type B. The method is validated using two widely used datasets. A first example looks at authors of the IEEE InfoVis Conference (InfoVis 2007 Contest). A second example looks at homophily relations between movie actors that have played under the direction of a same director (IMDB).

I. INTRODUCTION

The analysis and exploration of a social network depends on the type of relations at play. Borgatti [START_REF] Borgatti | Network analysis in the social sciences[END_REF] had proposed a type taxonomy organizing relations in four possible categories. The first type is homophily (also referred to as similarity) where connected members exhibit similar attributes such as membership in a club or interest group [START_REF] Mcpherson | Birds of a feather: Homophily in social networks[END_REF]. These types of ties do not represent actual social ties themselves, but might lead to a higher probability of a tie to develop between the members sharing similar attributes. Examples are networks of co-author, where homophily between two persons follows from co-authorship; or network of actors having played under the supervision of the same director, for instance.

The second type of ties are social relationships that can be affective relationships, friendship, . . . , usually spanning over a long period of time. The third type captures joint interactions usually observed through discrete events such as calling each other or travelling together. The last type of ties describes flow (tangible or intangible) between entities (migrants moving between places, passengers between airports, etc.). This paper focuses on networks induced from homophily relations,often embodied through a bipartite network where entities of a given type A (authors; movie actors) connect through entities of a different type B (papers; directors). Guillaume and Latapy [START_REF] Guillaume | Bipartite Graphs as Models of Complex Networks[END_REF] advocate bipartite graphs as being universal models for complex networks, hence offering additional motivations to use of these graphs to describe homophily relations.

When dealing with bipartite graphs, a common strategy is to project them onto a single-type network with entities of a same type A , possibly weighting edges based on how the type A entities interact with the type B entities underlying the edge. The resulting single-type network often tends to have high edge density, with an increased propensity to contain cliques (depending on the affiliation data used to build the bipartite graph) [START_REF] Guillaume | Bipartite Graphs as Models of Complex Networks[END_REF]. It may nevertheless be studied using standard techniques such as community detection using edge density, or the computation of various centrality indices.

Referring to the work of Manski [START_REF] Manski | Identification of endogenous social effects: The reflection problem[END_REF], we take the notion of a group as a central paradigm guiding the analysis of homophily networks. Numerous authors have indeed confronted homophily to many social behaviors or phenomenon (influence, contagion, information diffusion, e.g.) [START_REF] Aral | Distinguishing influencebased contagion from homophily-driven diffusion in dynamic networks[END_REF], [START_REF] Bakshy | The role of social networks in information diffusion[END_REF], [START_REF] Shalizi | Homophily and contagion are generically confounded in observational social network studies[END_REF] questionning Manski's group effect as the driving force explaining the observed phenomenon. This paper introduces a homogeneity measure inspired from past work by Burt [START_REF] Burt | Relation content in multiple networks[END_REF] as a mean to inspect and assess group cohesion in a homophily network modeled as a bipartite graph. Two entities of type B interact when they both induce a same edge between two entities of type A . When inspecting a subgroup of entities of type A (in the single-type network), we evaluate its homogeneity by measuring how intensely and how equally interactions occur between entities of type B giving rise to the subgroup. The measure differentiates subgroups of type A exhibiting similar topologies depending on the interaction patterns of the underlying entities of type B. Fig. 1 underlines the "nuance" we wish to bring into the analysis of homophily networks. Consider authors with attributes A, . . . , E in two different manners as shown in the Figure . Authors in the square node graphs (left) are linked by Fig. 1. An example underlining the "nuance" we emphasize by looking at how type B entities interact. In both figures, the square node graph (left) link type A entities (authors, movie directors, e.g.) whenever they are linked to a same entity of type B (keywords, movie actors, e.g.). Entities of type B appear as labels on induced links. The round node graph (right) describes how type B entities interact, that is when they co-occur as labels on an edge. The type B interaction network clearly distinguishes the two situations, whereas the projected single-type A networks show identical topologies.

an edge whenever they share an attribute. Observe that in both situations the pairwise "distance" between authors is the same, because any two authors share exactly two attributes, ending in identical topologies. As a consequence, based on pairwise distance, these two groups are somehow equivalent. Now, consider the circle node graphs (right) describing how attributes interact within the whole group of actors. Clearly, all actors having attribute A gives this attribute a central position. The second situation is much more balanced (although attributes do not mix as intensely as they could). This small example points at situations where the analysis may be mislead when solely inspecting the single-type author network.

Groups can be computed using a variety of methods, from data clustering to community detection.Although advances have been made on that front in the past decades [START_REF] Jain | Data clustering: 50 years beyond k-means[END_REF], [START_REF] Plantié | Survey on social community detection[END_REF] no algorithm or solution imposes itself as being superior in all situations. Understanding and validating the output of these algorithms is a challenging analysis task.

Our paper contributes an approach designed to help users evaluate the reliability of a proposed group structure. Because homophily (similarity) of actors is most often measured based on co-occcurences of attributes, we provide a mean to simultaneously work on the actor network and the attibute interaction network derived from the original homophily bipartite graph. The notion of a group here depends on the context: it may be a cluster computed from any algorithm, or a subset of authors selected by a user, for instance.

Our work exploits two statistics computed on any group of authors indicating the overall cohesion of the group measured through the intensity and homogeneity of interactions of their co-occurring attributes. Exploring the network, selecting a group or subset of co-occurring attributes and getting feedback on internal homogeneity, analysts can validate the model implicitly supported by the grouping procedure.

Our method has been validated based on two widely used datasets. A first example looks at homophily relations between movie directors that have directed the same movie actors (IMDB). A second example looks at co-authors of the IEEE InfoVis Conference where homophily is defined in terms of topics (keywords) associated with co-authored papers.

Related work. Bipartite graphs form an important modeling tool in social network analysis, supporting two-mode concepts [START_REF] Borgatti | Two-mode concepts in social network analysis[END_REF]. They form an important analytical artifact to study homophily relations [START_REF] Easley | Networks in their surrounding contexts[END_REF], and were even claimed as universal models for complex networks [START_REF] Guillaume | Bipartite Graphs as Models of Complex Networks[END_REF]. The literature covers a wide variety of approaches dealing with different properties of bipartie graphs and homophily networks. An optional but common strategy consists in projecting the graph inducing relationships between entities of a same type (see [START_REF] Jackson | Social and Economic Networks[END_REF], [START_REF] Newman | The structure and function of complex networks[END_REF], [START_REF] Zhou | Bipartite network projection and personal recommendation[END_REF], for instance), with the obvious disadvantage of containing lots of cliques.

Because of their wide applicability and because they also offer a straightforward graphical representation of the data, bipartite graphs have been recently used in the design of a website traffic analysis system [START_REF] Didimo | A graph drawing application to web site traffic analysis[END_REF]. Finally, Kaski et al. [START_REF] Kaski | Trustworthiness and metrics in visualizing similarity of gene expression[END_REF] studied homophily in gene networks (similarity in gene expressions) in bio-informatics with emphasis on the trustworthiness of similarities, which places it close in spirit to our work.

II. HOMOPHILY, ATTRIBUTES AND ENTANGLEMENT

INDEX

This section takes a closer look at homophily networks and describes the general framework we use.

As we shall see, group cohesion is easier to achieve with smaller groups. Inspecting a group, in an effort to understand why and how cohesion is embodied in the group certainly requires to be validated based on user knowledge. This only makes sense when conducted on small scale groups, gathering hundreds of nodes at most. Simple questions come to mind when inspecting a group, such as "How can we assess a group of actors really forms a cluster?" "How can we make sure all actors of a cluster really belong to it?" "Should we suspect the group to contain marginal (outlier) actors?", etc.

A central ingredient we used to answer these questions is a set of metrics that capture the intensity and homogeneity of interaction between attributes in a group of actors. These metrics can be viewed as an aid to assess of the internal homogeneity of a group.

A. Interaction network

Our starting point is a set of actors A * with associated attributes A, B,C . . . ∈ B * , as shown in Fig. 2

(a). Most techniques use vector of attributes to compute distances between actors and infer semantically close groups of actors.

The inspection of a group of actors and associated attributes raises several questions. It might be important to know whether attributes equally map to all actors in the group, for instance. Conversely, a misleading transitivity effect may be suspected to take place. Indeed, we may have attributes t,t ′ co-occurring between actors a and a ′ , and attributes t ′ ,t ′′ co-occurring between actors a ′ and a ′′ , may lead one to believe that attributes t,t ′ ,t ′′ simultaneously co-occur between all three actors a, a ′ , a ′′ . We addressed this issue by looking at how well attributes mix within a group. This is accomplished using the entanglement index computed for each attribute t, measuring how homogeneously an attribute co-occurs with all other attributes in a group of actors. Global homogeneity, at the group level, is then computed from the individual attribute entanglement indices. For instance, optimal homogeneity is reached whenever attributes have equal entanglement indices. This is the case

G = (A * ∪ B * , E) (c) Actor-actor graph G A = (A , E A ) (d) Attribute (keywords) interaction network G B = (B, E B ) Fig. 2.
The initial data is formed of actors (authors) having associated attributes A, B,C, . . . (a) (keywords indexing papers). This situation is modeled by a bipartite graph linking actors to attributes (b) (authors having co-published papers on a given topic -keyword, see section III-B). We then consider the projected actor-actor network with attributes as edge labels (c) and derive the resulting attribute interaction network (d).

when all actors have the exact same associated attributes, and that all attributes equally co-occur within actors.

We now provide more details on these indices. The data can be usefully modeled as a bipartite actor-attribute network G = (A * ∪ B * , E) with edges a -t whenever actor a has associated attribute t (see Fig. 2 (b)). Two other networks are derived from the actor-attribute network, namely an actor network G A and an attribute interaction network G B . A actor network is usually built from the actor-attribute network by projecting paths ata ′ (linking actors a, a ′ ∈ A through attribute t ∈ B) onto an edge aa ′ directly linking actors. We also need to store the attribute t as a label for the edge aa ′ . Edges in G A are thus labelled by subsets of attributes (all attributes t,t ′ , . . . collected from triples ata ′ , at ′a ′ , . . . ).

Because we are focusing on actor group cohesion and on attribute co-occurrence, we filtered out some of the edges. Loops were discarded, as well as edges aa ′ inferred from a single attribute t to obtain the actor network G A = (A , E A ). We moreover only kept edges aa ′ inferred from at least two different attributes t,t ′ . The resulting network is shown in Fig. 2 (c).

The attribute interaction network G B = (B, E B ) is built from attributes t that co-occur at least once with another attribute t ′ (through at least two actors). That is, there must exist at least two paths ata ′ and at ′a ′ to infer the edge tt ′ in E B . Note that this network is not obtained by projecting paths tat ′ onto edges tt ′ . For instance, E B does not contain edges connecting descriptors that only concern a single actor. The attribute interaction network is a central artifact in computing group homogeneity.

Edges tt ′ moreover carry weights n t,t ′ indicating how often attributes co-occur between actors in the considered group. We also define n t,t to count the number of edges in E A carrying the attribute t. The matrix N B collecting all these n t,t ′ entries gives rise to another matrix C B filled with ratios c t,t ′ = n t,t ′ /n t ′ ,t ′ . The value c t,t ′ may be viewed as computing the (conditional) probability that an edge be of type t given it is of type t ′ , while c t,t = n t,t /N is the proprtion of edges carrying attribute t among all N edges in G A = (A , E A ).

Consider the example in Fig. 2. Starting from authors (actors) a ∈ A * having published papers on topics t ∈ B * (attributes), we build a bipartite graph where authors a, a ′ link through topic b whenever a and a ′ have co-authored a paper on topic b (Fig. 2 (b)). A single-type graph is obtained by inducing edges between authors labeled with topics (Fig. 2 (c)). The resulting attribute interaction network directly linking topics in shown in Fig. 2 (d). The matrices N B and C B (built over attributes C, E, H and L) then read:

N B =    3 3 2 0 3 3 1 0 1 1 2 1 0 0 1 1    C B =    0.

B. Entanglement index

Inspired by Burt's work on relations ambiguity in multiple networks [START_REF] Burt | Relation content in multiple networks[END_REF], we now wish to compute the entanglement index for each attribute, ,measuring how much an attribute t contributes to the overall cohesion of an actor group.

The entanglement value of an attribute t is reinforced through interactions with other highly entangled attributes. Denote by λ the maximum value among entanglement indices λ t of attributes t ∈ B. In other words, the entanglement index of attribute t is a fraction of λ , namely λ t = γ t • λ . Having a probabilistic interpretation of the matrix entries c t,t ′ in mind, we can thus postulate the following equation which defines the values γ t .

γ t ′ • λ = ∑ t∈T c t,t ′ γ t (1)
The vector γ = (γ t ) t∈T collecting values for all attributes t, thus forms a right eigenvector of the transposed matrix C ′ I , as Eq. ( 1) gives rise to the matrix equation γ • λ = C ′ I • γ. The maximum entanglement index thus equals the maximum eigenvalue λ of matrix C ′ I . The actual entanglement index values λ t are of lesser interest; we are actually interested in the relative γ t values. Furthermore, we shall see how the entanglement vector γ and eigenvalue λ can be translated into a network measures to help understand entanglement in a group of actors.

C. Homogeneity and intensity

Let us see how our indices can help measure global entanglement intensity and homogeneity. The topology of the attribute interaction network G B = (B, E B ) provides useful information about how attributes contribute to the overall cohesion among actors of a group. The focus here is on interactions among attributes and aims to reveal how cohesive the group of actors is considering this set of attributes.

The archetype of an optimally cohesive actor group is when all actors have the exact same associated attributes. In that case, the graph G B = (B, E B ) then corresponds to a clique. As a consequence, all matrix entries n t,t ′ coincide, so all entries in matrix C I equal 1. The maximum eigenvalue of C ′ I then equals λ = |B|, and all γ t coincide. That is, all attributes indeed contribute, and they all contribute equally to the overall actor group cohesion. The Perron-Frobenius theory of nonnegative matrices [7, Chap. 2] further shows that λ = |B| is the maximum possible value for an eigenvalue of a non-negative matrix with entries in [0, 1].

The Perron-Frobenius holds for irreducible matrices, that is when the graph G B is connected. Hence, the connected components in G B = (B, E B ) must be inspected independently. When When the matrix C B is irreducible, the theory of nonnegative matrices tells us that it has a maximal real positive eigenvalue λ ∈ R, and that the corresponding eigenvector γ has non-negative real entries [7, Theorem 2.6]. We hereafter assume that C I is irreducible.

Inspired from the clique archetype of an optimally cohesive actor group, we wish to compute a cohesion index at the actor group level. We already know that the eigenvalue is bounded above by |B|, so the ratio λ |B| ∈ [0, 1] measures how intensely interactions take place within the actor group. This ratio thus provides a measure for cohesion intensity among all actors with respect to attributes in B.

We also know that the clique situation with equal c t,t ′ matrix entries leads to an eigenvector γ with identical entries. This eigenvector thus spans the diagonal space generated by the diagonal vector 1 B = (1, 1, . . . , 1). This motivates the definition of a second measure providing information about how homogeneously cohesion distributes among attributes. We may indeed compute the cosine similarity 1 B ,γ ||1 B ||•||γ|| ∈ [0, 1] to get an idea of how close the actor group is to being optimally cohesive. We will refer to this value as cohesion homogeneity.

A thorough study of the entanglement indices, and the homogeneity and intensity network indices is out of the scope of this paper (see [START_REF] Melanc ¸on | Mesurer la cohésion sémantique dans les corpus de documents[END_REF]).

D. Analysis of homophily networks

Attributes entanglement indices, and the homogeneity and intensity measures may thus be used to inspect homophily networks and assess cohesion in subgroups of actors. These computational devices suggest to use a synchronized dual view of a homophily network splitted into two distinct but complementary networks: the networks of actors G A = (A , E A ) and the interaction network of attributes G B = (B, E B ).

Typically, when using a node-link view of these networks, the selection of a set of actors should automatically trigger the selection of the relevant attributes and compute the corresponding entanglement, homogeneity and intensity values. This is illustrated in Fig. 4), where a set of movie directors has been selected (top panel). Movie actors that played under their direction, here seen as attributes of movie directors, are highlighted (bottom panel). The corresponding homogeneity index, restricted to these four selected directors, are displayed as a background of the selection lasso, while the actual values are reported in a side panel. The size of movie actors nodes corresponds to their entanglement index: a larger node indicates a movie actor weighs more in bringing these movie directors together as a group.

III. CASE STUDIES

The use cases we describe in this section aim at showing how the entanglement indices, and the homogeneity and intensity indices of networks help users explore social networks and reason about the homophily content. The examples are designed to highlight different aspects of the exploration, each time underlining how the indices contribute to better understand the group structure of the homophily network.

Roughly speaking, the knowledge users gain after applying a grouping procedure (clustering, community detection) is that "a group of actors" share "a list of attributes". This is where the entanglement index enters the scene. What does "a list of attributes" really mean? Do all actors share all attributes? Do actors more or less split between attributes? What particular attribute(s) make(s) the split explicit? In other words, users must be able to elucidate to what extent, and possibly how/why, the group of actors form a more or less homogeneous unit.

A. IMDB

This first use case is built from the Internet Movie DataBase, a largely used dataset (www.imdb.com).Starting from the main actors in a chosen subset, we have additionally extracted the corresponding movie directors to form a bipartite network where directors connect to movie actors they have directed. Applying our methodology we compute (i) a movie director network, where two directors connect when the set of actors they have directed share at least two actors, together with (ii) the corresponding actor interaction network. The data may thus be used to find homogenous subgroups of movie directors, those whose artistic signature rely on similar movie casts. Fig. 3. IMDBdirectors appear on top; actors on bottom. Selecting a group of directors highlights the corresponding actors, with node size mapped to their entanglement index. This group of directors shows low homogeneity and intensity. We can clearly see that the distribution of actors is unbalanced, partly because Sharon Stone plays by far a central role in the interactions between directors -the directors all have, at some point, directed her.

This first example gathers 15 actors and 16 directors (see Fig. 3). A low intensity and medium homogeneity, together with a loosely connected actor interaction network topology suggest that actors and directors roughly split into two communities. The director network has medium homogeneity that corresponds to a quite balanced distribution of actors among them. Homogeneity is not optimal: the directors did not individually direct each of these actors although, as a group, they did direct all of these actors. This indicates the need to dig further and try to "nuance" the homogenity of this group. Roughly speaking, low intensity is explained since most directors have directed only a small number of actors relatively to the whole set. As can be seen from Fig. 3 (bottom), the two communities of actors are connected through R. Duvall, and the two communities of directors are connected through S. Lurnet.

The "M. Brando" sub-community (bottom right) shows higher intensity (with homogeneity similar to the overall network). These actors appear as attributes for a subgroup of directors centred around F.F. Coppola, J. Huston, and others. Higher intensity means they played with many other actors under the direction of these movie directors.

The community of actors located in the top left part of the Fig. 4. A group of directors (top) and the corresponding actors they codirected (bottom, highlighted) with node size mapped to their entanglement index. This clique of 4 directors shows higher homogeneity and intensity than the selected group on Fig. 3. panel correspond to a different group of directors (connecting to the previous group through S. Lurnet). It gathers S. Lee, J. Jarmusch, M.Scorsese, W. Allen and others. This community has similar intensity but higher homogeneity when compared to the overall network. This means these actors have equal influence within this group and better capture altogether the artistic signature of these directors as a group.

The upper left subgroup in the director network (see Fig. 4) actually divides into three overlapping cliques. Two cliques reach maximal homogeneity and intensity (the exact same actors have all played under their direction). The third clique (B. Beresford, J. Jarmusch, B. Levinson, and S. Lurnet)selected in the top panel of Fig. 4 -focuses on E. Barklin and S. Stone. It has lower homogeneity and intensity indices: they don't mix that well with the other actors. This use case thus underlines the fact that although a group involve a well identified and distinct set of attributes (movie actors), the homogeneity of the considered group may rely only on a subset of these attributes. Clearly, group cohesion must not solely rely on the topology of the projected single-type network obtained from the original bipartite network.

B. InfoVis 2004 contest

Our second example brings data of a different nature, where topics (keywords) link to authors, showing that the notion of homogeneity can actually apply to a wide variety of entities.

We selected a subset of the InfoVis 2004 Contest dataset giving papers published in InfoVis between 1994 and 2004 [START_REF] Ke | Major information visualization authors, papers and topics in the ACM library[END_REF]. The data we consider are authors indexed by keywords gathered from papers they published. We thus compute a bipartite graph where authors link to keywords. To some extent, with respect to Borgatti's taxonomy of relations [START_REF] Borgatti | Network analysis in the social sciences[END_REF], this network could be considered as an interaction network since co-authorship indeed involves direct contact with collaborators. Fig. 5. The InfoVis 2004 Contest data gives rise to a topic (keywords) interaction network paired with an author social network. The three selected authors (top panel) hold a central position in the social network (top). Their co-publications cover a wide spectrum of topics as shows the clique of terms in the bottom image. Homogeneity, although good, is however not optimal: they did not pairwise co-published on all these topics. We may indeed suspect each of them to have different co-authors in the network.

When we consider authors and keywords, groups may form because authors are socially very close -working in same laboratories, graduated same institutions -or just formed an opportunistic association around trendy topics. We took this aspect in consideration by making sure that authors were connected through a keyword only when they indeed had copublished a paper on that topic -not just because they both had published a paper on that topic.

We show how our approach helps to solve two tasks of the InfoVis 2004 Contest: Where does a particular author/researcher fit within the research areas? What, if any, are the relationships between two or more or all researchers?

The author-keyword bipartite graph gives rise to a keyword interaction network G B and an author social network G A . The full social network contains about 1000 authors and breaks into several connected components. We will focus on the component lead by Woodruff, Olston and Stonebraker (see [13, leftmost part The answer to the first question is straightforward. Selecting a single author, its associated keywords are highlighted while positioned in the context of neighbor topics. The social network displays the co-authors of any selected author.

Inspecting the whole network author by author is lengthy and tiresome and cannot reasonably be performed on larger networks. This brings us to the second task requiring a more elaborated exploration strategy. In our case, we may take benefit of the apparent community structure of the social network. Conversely, we may select a subset of keywords and look at authors who have published on these topics to see how homogeneous a community they form, for instance.

The topology of the author network (Fig. 5 -top) clearly shows three authors as central actors (A. Woodruff, M. Stonebraker and A. Aiken) at the intersection of two different cliques. Their associated keywords form a large clique covering a large part of the keyword network (Fig. 5 -bottom). The entanglement values (node sizes) widely vary among keywords explaining why homogeneity is low, moreover suggesting that each of these three authors have her/his own set of topics.

Selecting the authors that are part of the top clique in the social network (Paxson, Wisnovsky, . . . ), except those central actors leaves us with a subset of authors with optimal homogeneity: they all co-published on the exact same topics. The same is true with the authors of the bottom clique (except the central authors -Olston, Spalding, . . . ).

We may also select two marginal authors sitting on the left side (Baldonaldo & Kuchinsky) and observe that they link to keywords located out of the "Woodruff clique" keyword subsets. Strikingly,none of these sub-communities seem to address the topics portals and data visualization located at the bottom left of the keyword network. Grasping these two keywords, we find that they solely concern Woodruff and Olston. Going back to the author network, selecting Woodruff and Olston we then see the additional topics these two authors have in common. Observe how these topics are marginally positioned with respect to the main clique (Fig. 6 -top). This second use case pointed at fully homogeneous subgroups where authors have co-published papers on the exact same topics. This also suggest that the analysis may be conducted either from the actor (author) network or the attribute (keywords) network. Going back and forth between these two perspectives seems a fruitful strategy to get the most out of the entanglement index and the dual G A -G B representation.

IV. CONCLUSION AND FUTURE WORK

This paper addressed the issue of assessing cohesion in groups from homophily networks mixing actors and attributes into a bipartite graph. Our approach considers splitting the bipartite into two single-type networks used in conjunction when analyzing the homophile relations between actors. To answer this question, we have defined the entanglement index on attributes, together with the homogeneity and intensity indices computed on any subset of attributes.

These attributes can be used to question the homogeneity of a group, where optimal homogeneity requires that actors simultaneously involve the exact same attributes, and maximum intensity occurs when actors cover all available attributes. A group of lower or unbalanced homogeneity indeed requires more careful analysis, and typically leads to the discovery of subgroups or regions locally showing higher homogeneity.

The case studies clearly show the relevance of questioning the attribute homogeneity of actors to potentially confirm the community structure derived from edge density, for instance. They focused on small size examples for sake of readability. This limitation is but apparent, as using the interaction network occurs after actors have been indexed and grouped. Although a query might return hundreds (or thousands) of actors, we may expect the grouping procedure to form much smaller groups before closer examination occurs. We also suspect that larger samples gather larger attribute sets, typically leading to less tangled attribute interactions and less homogeneous groups.

Our second case study suggests our approach applies to other types of networks modeled using a bipartite graph, namely interaction relations. There even is a potential to extend our approach to the study of multivariate networks. Extending the methodology to weightened relationships is also an avenue we plan to explore. These are design choices we suspect may depend on the nature and/or on the size of the dataset.

We also plan to examine strategies to automatically identify attribute and actor subsets with optimal (or maximum) homogeneity and/or intensity, suggesting potential areas of interest in the network under study. These problems, however, will inevitably bring us to combinatorial optimization problems, and we may expect to have no choice but to rely on heuristics to avoid typical algorithmic complexity issues.

  (a) Actors (authors) A * writing papers with keywords B * (b) Bipartite graph

  of Fig. 4]) gathering 16 authors (see Fig. 5 -top).

Fig. 6 .

 6 Fig. 6. Browsing around "obvious" sub-communities of authors, the keywords portals and data visualization never pop up. Directly selecting them in the keyword network brings two co-authors up front: Woodruff and Olston (top).Selecting these authors shows their common topics of interest to be marginally positioned with respect to the main clique (bottom).


Benjamin Renoust
email: benjamin.renoust@labri.fr

Guy Melanc
email: guy.melancon@labri.fr

Marie-Luce Viaud
email: mlviaud@ina.fr

Measuring group cohesion in document collections

Keywords: document collection exploration, document group cohesion, entanglement index, text analytics

Exploring document collections remains a focus of research. This task can be tackled using various techniques, typically ranking documents according to a relevance index or grouping documents based on various clustering algorithms. The task complexity produces results of varying quality that inevitably carry noise. Users must be careful when interpreting document relevance or groupings. We address this problem by computing cohesion measures for a group of documents confirming/infirming whether it can be trusted to form a semantically cohesive unit. The index is inspired from past work in social network analysis (SNA) and illustrates how document exploration can benefit from SNA techniques.

I. INTRODUCTION

This paper adopts a social network analysis perspective to investigate the notion of group cohesion in a document collection. Our contribution exploits structural features of a network describing how index terms associated with documents interact with one another. Different indices are computed to measure how well and how much terms cooccur with one another. This perspective differs from and complements more traditional approaches such as document ranking and topic detection.

Most search engines rank the documents they deliver when queried using keywords. Document ranking techniques, among which Pagerank [START_REF] Brin | The anatomy of a large-scale hypertextual web search engine[END_REF] is the likely most well known and widely used, most often order according to their relevance (with respect to a query) [START_REF] Croft | Search Engines: Information Retrieval in Practice[END_REF]. Ranking, however, does not necessarily consider relationships between keywords and terms indexing documents, leading to an ordered list of documents that concern distinct and often uncorrelated topics.

Another line of research focuses on the identification of topics in a document collection. Many approaches rely on terms to index documents and compute statistics indicating how relevant and important a word or topic is in a document or collection [START_REF] Salton | Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer[END_REF], [START_REF] Dumais | Using latent semantic analysis to improve access to textual information[END_REF], [START_REF] Thomas | Probabilistic latent semantic indexing[END_REF], [START_REF] Beaza-Yates | Modern Information Retrieval[END_REF], [START_REF] Blei | Latent dirichlet allocation[END_REF], [START_REF] Dumais | Latent semantic analysis[END_REF].

The contribution of this work complements ranking techniques and topic identification approaches. Inspired by social network analysis [START_REF] Burt | Relation content in multiple networks[END_REF], we introduce a term interaction network to measure how much terms indexing documents interact with one another within a document group. We refer to term interaction as entanglement, and compute entanglement intensity and homogeneity. These two statistics can then be used to assess the overall cohesion among a group of documents.

The term interaction network can be formed from any set of relevant terms that have been identified within a document group using any method (e.g., statistics [START_REF] Salton | Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer[END_REF], [START_REF] Beaza-Yates | Modern Information Retrieval[END_REF], LSA [START_REF] Dumais | Using latent semantic analysis to improve access to textual information[END_REF], [START_REF] Dumais | Latent semantic analysis[END_REF] or LDA [START_REF] Blei | Latent dirichlet allocation[END_REF]). One particularly interesting use of the interaction network and entanglement measures is to provide feedback on any document grouping or clustering, allowing users to locate more cohesive subgroups that result from an automated grouping procedure or algorithm.

The next section briefly reviews related work before laying out the necessary definitions and notations in Section II to introduce the term interaction network and entanglement measures. A case study is then discussed to show the potential use of these devices (Section III). We demonstrate the interaction network and entanglement measures on data obtained from TV news excerpt manually indexed by documentalists at INA 1 .

A. Related work

Document collection analysis classically considers a cooccurrence matrix, from which several indices can be derived. A well-known index is the tf-idf index [START_REF] Salton | Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer[END_REF], which computes a weight for terms. Documents d, d ′ can then be seen as vectors of weights indexed by terms, corresponding to a line in the co-occurrence matrix. These vectors can be used to evaluate similarities or dissimilarities between documents. The cosine similarity cos(d,

d ′ ) = d,d ′ d d ′
is one well known and vastly used similarity index.

Since the seminal work of Salton [START_REF] Salton | Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer[END_REF], researchers have proposed improvements to the "bag-of-words" model (see [START_REF] Lebanon | The locally weighted bag of words framework for document representation[END_REF], for instance). Latent Semantic Analysis (LSA) [START_REF] Dumais | Using latent semantic analysis to improve access to textual information[END_REF], or Latent Semantic Indexing [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF], exploits the idea that words with similar meaning occur close together in text. These methods evaluate semantic proximity by performing singular value decompositions on a word count matrix. Probabilistic Latent Semantic Indexing (PLSI) [START_REF] Thomas | Probabilistic latent semantic indexing[END_REF] is based on a mixture decomposition derived from a latent class model that can be adjusted using an expectation-maximisation algorithm. Latent Dirichlet Allocation (LDA) [START_REF] Blei | Latent dirichlet allocation[END_REF] is a topic model similar to PLSI, where each document is viewed as a mixture of various topics. LDA assumes that each document is a mixture of a small number of topics, where the presence of words in documents is attributable to one of the document's topics.

These models share the common goal of finding the most relevant terms or topics emerging from a set of documents. Documents can then be described using either a weighted vector or probability distribution indexed by terms, thus allowing the user to compute similarities between documents. These weighted vectors can then feed different algorithms to mine and/or cluster document collections ( [START_REF] Kohonen | Self organization of a massive document collection[END_REF], [START_REF] Zhao | Hierarchical clustering algorithms for document datasets[END_REF] or [START_REF] Steinbach | A comparison of document clustering techniques[END_REF]).

Other authors have developed approaches focusing on lexical cohesion in relation with document ranking [START_REF] Vechtomova | Lexical cohesion and term proximity in document ranking[END_REF] or text structure [START_REF] Morris | Lexical cohesion computed by thesaural relations as an indicator of the structure of text[END_REF]. In [START_REF] Vechtomova | Lexical cohesion and term proximity in document ranking[END_REF], the authors improve document ranking by computing various distances between terms. They exploit the structure of sentences and collocation of query terms in documents. Our work does not look at document content but assumes documents have already been indexed, or terms have already been extracted from documents. In our case, collocation of terms occurs when two terms index a same document. We use a term interaction network to capture multi-partite collocation, instead of considering only pairwise distance between terms.

Our approach also differs from these indexing and ranking techniques in various ways. First, we consider the term interaction network as a central ingredient from which the entanglement index is derived and several conclusions can be drawn. Our approach is similar to [START_REF] Arun | On finding the natural number of topics with latent dirichlet allocation: Some observations advances in knowledge discovery and data mining[END_REF] because it considers a term-document network rather than the topic-term matrix used in LDA. The authors in [START_REF] Arun | On finding the natural number of topics with latent dirichlet allocation: Some observations advances in knowledge discovery and data mining[END_REF] used a document-topic matrix to estimate the actual number of topics present in a document collection. Our concern is different, as we aim to establish whether a document group indeed forms a cohesive group for a given set of index terms. The network shape, however, may be a good indicator of the actual number of different topics that mix within a document collection.

The entanglement index may be computed on any group of documents and any term set indexing these documents. Our technique thus appears as a post-process, providing feedback about any indexing and/or grouping procedure used on a set of documents. The entanglement index is based on interactions that occur between terms (Section II) and fully exploits the interaction network topology. Our work shows how information retrieval can benefit from ideas and techniques borrowed from social network analysis (SNA). To our knowledge, most papers taking advantage of SNA in information retrieval do so by considering a social network of (human) actors, as in [START_REF] Kirchhoff | Using social network analysis to enhance information retrieval systems[END_REF].Our work takes a completely different perspective and directly applies SNA to a network of terms seen as interacting entities.

II. DOCUMENT GROUP COHESION

We now define the entanglement index of terms based on matrix analysis of a term interaction network. Let D be a collection of documents d ∈ D, each indexed by terms t ∈ T , where T denotes a collection of terms. Terms here index documents and correspond to words either taken from a fixed vocabulary (thesaurus) or extracted from documents. An example is a video document (e.g., an excerpt from an evening TV news program) indexed by terms related to the news excerpt topics. We assume here that terms have already been identified and/or computed, so all documents come equipped with a set of index terms. Let M = (m d,t ) d∈D,t∈T denote the usual co-occurrence matrix, where m d,t denotes the number of occurrences of term t in document d. Document d can then be seen as a vector of weights indexed by terms t ∈ T , namely d = (m d,t ) t∈T , corresponding to a line in the co-occurrence matrix M .

A. Term interaction network

One can define a graph-based representation of the document-term relations. The co-occurrence matrix indeed corresponds to a graph G D,T = (V, E), whose vertices are either documents or terms, V = D ∪ T and edges e = {d, t} ∈ E connect documents to terms whenever m d,t > 0. This graph is obviously bipartite, as edges never directly connect any two documents or any two terms. The top image in Fig. 1 illustrates this construction from a set of four different documents with index terms; the next image corresponds to the bipartite graph defined from these documents and index terms.

Many techniques and algorithms are found in the literature for exploiting this bipartite graph to mine and cluster either the document collection [START_REF] Xu | Document clustering based on non-negative matrix factorization[END_REF] [6], term set [START_REF] Slonim | Document clustering using word clusters via the information bottleneck method[END_REF] or both simultaneously [START_REF] Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF]. This bipartite graph is sometimes used to derive a graph

G D = (D, E D ), directly linking documents. The graph is built from G D,T by projecting paths d -t -d ′ onto edges e = {d, d ′ } ∈ E D . Fig. 1 (third image from top) illustrates how G D is obtained from G D,
T (it does not include loops connecting a document to itself). Distinct terms t, t ′ , . . . may link documents d and d ′ in G D,T , from which the edge e = {d, d ′ } is induced. We collect all such terms and turn them into attributes of edge e. Terms t may also be seen as types (labels) for edges in E D . These terms are called the terms associated with the edge e ∈ E D , common to both documents d and d ′ . Other applications turn this term set into a weight on edges e ∈ E and exploit it when mining the document-document graph G D = (D, E D ). However, projecting a bipartite graph onto a one-mode network unfortunately leads to information loss Graphs are built from a document collection indexed by terms (top), from which a bipartite graph linking documents and terms can be considered (next image). We then consider the projected documentdocument graph with terms as edge attributes (third image from top) and derive the resulting term interaction network (bottom).

[15], [START_REF] Zhou | Bipartite network projection and personal recommendation[END_REF]. We overcome the situation by considering an additional network on terms.

We now build a term interaction network. Consider the graph I = (T, F ), whose vertices are terms t ∈ T . An edge f ∈ F links terms t, t ′ ∈ T whenever they both are associated with edge e = {d, d ′ } ∈ E D , i.e., when two distinct documents d, d ′ ∈ D are both indexed by terms t, t ′ . Terms t and t ′ interact with one another through at least two distinct documents d, d ′ .

The graph I = (T, F ) is not built from G D,T by projecting paths t -d -t ′ onto edges e = {t, t ′ }. Fig. 1 (bottom) illustrates how I T is obtained from graph G D . The term interaction network I = (T, F ) is at the centre of our discussion and is actually an object of interest when exploring the document space. The interaction network is defined after documents have been indexed. The interaction network I = (T, F ) relies on the definition of a documentdocument graph G D = (D, E D ) that may be obtained from any data linking documents to terms. Nothing prohibits customizing the graph G D before it is used to define the interaction network I = (T, F ).

The idea of building the term interaction network is borrowed from social network analysis [START_REF] Burt | Relation content in multiple networks[END_REF]. We compute interaction matrices N I = (n t,t ′ ) and C I = (c t,t ′ ) (where subscripts are terms t, t ′ ∈ T ). Let e ∈ E D be an edge in G D and τ (e) ⊂ T denote the set of terms associated with e. Conversely, let τ -1 (t) denote the set of edges e ∈ E D with term t ∈ T as an associated term. We write n t,t = |τ -1 (t)| for the cardinality of that set. We also define n t,t ′ as the number of edges e ∈ E D with {t, t ′ } ⊂ τ (e), i.e., n t,t ′ equals the number of edges e ∈ E D that carry both terms t and t ′ . In other words, n t,t

′ = |τ -1 (t) ∩ τ -1 (t ′ )|, t = t ′ . Define c t,t = nt,t |E D | , and c t,t ′ = n t,t ′ nt,t , t = t ′ . If matrix N I is symmetric, matrix C I is not.
The diagonal entries c t,t in matrix C I can be informally seen as the probability that an edge in E D is associated with term t. Non-diagonal entries c t,t ′ would then correspond to the conditional probabilities that an edge is associated with term t ′ given that it is associated with term t.

Consider the matrices N I (left) and C I (right) shown below. These matrices are computed from the 5-term clique in Fig. 2

B. Entanglement index

We now wish to compute the entanglement index λ t for each term t, measuring how much t is entangled with other terms in the network I = (T, F ), seen as a measure of its contribution to the cohesion of a document group. Let λ denote the maximum entanglement index among all terms and γ t denote the fraction that computes the entanglement for term t. The entanglement index for term t can then be computed as λ t = γ t • λ. Now, the entanglement index of a term is reinforced through interaction with other well entangled terms. Having a probabilistic interpretation of the matrix entries c t,t ′ in mind, we postulate the following equation which defines the values γ t :

γ t • λ = t ′ ∈T c t ′ ,t γ t ′ (1)
The vector γ = (γ t ) t∈T , collecting values for all terms t, thus forms a right eigenvector of the transposed matrix C ′ I , as Eq. ( 1) gives rise to the matrix equation γ • λ = C ′ I • γ. The maximum entanglement index thus equals the maximum eigenvalue of matrix C ′ I . The entanglement indices λ t are of lesser interest; we are actually interested in the relative γ t values. Furthermore, we shall see how the entanglement vector γ and eigenvalue λ can be used to define global measures to help understand how cohesion in a document group takes place.

C. Entanglement intensity and homogeneity

This section introduces entanglement intensity and entanglement homogeneity as global network measures for the term interaction network I = (T, F ). Its topology provides useful information about how terms contribute to the cohesion of a document group.

The archetype of an optimally cohesive document group is when all documents are indexed by the exact same terms. Indeed, assume either that experts have manually indexed documents or that terms have been obtained through some automated procedure(s). The graph I = (T, F ) then corresponds to a clique, i.e., a graph where all nodes connect to all other nodes. In this case, all matrix entries n t,t ′ coincide, so all entries in matrix C I equal 1. The maximum eigenvalue of C ′ I then equals λ = |T |, and all γ t are equal. That is, all terms indeed contribute, and they all contribute equally to the overall document group cohesion. The Perron-Frobenius theory of nonnegative matrices [10, Chap. 2] further shows that λ = |T | is the maximum possible value for an eigenvalue of a non-negative matrix with entries in [0, 1].

An opposite situation occurs when the term interaction network is not connected. Terms split into two subsets that never interact and suggests that the document set may be divided into distinct subgroups. Note that this type of information is easily revealed by inspecting the interaction network, although it is not immediately revealed when looking at a weight vector computed by most indexing techniques. In this case, the connected components in I = (T, F ) must be inspected independently. In the sequel, we assume I = (T, F ) is connected. In that case, non-negative matrix theory tells us that the matrix C I has a maximal positive eigenvalue λ ∈ R with a single associated eigenvector γ with non-negative real entries [START_REF] Ding | Nonnegative Matrices, Positive Operators and Applications[END_REF]Theorem 2.6].

Another typical situation occurs when few terms appear central and the remaining terms are peripheral. On the one hand, documents share a few common terms or rally around a few central topics; on the other hand, documents form subgroups around secondary terms or subtopics. This situation is again easy to identify, as the term interaction network has a fragmented structure (Fig. 4). In this case, the entanglement index reaches higher values for central terms while showing a clear decrease in peripheral terms. Peripheral subgroups may form smaller but denser subnetworks. When examining them locally and recomputing the entanglement index based on the term subset involved, we may expect the entanglement index to adjust to the clique scenario. The case studies presented below develop this situation.

Inspired from the clique archetype of an optimally cohesive document group, we wish to compute a entanglement index at the document group level. Because the eigenvalue is bounded above by |T |, we define the network entanglement intensity (or intensity for short) as the ratio λ |T | ∈ [0, 1] to measure how intensely interactions occur within a document group.

We also know that the clique situation with equal c t,t ′ weights leads to an eigenvector γ with identical entries. This eigenvector thus spans the diagonal space generated by the diagonal vector 1 T = (1, 1, . . . , 1). This motivates the definition of a second measure providing information about how homogeneously interaction occurs among terms. We may indeed compute the cosine similarity 1 T ,γ 1 T γ ∈ [0, 1] to get an idea of how close the document group is to being optimally cohesive. We will refer to this value as the network entanglement homogeneity (or homogeneity for short).

III. USE CASES

This section discusses two use cases illustrating how the various entanglement measures we have defined, together with the term interaction network topology, can be employed to explore a document collection and assess the cohesion of document groups.

Both use cases are built using TV news excerpts that cover many subjects over a 100-day period. Documents were manually indexed at INA. Document groups were identified using classical clustering approaches, outputting groups of varying sizes and homogeneity. The procedures used to form these groups are not the focus here. Indeed, the entanglement index and interaction network are designed to provide feedback about the groups returned by any grouping procedures. A term interaction network may be inferred from any document group one wishes to inspect.

A. Road Safety

We first consider a set of approximately 20 documents, all relating to road safety. Although small, this document sample exhibits interesting features that can also be found in larger samples. Road safety became a topic of interest after the government established a safety policy promoting the use of automated radar, with an inevitable increase in traffic tickets and fines. As expected, this news generated attention, and all TV channels devoted parts of their news programs to this subject. Documents involve index terms, including accident prevention, arrest, danger, driver, driving behavior, money, offense, policeman, prison,road safety, society, and speed, speed camera as the resulting interaction network shows in Fig. 3.

Darker nodes have higher entanglement indices. Node size relates to the number of links n t,t in G D that are associated with term t. As we may guess from the layout, central nodes accident prevention and speed have higher entanglement indices, 0.38 and 0.44, respectively. Other nodes have lower values, such as danger and speed camera with 0.30 and 0.07, respectively. The intensity for the whole network I = (T, F ) is λ/|F | = 0.33, while the homogeneity is 0.81. Fig. 3 clearly shows that terms split into subgroups indicating why optimal cohesion might not be reached. The interaction matrix N I accordingly has a block structure (greyed background), with corresponding null off-diagonal blocks. The central terms are centred in the matrix and appear on top of a blue background. The matrix values show how terms interact within their components, except for central terms, which interact with all other terms. The upper part of the matrix corresponds to the upper part of the network and clearly shows that all terms interact with one another with low frequencies (e.g., terms index a small subset of all documents). The lower part of the matrix exhibits a completely different behaviour, where terms interact more vividly, but not with all other terms in the component.

The network topology suggests closely examining documents relating to terms at the bottom, positioned below the central terms accident prevention and speed. We consider a subgraph I ′ formed with the terms fine, policeman, speed camera, and road safety, etc. Terms in I ′ index all documents but one. For this sub-network I ′ , we have an entanglement intensity of 0.31 and homogeneity of 0.72, which is below those of the total network I. These lower values occur because many terms, e.g., fine, money and detector, actually index few documents (as suggested by their sizes) and the terms involved in I ′ distribute less evenly among documents than all terms in I globally do, as revealed by the zero entries in the lower right part of the matrix.

We may further discard the low interaction terms and focus on the 5-node clique in Fig. 2 associated with 18 of the 20 documents. The clique corresponds to the submatrix with high integer values near the centre of the image (Fig. 3). As expected, the clique reaches higher intensity 0.6 and homogeneity 0.98, confirming that these 18 documents form a cohesive unit around the five selected terms.

This first example clearly shows that entanglement indices, intensity and homogeneity provides insight on the structure of the document group. This document group clearly is homogeneous as all documents after all concern road safety. Different facets of the group may be investigated using techniques such as LDA to identify topics [START_REF] Blei | Latent dirichlet allocation[END_REF], with additional efforts to evaluate the actual number of topics [START_REF] Arun | On finding the natural number of topics with latent dirichlet allocation: Some observations advances in knowledge discovery and data mining[END_REF]. However, the shape of the network topology is a clear indicator of the number of "topics" or "stories" the group contains, as confirmed when observing the increased homogeneity of these two components.

Also, LDA provides no information on the relational structure underlying the term set.

Local inspection of the term interaction network moreover points at marginal terms that may be discarded in order to find core terms around which cohesion builds.

B. Students

The second example concerns a group of 36 documents about students and universities. They gather 3 stories about student protests in Chile, excessive behaviour during freshmen hazing and students' financial conditions, among other diverse related subjects. Documents are indexed using many terms, including Chile, Grande Ecole, higher education, cost of living, education, hazing, protests, salary, student, university, and violence, etc. Fig. 4 shows the resulting interaction network.

The terms with highest entanglement indices sit in the centre of the network: student and higher education, with respective values 0.72 and 0.47. The terms hazing and university immediately follow with entanglement indices of 0.34 and 0.27, respectively. Compared to the the previous example, the network globally has a low intensity of 0.09 and homogeneity 0.44. This is due to a more intricate topology splitting into three denser regions together with satellite terms.

Let us now focus on denser areas in the quest for more cohesive subgroups. The lower part of the network organises around the term protests and links to documents related to student protests in Chile and London. These terms (with 10 related documents) lead to a sub-network with increased intensity 0.23 and homogeneity 0.81. Further focusing on Chile leads to a 5-node clique with slightly higher intensity 0.30 and homogeneity 0.90. After foreign newspapers reported student protests in Chile and London, the French press raised interest about the condition of French students in universities. The terms salary, cost of living and part time thus link within the network (rightmost area of the network in Fig. 4), as they index documents concerned with students' life conditions both in France and abroad. Focusing solely on these three terms, we get a smaller sub-network (and four associated documents) with much higher intensity 0.64 and homogeneity 0.93; again, smaller term and document subsets typically reach higher cohesion. The upper part of the network in Fig. 4 gathers documents related to initiation rites in Grande Ecole. The press got interested in these rites after freshmen students complained about abuse during the hazing rites and brought their cases to court. The four terms at the top (with related documents) induce a sub-network with intensity 0.41 and homogeneity 0.76. Although intensity and homogeneity are higher than the overall network, they remain far from the optimal case and can be considered low. When more closely examining the situation, these low values occur because terms are nested: edges in G D associated with law are all associated with Grande Ecole, which are all associated with customs, ultimately contained in the set of edges associated with hazing.

Figure 4. Interaction network induced from a set of documents related to students and universities. This network has a much more intricate topology and twice as many terms as the previous example (Fig. 3).

This perfectly exemplifies how network topology can guide the document collection exploration. Identifying denser areas in the network is a useful strategy for selecting more cohesive documents from within the originally queried document set.

C. Structure of the (Intensity × Homogeneity) space

Now that we have put forward how the interaction network supports storytelling, and entanglement indices support term ranking, we can conclude this section and return to entanglement profiles considering the previously discussed examples. We have used intensity λ |F | and homogeneity

1 T ,γ
1 T γ as two distinct measures to provide complementary information about the term interaction network. The examples exhibit situations where intensity and homogeneity can be either low or high. Although we may suspect that these quantities do not vary independently, we nevertheless design a 2D plot where homogeneity is plotted along the x-axis and intensity is plotted along the y-axis (Fig. 5). Any term interaction network would then be plotted as a 2D point (x, y) = ( 1 T ,γ 1 T γ , λ |F | ) in the plane, and we may expect the plot to divide into areas that correspond to network profiles.

There is an obvious dependency between intensity and homogeneity: high intensity cannot be achieved without some amount of homogeneity so the space cannot spread

The clique was presented as the archetype of an optimal interaction network located at the top rightmost position (x, y) = (1, 1) in the plot. The top-right area thus collects these relatively dense and evenly interacting networks. The 5-node clique in Fig. 2 falls into this profile category, as does the "Road safety" upper sub-network considered in the first use case (Fig. 3, Section III-A). Higher intensity and homogeneity are much easier to achieve with smaller document and term subsets. The lowest-right area corresponds to relatively high homogeneity and lower intensity: terms almost all interact with one another, but not as much as the document graph G D theoretically allows. N I matrices are non-sparse, and they have large diagonal but rather low off-diagonal entries. Example networks in this category are the "Road safety" lower sub-network (Fig. 3, Section III-A), and the Chile sub-network with intensity 0.30 and homogeneity 0.90 is also part of this category.

The most left area is tricky. This case occurs when terms are nested, as if they were expressing similar concepts at different generality levels. This situation translates into consecutive inclusion of terms among documents links (i.e., links in G D associated with term t include all links associated with term t ′ plus some other links). We pointed out the "Hazing" sub-network in the second use case as a prototype of this phenomenon. The fact that it nevertheless has intensity 0.44 and homogeneity 0.76 stresses the fact that the areas defined by the orthogonal dotted lines must be refined and/or revised.

The lower-left case gathers networks with low intensity and low homogeneity. This is a rather common case, usually gathering more documents and terms with loose interaction. This is a situation where many terms could appear as satellites of more central terms. A term set covering a wider semantic scope inevitably induces a network falling in this category. A typical network would have a low density (few edges) and a random link structure, leading to a sparse N I matrix with ǫ entries. We could argue that the starting interaction network in the Students use case, with a intensity of 0.09 and a homogeneity of 0.44, falls within this category.

Although we have generated some random graphs to illustrate the span of homogeneity and intensity, more experimentation is needed to assess these prospective categories, determine thresholds defining the profile areas and estimate how they are populated.

IV. CONCLUSION

This paper introduced a term interaction network (Section II) as a device from which term entanglement indices can be computed. The cohesion indices can then be translated into global cohesion intensity and homogeneity measures among terms in a group of documents. The cohesion index, cohesion intensity and homogeneity can be computed for any group of documents. They can be used to provide feedback about procedures used to group documents, helping users decide whether documents can be trusted to form a genuine cohesive semantic unit.

The case study (Section III) clearly shows the added value brought by the interaction network topology. The network shape is a clear indicator of possible profiles with an obvious archetype profile of an optimally cohesive group as a clique. The examples show how the topology organises into different areas: some terms are deeply nested into a region, while others act as pivot between regions. Diagram 5 was used to distinguish four generic profiles induced from different cohesion intensity and cohesion homogeneity pairs ( λ |F | , 1 T ,γ 1 T γ ). Our technique is independent of the procedure used to extract or define the terms used to index documents; it thus usefully complements existing indexing techniques. LDA assumes that each document contains a mixture of topics that are revealed in a document collection as a mixture of terms. Determining the exact number of topics combined in a document collection is a difficult problem [START_REF] Arun | On finding the natural number of topics with latent dirichlet allocation: Some observations advances in knowledge discovery and data mining[END_REF]. The case studies suggest that this number may correlate or be derived from the term interaction network shape. Denser sub-networks coupled with relatively high interaction weights c t,t ′ correspond to higher local cohesion. Although a document group may be loosely cohesive, the interaction network may lead to discovering more cohesive term and document subsets.

The examples used have relatively small sizes. The largest document samples we considered gather hundreds of documents and terms, but this limitation is apparent, as using the interaction network occurs after documents have been indexed and grouped. Although a query might return thousands of documents, we may expect the grouping procedure to form much smaller groups before closer examination occurs. We also suspect that larger document samples gather larger term sets, typically leading to sparser term interaction matrices. This is confirmed by the examples discussed in Section III. Conversely, a close examination of the term interaction network helps to identify the core terms from which documents form a cohesive unit.

[

  Indexed documents D with terms T ] [Bipartite graph G = (D ∪ T, E)] [Document-document graph G D = (D, E D )] [Term interaction network I = (T, F )]

Figure 1 .

 1 Figure 1.Graphs are built from a document collection indexed by terms (top), from which a bipartite graph linking documents and terms can be considered (next image). We then consider the projected documentdocument graph with terms as edge attributes (third image from top) and derive the resulting term interaction network (bottom).

  indexing a collection of 18 documents sharing 103 links. Reading the diagonal, n 1,1 = 71 links are associated with the first term (road safety), and n 2,2 = 48 with the second (accident prevention). The number of links associated with both the first and second terms is n 1,2 = n 2,1 = 35. Reading the first entries in C I , the first term is associated with c 1,1 = 69% of all links, and there is a c 1,2 = 73% chance of finding a link associated with the second term among those associated with the first term, while only c 2,1 = 49% of the links are associated with the second term among those associated with the first term. 0.73 0.78 0.69 0.62 0.49 0.47 0.45 0.61 0.33 0.86 0.73 0.76 0.63 1 0.65 0.85 0.54 0.65 0.47 0.39 0.31 0.58 0.31 0.44

Figure 2 .

 2 Figure 2. Optimal cohesion is reached when the entanglement of terms forms into a clique where all terms interact with one another with equal frequency.

Figure 3 .

 3 Figure 3. Interaction network induced from a document set related to road safety and speed cameras. The network splits into two overlapping components organised around two central terms: road safety and speed, leading to an obvious block structure for the interaction matrix.

Figure 5 .

 5 Figure 5. Entanglement profiles can roughly be categorised by combining intensity and homogeneity. Measures on INA's document groups are in red. Randomly generated bipartite graphs are in yellow. Use cases examples are in blue with labels.

INA is the French National Multimedia Institute, see www.ina.fr

We plan to examine strategies to automatically identify term and document subsets with optimal (maximal) cohesion intensity and homogeneity. These problems, however, will inevitably bring us to combinatorial optimisation problems, and we may expect to have no choice but to rely on heuristics to avoid typical algorithmic complexity issues.