Arnaud Sallaberry
email: asallaberry@ucdavis.edu

Faraz Zaidi

Guy Melanc
email: melancon@labri.fr

Model for Generating Artificial Social Networks having Community Structures with Small World and Scale Free Properties

Keywords: Social Networks, Communities, Small World Networks, Scale Free Networks, Network Generation Models

Recent interest in complex systems and specially social networks has catalyzed the development of numerous models to help understand these networks. A number of models have been proposed recently where they are either variants of the small-world model, the preferential attachment model or both. Three fundamental properties attributed to identify these complex networks are high clustering coefficient, small average path length and the vertex connectivity following power-law distribution. Different models have been presented to generate networks having all these properties.

In this paper, we focus on social networks and another important characteristic of these networks, which is the presence of Community Structures. Often misinterpret with the metric called clustering coefficient, we first show that the presence of Community Structures is indeed different from having high clustering coefficient. We then define a new network generation model which exhibits all the fundamental properties of complex networks along with the presence of Community Structures.

Introduction

Most real world systems can be modeled as graphs where different fields of study use extensively the node-link representation to represent information. Wide use of this representation has been witnessed in Social Networks [START_REF] Wasserman | Social Network Analysis: Methods and Applications[END_REF]. A social network can be defined as a set of people, or groups of people interacting with each other [START_REF] Scott | Social Network Analysis: A Handbook[END_REF][START_REF] Wasserman | Social Network Analysis: Methods and Applications[END_REF]. These interactions can be classified into several types like friendship or business relationship. Although many examples have been studied for social networks, two classic examples that have attracted extensive attention in the computer science community and the social network community at large, are the Actor collaboration network from Internet Movie database (IMDB) and the Science collaboration network.

Social network modeling and analysis allows us to understand the different types of relationships that can either facilitate or impede knowledge creation and transfer in a society on the whole, in an organization in particular, and in individuals, providing an insight on the underlying patterns and the social structures present in these networks [START_REF] Scott | Social network analysis: developments, advances, and prospects[END_REF][START_REF] Cross | A bird's-eye view: Using social network analysis to improve knowledge creation and sharing[END_REF].

The study of networks in general, and of social networks in particular, was revived by the pioneering work of Watts and Strogatz [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] on the properties of small world networks. Equally important was the work from Barabasi and Albert on the growth of networks and the property of scale free degree distribution [START_REF] Barabási | Emergence of scaling in random networks[END_REF]. Although random graphs had been studied extensively in the past [START_REF] Newman | The structure and function of complex networks[END_REF], most of the real world networks have the properties of small world and scale free networks.

A small world network as defined by Watts and Strogatz [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], is a network when compared with a random graph of same node-edge density, has higher clustering coefficient and the typical distance between any two nodes scales as the logarithm of the number of nodes. The two structural properties used to define a small world network are, the average path length and the clustering coefficient. The most popular manifestation of the concept of low average path length is the 'six degrees of separation', uncovered by the social psychologist Stanley Milgram, who concluded that there was a path of acquaintances with a typical length of about six between most pairs of people in the United States [START_REF] Milgram | The small world problem[END_REF]. More precisely, the path length refers to the minimum number of edges traversed to go from a node A, to node B. The average path length is the average calculated for all pair of nodes in a network. Another important characteristic of these networks is the average clustering coefficient of nodes [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], sometimes referred as Transitivity [START_REF] Newman | The structure and function of complex networks[END_REF] to avoid confusion from the concept of Community Structure (or Clusters) [START_REF] Scott | Social Network Analysis: A Handbook[END_REF][START_REF] Wasserman | Social Network Analysis: Methods and Applications[END_REF]. The concept is very well known in social networks and can be described as the friend of your friend is likely to be your friend. Mathematically, for a graph G with nodes V and edges E, the clustering coefficient (CC) for a node v is defined as:

CC(v) = r(N (v)) |N (v)|(|N (v)| -1)/2
where u ∈ V and (u, v) ∈ E. The neighborhood of a node v is defined as the set of nodes in the neighborhood of v denoted by N (v). The number of elements in set N (v) is given by |N (v)|. And the notation r(N (v)) represents the number of edges (u, w) such that u, w ∈ N (v) and u = w. To calculate the clustering coefficient of the entire network, we take the average for all nodes in the network.

A scale free network is a network in which a few nodes have a very high number of connections (degree) and lots of nodes are connected to a few nodes. Generally, it was believed that the degree distribution in most networks follow a poisson distribution but in reality, real world networks have a highly skewed degree distribution. These networks have no characteristic scales for the degrees, hence they are called scale free networks [START_REF] Päivinen | A Quest for the Hidden Knowledge[END_REF]. In other words, the degree distribution of scale free networks follow a power-law distribution [START_REF] Barabási | Emergence of scaling in random networks[END_REF].

Apart from the small world and scale free properties, another important characteristic of real world systems and specially social networks is the presence of Community Structures. A more generic formalism for the term community is clusters, where sociologists use the term community [START_REF] Coleman | An Introduction to Mathematical Sociology[END_REF] as compared to the statistical and data mining domain where people use the term clusters [START_REF] Tryon | Cluster analysis[END_REF] to refer to the same concept. Roughly speaking, we like to define a community as a decomposition of a set of entities into 'Natural Groups'. There is no universally accepted definition of clustering [START_REF] Everitt | Cluster Analysis[END_REF], most researchers describe a cluster by considering the internal homogeneity and the external separation as the fundamental criteria for defining a cluster [START_REF] Gordon | Classification: Methods for the Exploratory Analysis of Multivariate Data[END_REF][START_REF] Almeida | Towards a better quality metric for graph cluster evaluation[END_REF][START_REF] Jain | Data clustering: a review[END_REF]. A number of algorithms are present in the literature to study clusters and clustering problem in social networks [START_REF] Newman | Detecting community structure in networks[END_REF][START_REF] Jia | Social network clustering and visualization using hierarchical edge bundles[END_REF][START_REF] Gilbert | Communities and hierarchical structures in dynamic social networks: analysis and visualization[END_REF]. Different network generation models have been proposed to generate artificial networks having both the small world and scale free properties. These models do not generate graphs with community structures by construction as the probability of connection is based solely on the degree of a node and in some cases, the immediate neighborhood of this node.

In this paper, we present a new network generation model which incorporates the properties of small world and scale free networks with the additional advantage of having distinct community structures. We explicitly target social networks and argue that using three fundamental concepts from the social network study, we can generate artificial networks replicating real world social networks. Clustering or Community detection remains an important technique to organize and understand complex systems [START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Jain | Data clustering: a review[END_REF][START_REF] Schaeffer | Graph clustering[END_REF][START_REF] Xu | Survey of clustering algorithms[END_REF] having a wide range of applications in various fields. For empirical evaluation of algorithms, metrics and analytical methods, it is important to be able to reproduce networks having community structures with small world and scale free properties that are close to real world networks. The proposed model, by construction incorporates the presence of community structures as we determine the connectivity of nodes based on a pre-generated clustering. We explain the details in the coming sections.

For the sake of discussion and explanatory purposes, throughout this paper, we are going to discuss four social networks. Two well studied and well structured social networks are the Actor collaboration network where nodes represent actors and two actors are connected to each other if they appear in a movie together. The other network is the Science collaboration network where nodes represent scientists and two scientists are connected to each other if they have written an artefact together. Apart from these two networks, we consider two hypothetical cases from everyday life. Consider a person joining a new organization as an employee and a person joining a sports club as a leisure activity. We will refer them as Actor, Author, Employee and Club networks respectively throughout this paper.

The rest of the paper is organized as follows: The next section contains a review of the existing network generation models for small world and scale free networks. In section 3, we discuss the metric clustering coefficient and compare it with the presence of community structures as being two separate concepts. We then discuss assortativity, transitivity and preferential attachment in social networks in section 4 and argue that with a little modification to these concepts, we can understand how networks having community structures evolve in the real world . We then present a network generation model in section 5. We introduce three networks in section 6 that are used for experimentation and comparative analysis with the artificial network generation models. In section 7, we show that the existing network generation models not only produce graphs without community structures but have other limitations as well. Finally we conclude giving possible future directions of our research in section 8.

Existing Network Generation Models

In this section, we review a number of network generation models proposed in the literature having small world and scale free properties. A comparative summary of these models is presented in Table 1.

Holme and Kim [START_REF] Holme | Growing scale-free networks with tunable clustering[END_REF] modified the well known Barabasi and Albert model [START_REF] Barabási | Emergence of scaling in random networks[END_REF] to obtain graphs that are small world as well as scale free. The idea is pretty simple and effective. A Triad formation step is added after the preferential attachment step where every node introduced in the network, connects not only to node w, but also to a randomly chosen neighbor of w thus resulting in a triad formation. The idea is similar to another model separately proposed by Dorogovtsev et al. [START_REF] Dorogovtsev | Evolution of networks[END_REF] in the same year where every new node added to the network is connected to both ends of a randomly chosen link where one of the nodes of this link is selected through preferential attachment. These models inspired Jian-Guo et al. to introduce another similar model [START_REF] Liu | Multistage random growing small-world networks with powerlaw degree distribution[END_REF]. The network starts with a triangle and at each time step, a new node is added to the network with two edges. The first edge would choose a node to connect preferentially, and the second edge will choose a node connected to the first node, again based on preferential attachment. This is different from the model of Holme and Kim where the second node is randomly chosen. Wang et al. [START_REF] Wang | Random pseudofractal scale-free networks with small-world effect[END_REF] proposed a similar model to that of Dorogovtsev et al. where at each time step, a new node with two edges is added to the network and the two edges are connected to the two ends of a randomly chosen existing edge.

Fu and Liao [START_REF] Fu | An evolving scale-free network with large clustering coefficient[END_REF] proposed another extension to the Barabasi and Albert model which they called the Relatively Preferential Attachment method. At each time step, the newly introduced node in the network connects to a node w with preferential attachment, the nodes in the immediate neighborhood of w have higher probability of connecting to this new node as compared to other nodes. The only difference in this model with the already proposed models is that the new node can have m edges instead of two edges where the value of m is chosen as an initial parameter which remains constant throughout the execution of algorithm.

Klemm and Eguiluz [START_REF] Klemm | Growing scale-free networks with small world behavior[END_REF] also proposed a model, where each node of the network is assigned a state variable. A newly generated node is in the active state and keeps attaching links until eventually disactivated. At each time step, a new node is added to the network by attaching a link to each of the z active nodes. The new node is set as active. One of the existing nodes is disactivated where the probability of a node being disactivated is inversely proportional to its degree i.e lower the degree, higher the probability of disactivation. To reduce the average path length of the entire graph, at every step, for each link of the newly added node, it is decided randomly whether the link connects to the active node or it connects to a random node.

Catanzaro et al. [START_REF] Catanzaro | Assortative model for social networks[END_REF] present a model taking into consideration the assortativity of social networks. Assortativity is the tendency of nodes to preferentially connect to nodes that are similar to them. This similarity in general, can consider any attribute but in case of social networks, it is referred to as the connectivity or the node degree of the nodes. At every step, a new node is added to the network based on preferential attachment and a new edge is added between two existing nodes. These existing nodes are chosen on the basis of their degree thus forcing links between similar degree nodes. The model is innovative as it allows addition of new links between old nodes.

Another interesting model was proposed by Guillaume and Latapy [START_REF] Guillaume | Bipartite graphs as models of complex networks[END_REF]. They identify bipartite graph structure as a fundamental model of complex networks by giving real world examples. The two disjoint sets of a bipartite graph are called bottom and top. At each step, a new top node is added and its degree d is sampled from a prescribed distribution. For each of the d edges of the new vertex, either a new bottom vertex is added or one is picked among the pre-existing ones using preferential attachment. A more generalized model based on similar principles was proposed by Bu et al. where instead of using the bipartite structure, a network can contain t disjoint sets (instead of just two sets, as is the case of the bipartite graph) where the example of sexual web [START_REF] Lilijeros | The web of human sexual contacts[END_REF] was considered as a model. A sexual web is a network where nodes represent men and women having relationships to opposite sex, and similar nodes do not interact with each other. At each time step, a new node and m new edges are added to the network with the sum of the probabilities equal to 1. The preferential attachment rule is followed as the new node links with the existing nodes with a probability proportional to the degree of the nodes.

Wang and Rong [START_REF] Wang | Evolving small-world networks based on the modified ba model[END_REF] proposed a slightly different model, which is still a modified form of the preferential attachment model. Instead of adding one node at a time, the model proposes to add n nodes at each time step which are connected in a ring formation. Any two nodes in the n new nodes are connected to the existing network where these connections are determined through preferential attachment.

Generation models for clustered graphs exist in the literature such as the work of Condon and Karp [START_REF] Condon | Algorithms for graph partitioning on the planted partition model[END_REF] and Virtanen [START_REF] Virtanen | Properties of nonuniform random graph models[END_REF] where the idea is to generate graphs that are already clustered as opposed to random graph models of Rapoport [START_REF] Rapoport | Contribution to the theory of random and biased nets[END_REF] and Erdos and Renyi [START_REF] Erdos | On the evolution of random graphs[END_REF]. A recent work by [START_REF] Zaidi | Small world networks and clustered small world networks with random connectivity[END_REF] addresses the issue of generating clustered small world networks which are not scale free and the clusters are randomly connected to each other. As these generation models do not produce graphs with small world and scale free properties which are fundamental to most real world networks. Thus the study and comparison of these other models remain out of the scope of the paper.

Comparing the different network generation models (See Table 1), first five models are quite similar to each other, as they try to force the triad formation step, one way or the other. Another common aspect in the first five models is that in every step, only one node and two edges are added to the network. The only other taxonomical grouping possible is the last two models where the bipartite and n-partite structures are used as the fundamental property of real world networks. The model of Wang and Rong is slightly different as it allows the addition of m new nodes at every time step. The ideas of Klemm and Eguiluz, Catanzaro et al. are quite original and provides another way to look at the evolution and structure of complex networks.

Clustering Coefficient and Community Structures

Largely due to the terminology used to define the metric clustering coefficient, often it is misunderstood that a network having high clustering coefficient suggests the presence of clusters or community structures in a network. Clustering coefficient, by definition, determines the local cohesiveness of a set of nodes, i.e. it focuses on the immediate neighborhood of nodes but fails to capture the presence of communities on the whole as argued by different researchers [START_REF] Brandes | Network Analysis : Methodological Foundations[END_REF][START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Zaidi | Identifying the Presence of Communities in Complex Networks Through Topological Decomposition and Component Densities[END_REF]. High clustering coefficient only indicates the presence of a large number of triads, i.e. three nodes connected to each other through three edges. This property is often present in social networks where it refers to the phenomena that if you know two people, there is a high probability that the two people know each other as well. This metric also measures the presence of cliques as they are a composition of triads but it cannot be used to identify the presence of densely or sparsely connected nodes in a network as we explain below using examples. Fig. 1 is an example graph that depicts the differences between clustering coefficient and community structure. Fig. 1(a) clearly has four communities with high connectivity between nodes of the same community and (b) has several nodes sharing common neighbors but visually, no distinct groups. Both these graphs have the same number of nodes and edges where the clustering coefficient for graph (a) is 0.70 and (b) is 0.69. No information about the presence of four communities can be deduced from the clustering coefficient of graph (a).

Another interesting example is shown in Figure 2 considering (a) and (b) as clusters obtained from some graph. Both contain the same number of nodes and edges. Thus the density (ratio of number of edges and number of nodes) of the two clusters is exactly the same. Cluster (a) is constructed using Quads instead of triads where a quad is a set of four nodes connected through four edges in a ring. We then compare this cluster with a cluster constructed with triads. Both these clusters are shown in in Figure 2 tering coefficient of cluster (a) is 0.0 representing the absence of triads and as compared to cluster (b) with a value of 0.69. This is no surprise as clustering coefficient, by definition, measures the quantity of triads in a graph. Another important metric used to classify a network as small world is the average path length. Calculating the average path lengths of the two clusters, (a) has a lower value with 2.3 as compared to (b) with a value of 2.6 showing that cluster (a) is more compact and on average, the nodes lie closer to each other as compared to cluster (b) and thus is a better cluster even though its clustering coefficient is 0.

From the above two examples, we can conclude that a graph having high clustering coefficient does not necessarily suggests the presence of distinct group of nodes tightly connected to each other and loosely connected within themselves. Moreover a cluster can be a good cluster even if its nodes have a low average clustering coefficient.

Assortativity and Triads in Social Networks

In this section, we present three fundamental concepts associated with the theory of social networks. First, we briefly introduce these concepts and then we argue that combining these concepts, we can produce a network generation model with small world and scale free properties having distinct clusters.

The Theory of Assortativity or Assortative Mixing refers to the principle that in a network, similar nodes tend to attach to each nodes. This similarity can be based on one or more than one attributes. An important application of this theory is the assortative mixing in social networks where nodes attach to other nodes having similar degree. This differs from biological and technological networks that exhibit disassortative mixing [START_REF] Newman | Assortative mixing in networks[END_REF][START_REF] Newman | Mixing patterns in networks[END_REF]. Disassortative mixing refers to the phenomena where dissimilar nodes tend to connect to each other. A good example is the Sexual Web [START_REF] Lilijeros | The web of human sexual contacts[END_REF] where nodes representing men or women connect to nodes with opposite sex.

We move on to another important concept in social networks, the formation of Triads introduced by Simmel [START_REF] Simmel | The sociology of Georg Simmel / translated and edited with an introduction[END_REF] as a fundamental structure for social networks. In fact, the smallest and most elementary social unit, a dyad is a social group composed of two members while a triad is a social group composed of three members. Groups of larger size are also possible but since a variety of relationships can form in them, they are less stable [START_REF] Simmel | The sociology of Georg Simmel / translated and edited with an introduction[END_REF] and often less studied in sociology.

Finally, the principle of Preferential Attachment introduced by Barabasi and Albert [START_REF] Barabási | Emergence of scaling in random networks[END_REF] as an ingredient for growing network model with power law degree distribution. Some times, referred to as the 'Rich gets richer', the idea is that in real world networks, nodes having high degree have a high probability of attracting more connections as compared to nodes with low connectivity. In terms of social networks, this means that a famous person is likely to become more famous as compared to a person who is not well known in the social community. The idea is the direct implication of the human trait of extraversion-introversion [START_REF] Jung | Psychologischen Typen[END_REF]. Extroverts, who are open to meeting new people and developing new relationships are expected to have high degree of connectivity in a social network as compared to Introverts, who tend to be more reserved, less outgoing, and less sociable.

Extending the principle of assortativity, we argue that in theory, since nodes tend to connect to similar nodes, it is not always the case that the similarity is based on node degree.

We consider examples from two of the most studied social networks in computer science, the actor network and the authorship network [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF][START_REF] Barabási | Emergence of scaling in random networks[END_REF][START_REF] Freeman | The Development of Social Network Analysis: A Study in the Sociology of Science[END_REF][START_REF] Wasserman | Social Network Analysis: Methods and Applications[END_REF]. If the degree was the only criteria for associating to other nodes, in case of an actor network, actors beginning their career will never get to play a role in a movie with well known actors. This is contrary to the reality as often, new actors are given supporting roles along with well known actors and thus the similarity is based on some other criteria. Similarly, for the authorship network, if degree was the only criteria, an experienced professor will never take a doctorate student who has only a few publications under his supervision which is generally not the case.

Our deduction from the above two examples is that the nodes tend to associate to other nodes having similarity based on the context and not the node degree. For example an actor starting his career as a comedian has a higher probability to act in a comedy film and thus act with a well known actor in the domain of comedy films. In this case, the similarity is based on the domain of the two actors. Similarly for the case of authorship network, a student having done a masters in a particular domain such as computer networks, has a high probability of collaborating with a well know researcher of the same domain, probably as a doctorate student. Again, the connectivity preference is due to the domain or subject of research. Generalizing from this concept, for other social networks in real world, consider the example of a person joining a new organization as employee. He has a high probability of interaction with his fellow employees, people working on the same project or sharing the same office. Another example is that of a person joining a sports club. He has a high probability of interaction with people sharing the same sports activity like Tennis.

Returning to the formation of triads in social networks, our perspective is that usually when a person enters a new social network, its not just the triads that are formed but Groups of larger size, or cliques are formed. From the actor example, it is quite clear that a new actor will probably act with a well known actor, but the social interaction will take place within the entire cast of the movie. This interaction will be represented with a clique where all the nodes representing the actors will be connected to each other. The authorship network is no different as people co-authoring an artefact will form a clique. Similarly in real world, usually groups of larger size are formed. Continuing with the two examples, a new employee will interact with not just only one or two more people, but with different colleagues in the same organization which work together on the same project or with whom he shares an office, and for a person joining a sports club, he will interact with people sharing similar activities instead of just one or two others.

Addressing the principle of Preferential Attachment, we argue that for every node in a Group (or Clique), few nodes have a higher number of connectivity with other nodes. For example, in a group representing the actors playing in the same movie, the famous actors will have many connections with others as they would have played a role in many movies. Similarly, in the authorship network, an experienced researcher would have published an artifact with many other researchers and thus would have a high number of connections.

Combining the above principles together, we claim that People in social networks are most likely to interact with similar people where similarity is based on the context and the domain. People form Groups of larger size and not just triads, there are few people that have a very high degree of connectivity as compared to others. Based on these ideas, we present a new network generation model in the next section.

Proposed Network Generation Model with Communities

The basic idea of the proposed algorithm comprises of three major steps. Instead of adding one node at a time, we add cliques of various sizes. This results in the network having high clustering coefficient. Next, we associate a possible connectivity attribute drawn from a degree distribution following power law. This ensures that the degree distribution of the final network follows a scale free property. Finally, to obtain community structures where some nodes are densely connected within and sparsely connected to other nodes, we generate a cluster tree which represents the possible communities for this network. Based on the connectivity attribute, and the distances in the cluster tree, nodes within the cliques are merged together creating highly dense groups of nodes well connected within and sparsely connected to nodes distant in the cluster tree.

The proposed algorithm comprises of several steps where each of these steps is explained in detail below. The following mathematical notations are used throughout the explanation: G(V, E) represents an undirected multigraph where V is a set of n nodes and E is a set of e edges. The graph G is initially empty and the nodes and edges are added as the algorithm progresses. C represents a set of cliques such that

C = {C 1 , C 2 , • • • , C k } are different cliques
each comprising of one or several nodes. T represent a tree where its leaves are equal to k (the number cliques in set C ). In contrast to existing network generation models, instead of adding one node or triads at a time, to generate the network, we start by adding cliques of variable sizes to G. The algorithm takes as parameter, the number of cliques to be generated (k), the minimum (minSize) and the maximum size (maxSize) of the cliques to be generated. A random number is generated between these two limits and for each random number, a clique C i is added to the graph G such that nodes and edges of the clique become member of V and E respectively. As a result, G contain nodes that are well connected to each other within a clique, and nodes from different cliques are not connected to each other. G becomes a graph comprising of

Step 1: Clique Generation

C = {C 1 , C 2 , • • , C k } as shown in figure 3.

Step 2: Scale Free Degree Distribution

In order to have the degree distribution of G follow a scale free behavior, we generate a separate scale free graph G ′ with the same number of nodes as in G, using [START_REF] Barabási | Emergence of scaling in random networks[END_REF]. Next, we assign the degree of a node in G ′ as an attribute of a node in G chosen randomly and call this attribute sf Deg. Nodes once processed are not reconsidered for another assignment. The Psuedo Code for the process is given in algorithm 1. Every time the procedure getN ode is called, it picks a unique and randomly selected node from a given graph until all the nodes have been selected. The assignment of values from nodes of G ′ to G is random but since there are few nodes with very high node degree, there is a high probability that they are divided among the cliques sparsely. Thus we end up with one or two nodes in a clique with a high node degree as shown in figure 4. This step assures that the final graph G has a scale free degree distribution.

Step 3: Merger of Nodes

The next step is the merger of nodes from different cliques to form a single connected network. The merger is a simple step where two nodes to be merged are replaced by a single node, and all the edges connected to the two merged nodes are connected to this new node. Figure 5 shows how two nodes from two different cliques are merged forming a connected network of two cliques. The exact details of how to select two nodes and how many nodes are selected for merger are explained in the following sub-steps.

Algorithm 1: Scale Free Degree Association to nodes of G

Input: Graph G and G ′ Output: G(V, E) begin node n, n ′ ; attribute sfDeg(G); n ← getN ode(G); n ′ ← getN ode(G ′ ); foreach node ∈ G do if deg G (n) < deg G ′ (n ′ ) then sf Deg(n) ← deg G ′ (n ′ ); else sf Deg(n) ← deg G (n);
end Fig. 4 Step 2: A scale free degree distribution is imposed as attribute of nodes in graph G containing cliques.

Step 3.1: Calculate Number of Merges

As a first step, we need to calculate for each node, how many merges will it perform with other nodes. This calculation is based on the attribute sf Deg. The idea is pretty simple, the more a node is merged with others, the more higher its degree will be in the final network. This phenomena is shown in figure 5 where the two merged nodes result in a single high degree node. The number of merges for each node n ∈ G is calculated using sf Deg as follows:

N ode M erges(n) = sf Deg(n) Avg N ode Degree(G) (1)
We use the following equation to calculate the total number of merges for a clique C j ∈ C:

Clique M erges(C j ) = ∀n∈Cj N ode M erges(n) (2)

Step 3.2: Generation of Cluster Tree

As the main objective is to have distinct clusters in the graph, we generate a random tree T with the number of leaves exactly equal to the number of cliques generated in step 1. Each clique C j ∈ C is assigned to a leaf of the cluster tree T as shown in figure 6. The tree can Fig. 6 Step 3: A cluster tree T is generated and cliques are assigned to its leaves to decide how the nodes (in the cliques) will be connected to each other forming clusters.

have varying depths to generate a hierarchical clustering where one such tree is shown in figure 6.

Step 3.3: Merging Nodes of Cliques to Form Clusters

For every clique C j ∈ C in the cluster tree T , we calculate a vector of probabilities P ji where j represents the clique for which this vector is being calculated and i represents the clique with which the probability of connecting j is calculated. This probability is inversely proportional to the distance between two cliques in T and is spread equally over the branches of T as shown in figure 7. The vector P ji thus obtained represents the probability of two cliques having their nodes merged.

For example, to calculate the probability of connection of the encircled node with other nodes in T , the probability is uniformly divided among the three branches (1/3 in this example) for each branch leading outwards from the encircled node. One of these branches leads to the root of the tree which is again uniformly divided among two of its children as shown in figure 7.

Using probability vector P ji and Clique Merges(C j ) from equation 2, we calculate the exact number of pairwise merges using the equation below:

P airwise M erges(C j , C i ) = Clique M erges(C j ) * P ji ∀j, i ∈ C (3)
Pairwise Merges(C j , C i ) is a directed vector representing the exact number (as integer) of merges between each pair of clique (C j , C i ). Based on these integer values, nodes from different cliques are merged to form connections between cliques which results in a fully connected network with the desired properties. This calculation is depicted in figure 8 where we show the probability vector for C 0 , P 0i and its corresponding Pairwise Merges(C 0 , C b ) high probability of 0.33 each of merging with C 0 . The merger of nodes with close neighbors result in lots of connections being built between the cliques nearer to each other in the tree and thus represents clusters in the final graph. Algorithm 2 contains the pseudo code for the merger of two nodes.

∀b ∈ C.
Algorithm 2 uses a procedure Merge where two functions are used to select nodes from a clique named Select One N ode rand (Ca) and Select One N ode prob (C b ). The implementation of these functions is very simple. The function Select One N ode rand (Ca) chooses a node n randomly such that n ∈ Ca and Ca ∈ C and N ode M erges(n) > 0. Note that the equality in equation 2 is always preserved during the execution of algorithm. The function Select One N ode prob (C b ) uses the sf Deg(n) to calculate a probability which is proportional to the node degree of the node. Thus nodes having high connectivity have a high probability of being selected as compared to nodes with low connectivity.

Further Explanations and Possible Variants to the Proposed Model

In this section, we provide explanations of the different steps of the proposed model and relate these explantations to real world social networks. This helps to understand how characteristics of real world networks are incorporated in the proposed model. We also discuss The first possible variation to the model is in the very first step explained in section 5.1 where we add cliques of different sizes. The size of the cliques can be forced to be exactly 3, in which case we would have forced the presence of only triads just as the other network generation models presented in section 2. Due to the presence of cliques (or triads), the average clustering coefficient of the entire graph increases as compared to a random graph which is a fundamental property to identify a small world network.

The assignment of values in the section 5.2 is easy to comprehend once considered in the context of real world. This assignment represents that in certain social groups, there are people who have relatively high connectivity with others. Continuing with our two example social networks, a famous actor who plays in many films will have a high number of connections with other actors and similarly, a senior professor will have a high number of connections with other researchers. This value is used in Step 3 of the model to determine how different cliques of Step 2 are merged together to form a single connected network.

A variation to this step can be the assignment of a normal degree distribution or a uniform degree distribution. The choice results in what the final degree distribution would be for the generated network. This flexibility is quite useful as the model can be used to generate networks with any kind of degree distribution.

In section 5.3.2, we discuss how a cluster tree is used to generated a network with hierarchical clusters. A possible variation is the gerenation of a flat or partitional clustering. We can generate only a tree with depth 2 where we have all the cliques at the bottom level, merging with other cliques at level 1 to form clusters and the root represents the regrouping of all the clusters as shown in figure 9 which contains 4 clusters and 12 cliques.

Real World Social Networks

For the analytical study of the network generation models, we compare the networks generated by existing models with real world networks using a number of metrics (see Section 7). We consider three social networks, two of which are author networks and the third one is an actor network.

The author network is a network where nodes represent scientists and an edge between them represents a collaboration in terms of co-authoring a scientific artefact like a book or an article. The two data sets are the Network Science data set and the Geometry data set. The Network Science data was compiled by Newman [START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF] from the bibliographies of two review articles on networks, M. E. J. Newman, SIAM Review 45, 167-256 (2003) The Actor network is a network where nodes represent actors and two actors are connected to each other if they have acted in a movie together. The data set we use here is a subset taken from the IMDB3 database of movies made until the year 1999 and used by other researchers such as [START_REF] Auber | Multiscale visualization of small world networks[END_REF][START_REF] Archambault | Grouse: Feature-based, steerable graph hierarchy exploration[END_REF]. This network contains 7640 nodes and 277029 edges.

The choice of selecting these models is based on two criteria. First we wanted to use graphs that are publicly available and have been studied by other researchers. Moreover, networks having varying density and size so as to see the behavior of the different models in terms of scalability and flexibility could be evaluated.

Results and Discussion

We calculate a number of statistics using various Network generation models and compare them with the real world networks of equal sizes. The results are shown in Table 2 and Table 4. In some cases, the models are not parameterized and thus the node-edge density could not be controlled. We tried to generate models of similar size in terms of number of nodes, and where possible, similar number of edges. An important observation about these networks is that since all of them use the preferential attachment to produce the scale free property, the degree distribution for all the models follow a power law. To the best of our knowledge, there is no metric which tries to identify the presence of communities in a network by analyzing the graph on the whole in a global perspective, thus the presence of community structure in the proposed model is only justified by construction. Using the cluster tree, the way the nodes connect to each other can be controlled and thus any network that is produced has densely connected nodes which are sparsely connected to other nodes.

Lets have a look at some individual results for the various models in comparison to the real world networks. For example, graphs generated using the model of Guillaume and Latapy, the node-edge density in every case is very high and could not be controlled. The model of Fu and Liao, in all the three examples, have a very low clustering coefficient as compared to the respective real world network and thus could not really be classified as generating similar networks to the real world networks used as examples in our study. Looking at the clustering coefficient of the model by Wang and Rong in Table 3, it is quite clear that the model fails to generate a high clustering coefficient for a similar size network. An observation about the model of Holme and Kim, In Table 4, where the node-edge density of the network is comparatively high to other two networks but the the network has a large size, the clustering coefficient drops considerably. The model of Klemm and Eguiluz scales well in terms of clustering coefficient, but in case of low node-edge density (see Table 2), the average path length is considerably high to be a small world network. Also, from Table 4, the average path length in case of a number of models is 1.99, which is a direct implication of a node having a very high degree. As a result, most of the nodes are connected to this high degree node and thus have almost a distance which reduces the average path length of the entire network.

From the above examples, one obvious problem that can be inferred is that these models have problems with scalability, as the node edge density is varied for a network, the models are not able to reproduce comparative values with real world networks for various statistics. On the other hand, the proposed model in this paper has the ability to control the size of cliques as the starting point, which helps us to gauge the density and at the same time, and generate small world and scale free networks. The values are quite close to the ones expected and thus the proposed model is quite flexible.

Conclusion and Future Research Directions

In this paper, we have studied the concepts of assortativity, triads and preferential attachment as the building blocks for the structure of social networks. We use these concepts to present a model to generate artificial social networks. We evaluated a number of network generation models that successfully generated small world and scale free networks but fail to capture another important characteristic of real world network i.e. the presence of Community Structures. We compared the existing and the proposed network model with real world social networks using a number of statistics. Results show that the proposed model indeed generates networks that have community structures and are topologically similar to real world networks as compared to the other existing models that generate small world and scale free networks. Moreover, we identified another problem for the existing models, the scalability in terms of node-edge density, where it is difficult to maintain the high clustering coefficient and low average path length as networks of varying sizes are produced.

In this paper, we have focused on social networks and effectively presented a model to generate networks having small world and scale free behavior with communities. We intend to extend our study to other types of networks such as biological and technological networks to propose network generation models for these types of networks as well incorporating several real world networks.

  (a) and (b). The clus-

Fig. 1

 1 Fig. 1 Two graphs with the same number of nodes and edges (a) Four Groups of Nodes well connected within and sparsely connected with other groups.(b) Nodes sharing neighbors in the form of triads. Clustering Coefficient for graph (a) is 0.70 and (b) is 0.69. High values for clustering coefficient does not necessarily imply the presence of community structures in a network as shown in graph (b).

Fig. 2

 2 Fig. 2 Consider two clusters of some graph with same number of nodes and edges and thus having the same density in terms of number of nodes and number of edges. (a) Nodes well connected to each other forming quads, (b) Nodes sharing neighbors to form triads. Clustering Coefficient for cluster (a) is 0.0 and (b) is 0.69 representing the absence of triads in cluster (a). The Average path length of (a) is 2.3 and of (b) is 2.6 showing that cluster (a) is more compact and on average, the nodes are much closer to each other than cluster (b). This example shows that a cluster can exist even with a low value of clustering coefficient as shown in (a).

Fig. 3

 3 Fig. 3 Step 1: A graph G containing only cliques of different sizes. Parameters used for this example are minSize=1, maxSize=5 and k=11.

Fig. 5

 5 Fig. 5 Merging two nodes from two different cliques. Two nodes from different cliques are removed and a new node is added which takes all the connections of the two removed nodes.

Figure 8

 8 Figure 8 also shows the probability of C 0 divided uniformly among C 1 , C 2 and the rest of the cliques in the cluster tree. The close neighbors of C 0 in the tree C 1 , C 2 have a very

Fig. 7

 7 Fig. 7 Calculation of probabilities of merger of the left most leaf containing a clique (encircled) with other leaf nodes based on distances in the Cluster Tree T where the probabilities represent the likeliness of a node in the encircled leaf (containing a clique) to be merged with other nodes in the cliques.

Fig. 8

 8 Fig. 8 Calculation of P airwise M erges(C 0 , C b ) using distances in T and Probability Vector of C 0 to determine the number of merges between C 0 and C b where C b ∈ C and C 0 = C b .

Algorithm 2 :

 2 Merger of Nodes in the Cliques to Form Clusters in GInput: Graph G, Pairwise Merges, Node Merges, C = {C 1 , C 2 , • • • , C k } Output: G(V, E) begin foreach Ca ∈ C do foreach C b ∈ C do while Pairwise Merges(Ca, C b ) > 0 do Call Merge(Ca, C b ); Pairwise Merges(Ca, C b )=Pairwise Merges(Ca, C b )-1 ; end Procedure Merge(Ca, C b ); begin node nu, nv; nu ← Select One N ode rand (Ca) ; Node Merges(nu)=Node Merges(nu)-1 ; nv ← Select One N ode prob (C b ) ; Merging Nodes(nu, nv) ; end possible variations in the different steps that can change the behavior of the network generated. These variations demonstrate the robustness and flexibility of the proposed model as it can be used to generate networks with varying properties.

Fig. 9 A

 9 Fig. 9 A cluster tree T to generate Flat or Partitional clustering with the leaf nodes containing the cliques at the bottom level, the clusters at the second level and the root regrouping the clusters at the top level.

  and S. Boccaletti et al. ,Physics Reports 424, 175-308 (2006), with a few additional references added by hand. The network contains a single connected component with 379 nodes and 914 edges. The other Author network is the authors collaboration network in computational geometry. It was produced from the BibTeX bibliography obtained from the Computational Geometry Database geombib 1 , version February 2002. Problems with different names referring to the same person are manually fixed and the data base is made available by Vladimir Batagelj and Andrej Mrvar from the Pajek datasets website 2 . Only the biggest connected component was considered for experimentation where the reduced simple network contains 3621 vertices and 9461 edges.

Table 1

 1 Triad formation step, forcing a new node to connect to the neighbors of the first node it links to, in order to have triangles and increase the clustering coefficient. Comparing and Summarizing different Artificial Network Generation Models for Small World-Scale Free Networks existing in the literature.

				Comparative Summary of Existing Network Generation Models
	Model		Year	Nodes	Edges	Innovation
				Added	Added
				per	per
				Step	Step
	Holme and	2002	1	m
	Kim
	Dorogovtsev	2002	1	2	Randomly chose an edge and attach both ends of this edge with the
	et al.					new node where the probability of choosing an edge is based on the
						degree of the nodes at its ends.
	Jian-Guo et	2005	1	2	Each new node attaches to existing node with preferential attach-
	al.					ment and choses one of its neighbors again based on preferential
						attachment (and not randomly as compared to Holme and Kim).
	Wang et al.	2006	1	2	For each edge, a new node with two edges is added, which is
						attached to both end nodes of the edge. Produces Fractals rather
						than a random graph.
	Fu and Liao	2006	1	m	Once a new node attaches to a node, its neighborhood has a higher
						probability of connecting to the new node.
	Klemm and	2002	1	m	Activate and Disactivate nodes based on node degree where nodes
	Eguiluz					having low degree have a high probability of getting disactivated.
	Catanzaro et	2004	1	m	Assortativity &
	al.					Allows growth in old nodes by allowing new edges.
	Guillaume &	2004	1	m	Bipartite Structure identified as a fundamental characteristic for real
	Latapy					world graphs.
	Bu et al.		2007	1	m	n-partite Structure, where nodes do not connect to similar node
						types.
	Wang	and	2008	n	m	Add m new nodes and any two nodes in the m new nodes link
	Rong					together from each other and they link to existing nodes based on
						preferential attachment.

Table 3

 3 ,Comparative Summary of Various Statistics of Real World and Network Generation Models

	Model	Nodes	Edges Average Path	Clustering	Maximum
				Length	Coefficient	Node Degree
	Network Science	379	914	6.04	0.74	34
	Zaidi et al.	364	935	4.7	0.65	34
	Holme and Kim	379	757	4.86	0.77	42
	Fu and Liao	379	744	4.03	0.01	31
	Klemm and Eguiluz	379	755	9.08	0.5	33
	Catanzaro et al.	379	898	2.42	0.58	197
	Guillaume & Latapy	379	5315	2.30	0.54	109
	Bu et al.	379	755	3.05	0.37	80
	Wang and Rong	379	943	4.32	0.37	14

Table 2

 2 Comparing different models with the Collaboration Network of Scientists from the Network Science data.

	Comparative Summary of Various Statistics of Real World and Network Generation Models
	Model	Nodes	Edges	Average Path	Clustering	Maximum
				Length	Coefficient	Node Degree
	Geometry	3621	9461	5.31	0.53	102
	Zaidi et al.	3567	9433	5.4	0.66	127
	Holme and Kim	3621	7241	7.3	0.79	90
	Fu and Liao	3621	10662	4.22	0.005	101
	Klemm and Eguiluz	3621	10857	2.27	0.72	197
	Catanzaro et al.	3621	8896	2.47	0.48	1720
	Guillaume & Latapy	3621	528499	*	*	1275
	Bu et al.	3621	10856	3.13	0.24	607
	Wang and Rong	3621	10828	4.6	0.10	30

Table 3

 3 Comparing different models with the Collaboration Network of Scientists from the Computational Geometry data.

	Comparative Summary of Various Statistics of Real World and Network Generation Models
	Model	Nodes	Edges	Average Path	Clustering	Maximum
				Length	Coefficient	Node Degree
	Actor	7640	277029	2.94	0.87	1271
	Zaidi et al.	7413	244905	3.1	0.98	352
	Holme and Kim	7640	274865	2.35	0.09	2303
	Fu and Liao	7640	29972	4.00	0.004	163
	Klemm and Eguiluz	7640	274374	1.99	0.97	7627
	Catanzaro et al.	7640	28127	1.99	0.78	7639
	Guillaume & Latapy	7640	2378281	*	*	2614
	Bu et al.	7640	274935	1.99	0.83	12151
	Wang and Rong	7640	273355	3.28	0.94	83

Table 4

 4 Comparing different models with the Actor network from the IMDB dataset.

http://www.math.utah.edu/ ˜beebe/bibliographies.html

http://vlado.fmf.uni-lj.si/pub/networks/data/

http://www.imdb.com/


Faraz Zaidi
email: faraz@pafkiet.edu.pk

Fuzzy Clustering and Visualization of Information for Web Search Results

Keywords: Web Mining, Information Retrieval, Fuzzy Hierarchical Clustering, Visualization

Searching for information on the web is a common task. Often information on the web is distributed, semi-structured, overlapping and heterogeneous. Organization and Visualization of this information is an active area of research where the goal is to help users locate required information in web pages efficiently.

The most widely used data organization technique is clustering. This paper introduces a new clustering algorithm to organize web pages, and a visualization method which facilitates users to search information efficiently from the web. The algorithm presented is a hierarchical fuzzy clustering algorithm which uses domain knowledge to determine input parameters as opposed to other existing algorithms in the literature. The comparative results show that the algorithm performs as well as existing algorithms. Next, we present a methodology to visualize the clustered collection of documents and their contents such that users can visually explore data and extract information. A detailed example is presented to demonstrate various views to visualize clusters, documents and the keywords present in the web pages.

Introduction

The explosion of web pages has created an overload of information available on the Internet. Often this information is distributed, semi-structured, overlapping and heterogeneous [START_REF] Arotaritei | Web mining: a survey in the fuzzy framework[END_REF]. Development of efficient methods to organize and visualize this information is an active area of research [START_REF] Bonnel | Effective organization and visualization of web search results[END_REF] where the goal is to help users access this information quickly. A typical solution to this problem in the context of information retrieval from the web is to organize and to visualize search results of a query launched on a search engine [START_REF] Nguyen | A novel visualization model for web search results[END_REF]. Search engines such as Google; tend to return a long list of search results with titles, small images and short paragraphs. Users have to open each and every web page to assess its utility and relevance to the searched topic which can become tedious and unproductive [START_REF] Leuski | Lighthouse: showing the way to relevant information[END_REF]. As an example, consider searching for the word Jaguar using Google Search Engine. Top seven results returned by Google (see Figure 2), are distributed heterogeneously in the list, i.e. pages 1, 2, 3 and 6 are about the automobile Jaguar, pages 5 and 7 are about jaguar the animal and page 4 is about a super computer called Jaguar. If we look further down in the list, we find pages related to a software solution provider, a musical group, and a guitar manufacturing company all having the name Jaguar. Ideally we would like to group the pages together based on their content so that the user can immediately realize that there are multiple topics or themes related to the searched keywords as shown in Figure 1. To represent the contents of these groups, displaying noun phrases and keywords would allow users to glance contents of search results without reading or scanning individual web pages and thus reduce their effort in locating relevant information [START_REF] Wu | Finding more useful information faster from web search results[END_REF].

Clustering has long played a pivotal role in the organization of information and has been used by several researchers efficiently for information retrieval [START_REF] Salton | Introduction to Modern Information Retrieval[END_REF]. In the context of web pages, clustering has several applications such as organization of web search results [START_REF] Leuski | Lighthouse: showing the way to relevant information[END_REF], web browsing [START_REF] Zaidi | Revealing hidden community structures and identifying bridges in complex networks: An application to analyzing contents of web pages for browsing[END_REF] and automated categorization of web pages [START_REF] Halkidi | THESUS: Organizing Web document collections based on link semantics[END_REF].

Typically, document clustering techniques consider documents as entities, and calculate a similarity between documents based on keywords appearing in these documents. This similarity is further used to group similar documents together to obtain clusters. Intuitively, an alternative approach is to consider keywords as entities related to each other if they appear in a single document. Clustering keywords can group Themes together such that when a keyword is searched, its theme can be identified from the cluster it belongs to. Obviously documents can be associated to these themes and returned as search result to the user. We discuss a number of issues that need to be addressed before selecting the right clustering algorithm. shown that very often, a web page can belong to more than one category and thus it is more useful to use Soft or Fuzzy clustering algorithms. A decision is also required to choose between Hierarchical or Flat clustering. Naturally, information around us is organized in a hierarchical manner. Again this claim is supported by many researchers that tend to organize documents and web pages in hierarchies [START_REF] Dhillon | Enhanced word clustering for hierarchical text classification[END_REF][START_REF] Steinbach | A comparison of document clustering techniques[END_REF][START_REF] Zhang | A co-occurrence based hierarchical method for clustering web search results[END_REF].

Having said that we need hierarchical and fuzzy clustering algorithms to cluster web pages, we would like to point out some other requirements induced by the domain, that is, the web. In terms of hierarchical clustering, generating a hierarchy of high depth is not suitable, as the famous Three-Click Rule [START_REF] Zeldman | Taking Your Talent to the Web: A Guide for the Transitioning Designer[END_REF] suggests, users tend to abandon a site if they don't find their required information within three clicks. Therefore, the depth of the hierarchical clusters should not be more than 3 levels deep making the navigation hierarchy shallow and wide. Another requirement from the fuzzy logic perspective is that once we have calculated the degree of similarity of a web page to various clusters, we need to find a threshold which assures that only relevant pages are grouped together. The correct threshold value depends on the collection of web pages, the words searched and the degree of semantic disambiguity in the searched keyword. To solve this complex problem, instead of forcing a threshold value, we propose a method to visualize documents and clusters that allows a user to determine the relevance of a document to a cluster by examining its contents.

Finally the classical problem of deciding the number of clusters to be generated is also important. Instead of using it as an input parameter, this number should be determined based on the data itself. Also, in case of a hierarchical algorithm, the number of clusters generated at each level needs to be considered as well.

In this paper, we take a different approach to solve all these issues by looking at the co-occurrence network of keywords. These keywords are extracted from web pages to represent the contents of a webpage. A co-occurrence network is a graph where the nodes are represented by keywords and edges between keywords means that they appear together at least once in a web page. These networks have some interesting properties that can be used to devise heuristics which can eventually help us resolve issues described earlier. Based on these properties, we propose a new Hierarchical Fuzzy Clustering Algorithm based on Co-Occurrence Networks (HFC-CN) where the algorithm automatically determines the initial centroids and in turn, the number of clusters. The performance of the proposed algorithm is compared with other existing algorithms and the results are satisfactory as shown in Table 1. Note that we do not claim that the proposed algorithm outperforms the existing algorithms, but the automated parameter selection performs as well as the case where these parameters are selected manually. Next we use graph drawing algorithms to visually represent clusters, documents and their keywords (see Figure 1) to help users retrieve information. Details of the visualization methods are presented in Section 7.

The paper is organized as follows: In the following section, we summarize recent work related to Document Clustering using the Hierarchical Fuzzy Clustering Algorithms and Document Visualization techniques for web pages. Next, in Section 3, we formalize the problem and explain how the co-occurrence networks are constructed. Section 4 presents the data sets used as examples for experimentation. In Section 5, we present the details of the proposed clustering algorithm. Section 6 presents the results of the experimentation followed by discussion. Next, we present the visualization methodology using a case study in section 7. In the end, we present our conclusions and future research prospects in Section 8.

Related Work 2.1 Clustering

There are a number of document clustering algorithms available in the literature. We briefly present the different taxonomies of clustering algorithms in the context of document clustering and then focus on hierarchical fuzzy clustering algorithms. Clustering algorithms can be classified by different criteria. One classification can be based on the resulting clusters which can either be hierarchical or partitional [START_REF] Jain | Data clustering: a review[END_REF]. Hierarchical algorithms can be further classified as agglomerative or divisive. Another way to classify algorithms is the way in which similarity measure is being calculated [START_REF] Yoo | A comprehensive comparison study of document clustering for a biomedical digital library medline[END_REF] between documents like single link, complete link and the average link. We can also classify the algorithms if the resulting clusters are soft clusters or hard clusters [START_REF] Zhao | Soft clustering criterion functions for partitional document clustering: a summary of results[END_REF]. An important criterion often less studied is the way the documents are represented such as the vector space model [START_REF] Steinbach | A comparison of document clustering techniques[END_REF], the graph model [START_REF] Schenker | Comparison of algorithms for web document clustering using graph representations of data[END_REF] and the suffix tree model [START_REF] Zamir | Web document clustering: A feasibility demonstration[END_REF]. [START_REF] Yoo | A comprehensive comparison study of document clustering for a biomedical digital library medline[END_REF] have performed a comprehensive comparative study of different hierarchical (divisive and agglomerative) and partitional algorithms for document clustering and have shown that the bisecting k-means algorithm outperforms other clustering techniques. D. Arotaritei and S. Mitra [START_REF] Arotaritei | Web mining: a survey in the fuzzy framework[END_REF] provides a good summary of web clustering in the fuzzy framework.

Each of these classifications and algorithms has shown to be effective in the document clustering domain. No single algorithm clearly outperforms the other as different comparative studies have shown conflicting results [START_REF] Eissen | The suffix tree document model revisited[END_REF][START_REF] Schenker | Classification of web documents using a graph model[END_REF][START_REF] Steinbach | A comparison of document clustering techniques[END_REF][START_REF] Yoo | A comprehensive comparison study of document clustering for a biomedical digital library medline[END_REF][START_REF] Zhao | Evaluation of hierarchical clustering algorithms for document datasets[END_REF]. I. Yoo and X. Hu [START_REF] Yoo | A comprehensive comparison study of document clustering for a biomedical digital library medline[END_REF] has shown that over a large and different number of datasets, bisecting k-means using the vector space model outperforms the other hierarchical and partitional clustering algorithms and the suffix tree model, but [START_REF] Schenker | Classification of web documents using a graph model[END_REF][START_REF] Schenker | Comparison of algorithms for web document clustering using graph representations of data[END_REF] have shown that the graph model for representation of a document outperforms the vector space Model. [START_REF] Schenker | Comparison of algorithms for web document clustering using graph representations of data[END_REF][START_REF] Schenker | Classification of web documents using a graph model[END_REF] generate hard clustering using the graph model whereas [START_REF] Zhao | Soft clustering criterion functions for partitional document clustering: a summary of results[END_REF] has shown that soft clustering is more effective than hard clustering.

Other notable clustering algorithms used in the domain of web page clustering are [START_REF] Cutting | Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections[END_REF][START_REF] Zamir | Web document clustering: A feasibility demonstration[END_REF], but these algorithms do not produce hierarchical fuzzy clusters. A comprehensive survey on the topic of clustering web pages is by Carpineto et al. [START_REF] Carpineto | A survey of web clustering engines[END_REF].

Our focus in this paper is information retrieval where we limit our problem to the use case that a user has one or more than one keywords and the goal is to search for documents or web pages containing those keywords within a collection of documents.

In this paper, we present a new approach to document clustering which is based on clustering keywords. These clusters are then used to regroup documents, where the degree of similarity of a document and a cluster of keywords is calculated. As a result, a document can belong to more than one cluster. Clustering words is not a new idea. [START_REF] Dhillon | Enhanced word clustering for hierarchical text classification[END_REF][START_REF] Tjhi | Possibilistic fuzzy coclustering of large document collections[END_REF] have used word clustering to reduce dimensions of a document before eventually clustering documents. Our approach presents a solution to the information retrieval problem and has clearly different objectives than presented in [START_REF] Dhillon | Enhanced word clustering for hierarchical text classification[END_REF]. Furthermore the document clusters we produce at the end are overlapping which is completely different from [START_REF] Dhillon | Enhanced word clustering for hierarchical text classification[END_REF].

There are a number of Hierarchical Fuzzy Clustering algorithms proposed in the literature. G. Bordogna and Pasi [START_REF] Bordogna | Hierarchical -hyperspherical divisive fuzzy c-means (h2d-fcm) clustering for information retrieval[END_REF] provides a good overview of these algorithms. A general drawback for these algorithms is the number of input parameters required to determine the number of clusters, the initial centroids and the hierarchy cut. Our approach differs from these algorithms as we do not need the user to input any parameter for execution. We have compared our results with two such algorithms that require minimal number of parameters and have shown the results in Section 6.

Many researchers [START_REF] Backer | A clustering performance measure based on fuzzy set decomposition[END_REF][START_REF] Bensaid | Validity-guided reclustering with applications to image segmentation[END_REF][START_REF] Bezdek | Cluster validity with fuzzy sets[END_REF][START_REF] Gath | Unsupervised optimal fuzzy clustering[END_REF][START_REF] Kothari | On finding the number of clusters[END_REF][START_REF] Man | Detection and separation of ring-shaped clusters using fuzzy clustering[END_REF][START_REF] Zou | A new initialization method for fuzzy c-means algorithm based on density[END_REF] have undertaken to determine the correct parameters for clustering algorithms. Our aim is not to perform a comparative study but to show that domain dependent heuristics can help determine these parameters. In this paper, we use the co-occurrence network to achieve this task and the results shown in Section 6 reflect that the method performs well.

To compare the performance of the proposed algorithm, we use two algorithms that have similar goals to the clustering problem addressed in this paper, which is producing hierarchical fuzzy clusters for information retrieval: the Fuzzy Agglomerative Hierarchical Clustering (FAHC) Algorithm introduced by [START_REF] Yih-Jen | A new method for fuzzy information retrieval based on fuzzy hierarchical clustering and fuzzy inference techniques[END_REF] and the Hierarchical -Hyperspherical Divisive Fuzzy C-Means (H2D-FCM) Algorithm [START_REF] Bordogna | Hierarchical -hyperspherical divisive fuzzy c-means (h2d-fcm) clustering for information retrieval[END_REF]. The FAHC algorithm is an agglomerative fuzzy clustering algorithm which requires two parameters, the similarity threshold value and the difference threshold value. Both these values are used to determine how similar two documents should be to get clustered together. The H2D-FCM is a divisive fuzzy clustering algorithm which uses partition entropy to decide the best possible number of clusters (K) that are to be generated. Moreover the algorithm is required to run for a number of different K values before deciding the best possible value for K. For both these algorithms, we force the hierarchy of depth to three so as to avoid comparing a high depth clustering to a low depth clustering. As suggested earlier, this decision is supported by the Three-Click Rule [START_REF] Zeldman | Taking Your Talent to the Web: A Guide for the Transitioning Designer[END_REF]. One reason to choose these two algorithms is because one algorithm is agglomerative and the other is divisive covering two different approaches of clustering data.

Document Visualization

Different visualization systems to search and navigate through web pages have been proposed. These systems to visualize web pages can broadly be grouped into two categories: List Based Systems and Graphical Visualization systems. The list based systems keep the traditional ordered list visualization adding visual aids such as bolding words in the paragraphs [START_REF] Kickmeier | The effects of scanability on information search: An online experiment[END_REF] or clustering web pages and presenting a tree view [START_REF] Wu | Finding more useful information faster from web search results[END_REF][START_REF] Zeng | Learning to cluster web search results[END_REF] along with the list. Graphical systems represent search results in a graphical environment where the visualization can either be 2D [START_REF] Nguyen | A novel visualization model for web search results[END_REF] or 3D [START_REF] Bonnel | Effective organization and visualization of web search results[END_REF]. The effectiveness of both list based and graphical systems has been investigated by different comparative studies but no formal proof exists and thus remains an open area of research [START_REF] Aula | Enhancing the readability of search result summaries[END_REF]. The visualization we propose in this paper belongs to the category of Graphical Visualization Systems where we review a few systems below.

WebSearchViz [START_REF] Nguyen | A novel visualization model for web search results[END_REF] is a graphical system that uses the metaphor of the solar system where the user query is placed at the center and the relevant pages placed around it as a function of the similarity to the user query. It uses a vector-based similarity measure to compute the degree of relevance of a document to a keyword without clustering these documents. LightHouse [START_REF] Leuski | Lighthouse: showing the way to relevant information[END_REF] is an information retrieval system that integrated both the list based and graphical based visualization to represent the clusters. The visualization uses spheres to represent web pages and two spheres overlap if they are semantically very similar to each other. Although this is useful in case of a few web pages, but if many overlaps occur, it becomes difficult to visualize the web pages. [START_REF] Nguyen | A novel visualization model for web search results[END_REF] provides a good overview of the different visualization systems for web search results.

Problem Formalization

Formulating the document clustering problem, we say that given a set of n web pages represented by (p 1 , p 2 ,…, p n ), the goal of document clustering is to group documents into K clusters such that the documents from different clusters are dissimilar from each other based on some similarity criteria. For a Fuzzy clustering algorithm, the object can belong to all of the clusters with a certain degree of membership. And for a Hierarchical clustering algorithm, each cluster K can be further divided into smaller clusters. The FAHC and the H2D-FCM algorithms use the vector space model to represent a document where each document is considered to be a vector of term frequency-inverse document frequency (tf-idf) representing keywords and given by p i = (w 1 ,w 2 , … ,w m ) where p i refers to a document indexed 'i' and each 'w' refers to the tf-idf weight of a keyword. From this data, we construct a co-occurrence network, a graph G(V,E) where V represents the nodes or keywords (w) and E represent edges between two nodes if they appear together in a document. A node (keyword) is weighted by its frequency in the collection of documents and an edge is weighted by the number of documents in which the two keywords appear together.

These co-occurrence networks have two interesting properties.

First, the node degree distribution in these networks have a long tail like structure (see Figure 4) representing the scale free degree distribution [START_REF] Barab´asi | Emergence of scaling in random networks[END_REF]. This suggests that there are nodes in the network with very high node degree or connectivity. Another important property is that every node in this network belongs to a clique. This property is inherited by construction as all the keywords extracted from a single document are connected to each other by an edge in the co-occurrence network, thus forming a clique as shown in Figure 3. We exploit both these properties to determine initial centroids and the number of clusters-the details are explained in Section V.

Data Sets

We have used three different data sets for experimentation. These data sets are a collection of web pages found on Wikipedia encyclopedia. These web pages were returned as a search result when Jaguar, CAC40 and Hepburn were searched as a query on the Exalead1 search engine. The web pages returned contain pages in different languages pertaining to the searched word. In each case, the top 50 results were considered and keywords from these web pages were extracted by Exalead Search Engine (http://www.exalead.com/search/wikipedia/). From each webpage, 1 to 23 keywords were extracted and the average number of keywords extracted per page for the three collections is 13. These words were chosen due to their semantic ambiguity (Jaguar), domain specificity (CAC40 Paris Stock Exchange) and affiliation to a single entity (a unique person).

Proposed Algorithm

Detection of Number of Clusters and

Centroids using Topological Decomposition In this section, we present a decomposition method to identify the important keywords in the co-occurrence network. The method exploits the fact that nodes having high degree are responsible for keeping large size networks as a single connected component. This fact can be used to identify, what we call themes or subjects around which the different web pages are organized.

The goal is to identify the keywords that have a relatively high connectivity to other nodes but are not present in all the documents. We define a Min d -Degree Induced Subgraph (Min d -DIS) which is an induced subgraph of nodes having degree at least d in graph G. Mathematically for a graph G(V, E) where V is a set of nodes and E is a set of edges, the Min d -DIS is defined as G'(V', E') such that V' ⊆ V and each other, representing that they all appear together in documents, let's call these nodes core nodes of the network. Moving from high values of node degree, we eventually come across nodes that are not connected to the core nodes in the Min 70 -DIS graph.

Figure 6(b) is such an example where Min 50 -DIS contains nodes that are not connected to every other node. Here we clearly see that if the core nodes (found in Min 70 -DIS) are removed from this graph, we will be left with three connected components, the component with the nodes labeled Ferrari and Sports Cars, the Jaguar Cat and Atari. By repetitive application of this method, we identify these components as the basic themes of the collection of pages. We justify the use of degree of nodes by comparing it to the vector space model using tf-idf weights to represent documents. Note that the idf part of this weight assigns a low value to the keywords that are present in lots of documents. This is what we try to do when identifying themes, the keywords that are present in lots of documents can be found in what we call core nodes, thus we avoid using these nodes to determine the themes within the document collection. On the other hand, there are keywords that are present in a few documents, but are not so abundant in the entire document collection are interesting candidates to be identified as themes. Remember that the average number of keywords extracted and the maximum number of keywords extracted are not so different. We would like to mention that we tried another method called K-core decomposition [START_REF] Alvarez-Hamelin | k-core decomposition: a tool for the visualization of large scale networks[END_REF] to extract the core keywords and themes from the collection, but the results were not semantically and empirically encouraging.

Once we have identified these basic themes, we need to find the centroids for these themes. An additional information which can be used to devise the centroids for these themes comes from the fact that by construction, in the co-occurrence network, every node belongs to a clique (as all keywords belonging to a document are connected to each other in the co-occurrence network). If we look at Figure 6(b), the word Jaguar Cat, Atari and Ferrari, Sports Cars must belong to different cliques.

Moreover, by construction of the Min 50 -DIS, these nodes have a node degree of at least 50. This suggests that these nodes are important in this collection of documents. To find the collection of documents to which these themes belong, we simply group the nodes that are at distance 1 from each of these nodes in the entire network. In this way, we identify a group of documents belonging to a theme which can be used to calculate the centroid of the cluster for this theme. We also use these themes as centroid titles (see Figure 1). Algorithm 1 requires a parameter cutoff as input which represents the value up to which the Min d -DIS is calculated. To determine this value, we use a heuristic based on the degree distribution of nodes. Looking at the node degree distribution and their frequencies of the three data sets as shown in Figure 4, it is quite clear that in all these networks, there are nodes that dominate the number of connections by having a high node degree. Semantically, it is quite obvious, if we search for the word Jaguar on the web; all the pages returned will surely have this word and thus would have a very high degree as compared to the other words appearing in this collection of web pages.

To find out these high degree nodes, we calculate the slope of every two consecutive points of the degree distribution. At point 'a' in Figure 5, the slope becomes equal to zero. As the slope becomes zero or close to zero (values of -1 or -2) the point can be considered as the cutoff point where the nodes lying after this point represents the nodes that have relatively high node degree as compared to other nodes in the network. Since our goal is to generate a hierarchical clustering, we need to generate different cutoff points to incorporate the multilevel structure. Another point that stands out in the degree distribution of these co-occurrence networks is at some value for node degree, the number of nodes attain a maximum number, as pointed by 'b' in Figure 5. Since our goal is to generate a hierarchy of up to three levels, the second cutoff is considered to be the arithmetic mean of point 'a' and 'b' whereas the third cutoff is the point 'b'.

The idea of using node degree to first decompose the entire graph, and then identify themes works because the method by construction identifies nodes that appear with a relatively high frequency in the document collection. These keywords appear in a number of documents (because of their high degree), thus they play the role of keywords that span over a number of web pages and thus, are good candidates to start identifying themes.

Hierarchical Fuzzy Clustering Algorithm based on Co-Occurrence Network (HFC-CN)

Once we have calculated the cluster centroids, the remaining algorithm to generate a fuzzy clustering is quite simple. First we associate all the remaining nodes in the co-occurrence network by assigning them to one of the centroids. Remember that the edges between any two nodes are weighted by the number of documents that appear together. This weight can be calculated for a node and a centroid by adding the weight of all the edges between a node and the nodes of a centroid. As a result of this association, we generate a hard and partitional clustering for the network. We then calculate for each document in the collection its degree or relevance to these centroids giving us a fuzzy clustering where a document can belong to more than one centroid. To generate a hierarchical clustering, we run the algorithm for different values of cutoff where at each level, only the nodes belonging to a cluster are considered rather than the whole network. The resulting algorithm gives us a divisive hierarchical fuzzy clustering for the document collection. Each document has an associated degree of relevance to the other cluster centroid which in some cases can be zero as well. The results of the quality of clustering produced are tabulated in Table 1.

Experimentation and Results

To measure and compare the validity of the clustering produced by the proposed algorithm with that of FAHC and H2DFCM algorithms, we use two validity indices used in the fuzzy environment:the Partition Co-efficient (PC) [START_REF] Trauwaert | On the meaning of dunn's partition coefficient for fuzzy clusters[END_REF] and Partition Efficiency (PE) [START_REF] Bezdek | Cluster validity with fuzzy sets[END_REF]. Both of these methods are based on only the membership values [START_REF] Wang | On fuzzy cluster validity indices[END_REF] of an artifact to various clusters. The PC index indicates the average relative amount of membership sharing done between pairs of fuzzy subsets. The values range is [1/c, 1] where c is the number of clusters. The PE index is a scalar measure of the amount of fuzziness in a given fuzzy clustering where the values range is [0, log c]. In both of these cases low values indicate high clustering quality. To handle the hierarchical clustering, for each level we compute these validity indices and then we take the average over the different hierarchical levels. Note that we have forced the algorithms to produce a hierarchy of at most 3 levels. There are different approaches to evaluate cluster quality which can be classified as external, relative or internal. The term external validity criterion is used in the presence of ground truth [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF] or when the results of the clustering algorithm can be compared with some pre-specified clustering structures [START_REF] Halkidi | Cluster validity methods: Part i[END_REF].. Relative validity criteria measure the quality of clustering results by comparing them with the results of other clustering algorithms [START_REF] Maimon | Data Mining and Knowledge Discovery Handbook[END_REF]. Internal validity criteria involve the development of functions that compute the cohesiveness of a clustering by using density, cut size, distances of entities within each cluster, or the distance between the clusters themselves etc [START_REF] Halkidi | Clustering validity assessment: Finding the optimal partitioning of a data set[END_REF][START_REF] Milligan | A monte-carlo study of 30 internal criterion measures for cluster-analysis[END_REF][START_REF] Nguyen | Internal quality measures for clustering in metric spaces[END_REF].

For the given data sets, external validity criteria are simply not available. In the case of relative validity criteria, as Jain [START_REF] Jain | Data clustering: a review[END_REF] argues, there is no clustering technique that is universally applicable in uncovering the variety of structures present in multidimensional data sets. Thus we do not have an algorithm that can generate a benchmark clustering for data sets with varying properties. For these reasons we focus on internal quality metrics only.

Table 1 shows the results obtained by the HFC-CN algorithm as compared to the other two clustering algorithms using Partition Coefficient and Partition Efficiency. These values indicate how close the elements of a cluster are to each other, and how far apart they are from elements of other clusters. Comparing values for the different algorithms, it can easily be concluded that the HFC-CN algorithm's performance is comparable to other algorithms.

An important feature of the proposed algorithm is its different approach to calculate initial centroids. Whereas the other algorithms use only one single document as a centroid either chosen randomly, or based on the dissimilarity of existing centroids and a new document; the proposed method identifies important keywords and then calculates the initial cluster centroids based on a number of documents containing those keywords. Moreover, since the clustering is based on similarity of words as compared to similarity of documents, the topics that are similar based on some theme are grouped together and we only calculate the similarity of documents to the set of words that are clustered together. This seems to work well because semantically when we look at the clusters produced by the clustering algorithm, they are indeed coherent (see Figure 1).

Finally, we would also like to mention a few words on the efficiency of the algorithm. Other clustering algorithms based on minimizing sum-of-squares (such as the H2D-FCM algorithm) require multiple runs of the algorithm to obtain the correct value for the number of clusters K. The proposed HFC-CN algorithm uses heuristics to detect initial centroids and the number of clusters to be generated in a single pass which speeds up the clustering process.

In this section, we present a visualization method for clusters, documents and keywords present in the document collection. Figure 1 represents how the clusters are visualized to give an on overview of the document collection. The Clusters are placed in a circular layout represented by round nodes and violet color. The titles of the clusters are displayed which were identified at the time of theme detection described in Section 5. All the documents are placed in an outer layer using a circular layout algorithm [START_REF] Tollis | Graph Drawing: Algorithms for the Visualization of Graphs[END_REF] and are represented by square shaped nodes. The documents are connected by edges to cluster centroids.

Three different colors are encoded on these documents to represent different information. The documents that belong to only a single cluster are encoded with blue color. Recall that we have a fuzzy clustering and a document can belong to more than one cluster. To avoid edge crossings and to simplify the view, we have duplicated the nodes representing a document which belongs to multiple clusters-one copy for each cluster. Although this increases the number of actual documents (outer most layer), but we are able to avoid the edge crossing problem. This technique has been used by earlier as well to reduce visual clutter and simplify drawings [START_REF] Henry | Improving the readability of clustered social networks using node duplication[END_REF]. The nodes that are duplicated are shown in green color. To locate the presence of multiple copies of a document, or to identify how many clusters a document belongs to, we have used pink color, which is activated when a green node is selected. For example, in Figure 1, we can see that there are four instances of a document as this document belongs to four different clusters.

The edges connecting documents and clusters are encoded by a gradient from Red to Yellow representing high to low values. These colors represent the strength of membership of a document to a cluster. So, a red edge between a document and a cluster suggests that the document has high similarity as compared to edges in yellow color. A better example can be seen in Figure 7(a) where the DocumentView puts a document at the center, and the color encoding on the edges connecting to different clusters show the degree of association of the document to the clusters. From the given example, we easily see that the document titled jaguar cars is connected with high degree of association to the clusters vehicles, sports cars and jaguar but has less in common with the cluster Jacksonville Football League. DetailView as shown in Figure 8(a) enables a user to visualize a cluster and the related web pages in an expanded view where each keyword (node) is visible to the user. In Figure 8(a), we see the cluster Atari, and some of the web pages related to this cluster. The node in the center represents the title of the web pages as named in Wikipedia. Note that the visualization presented in this section only supports visualization of a single level clustering. If we put all the layers in the presented layout as layers, it becomes very difficult to understand the data and focus on individual pages and keywords.

Conclusions and Future Research Directions

In this paper, we have presented a divisive fuzzy clustering algorithm for documents. We use graph theoretical concepts on the co-occurrence network of keywords obtained from a collection of web pages. We have addressed the well-known problems of the detection of number of clusters, the initial centroids and the depth of hierarchy to be generated in the context of information retrieval and web pages. Comparative results show that the proposed method's performance is comparable with that of two other well known Hierarchical Fuzzy Clustering algorithms. Moreover we have presented a methodology to represent the clusters, documents and their keywords to help users efficiently navigate through the collection of documents. As part of future work, we intend to test the HFC-CN algorithm for other domains as it remains an interesting path to explore the performance of the proposed algorithm. We have not performed a formal user evaluation of the proposed visualization technique and this remains a priority to validate the efficiency of the system. Moreover, the current visualization only suits single level clustering, we tend to extend this work and find ways to enable the user to navigate and visualize a hierarchy of clustering.

Figure 1 .

 1 Figure 1. (a) Showing the Bi-partite graph of Web pages and Keywords (b) Clustered Network showing Clusters and Web pages.

Figure 2 .

 2 Figure 2. Screen Shot of the top seven Search Results returned by Google for the searched term Jaguar.

Figure 3 .

 3 Figure 3. Co-Occurrence Network of Keyword Jaguar, Disconnected components can be easily identified as forming a clique.

Figure 4 .

 4 Figure 4. Degree Distribution of the three data sets.

  E' ⊆ E, ∀ u ∈ V', Deg G (u) ≥ d where d can have values from 0 to the maximum node degree (represented by MaxDeg) possible for a network. We construct Min d -DIS for d = {0,1,…,MaxDeg} to obtain a set of graphs (G 0, G 1 ,…,G MaxDeg ).

Figure 5 .

 5 Figure 5. Degree Distribution of Jaguar Co-Occurrence Network.

Algorithm 1 .

 1 Detection of Number of Clusters and their Centroids.

Figure 6 .

 6 Figure 6. (a) Min70-DIS and (b) Min50-DIS for the Jaguar example

Figure 8 (

 8 b) shows a portion of Figure 8(a) after zooming the bottom-right corner. The bottom-left webpage in figure 8 refers to the Atari game, bottom-right page refers to the web page on Wikipedia called jaguar homonymy disambiguity and contains the different semantic meanings related to the jaguar keyword existing in the Wikipedia database. The webpage on the right represents the webpage about the game called Alien vs. Predator based on the famous movie by James Cameron.

Figure 7 .

 7 Figure 7. (a) DocumentView where a document is placed at the center and its relationship to other clusters is shown by color encoding on the edges is shown. (b) ClusterView where the centroid of a cluster can be seen, intensity from blue (high) to yellow (low) color of the represents the frequency of keywords in the entire document collection.

Figure 8 .

 8 Figure 8. (a) DetailView showing the expanded view where the keywords (nodes) of a cluster and the web pages can be seen (b) A zoom-in on the right-bottom of the DetailView.

Table 1 .

 1 Comparisons of results of clustering algorithms using partition coefficient and partition efficiency.