{'fraction_non_alphanumeric': 0.020374431836241696, 'fraction_numerical': 0.00778741934458536, 'mean_word_length': 5.043411448328851, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Demographic and Structural Characteristics to Rationalize Link Formation in Online Social Networks

Recent years have seen tremendous growth of many online social networks such as Facebook, LinkedIn and MySpace. People connect to each other through these networks forming large social communities providing researchers rich datasets to understand, model and predict social interactions and behaviors. New contacts in these networks can be formed either due to an individual's demographic profile such as age group, gender, geographic location or due to network's structural dynamics such as triadic closure and preferential attachment, or a combination of both demographic and structural characteristics. A number of network generation models have been proposed in the last decade to explain the structure, evolution and processes taking place in different types of networks, and notably social networks. Network generation models studied in the literature primarily consider structural properties, and in some cases an individual's demographic profile in the formation of new social contacts. These models do not present a mechanism to combine both structural and demographic characteristics for the formation of new links. In this paper, we propose a new network generation algorithm which incorporates both these characteristics to model growth of a network.We use different publicly available Facebook datasets as benchmarks to demonstrate the correctness of the proposed network generation model.


I. INTRODUCTION
Past decade has seen an exponential growth in the usage of online social networks such as Facebook, LinkedIn and MySpace [1] with hundreds of millions of users connecting to these networks everyday. The field of social network analysis and complex networks has profited from these networks as they provide rich datasets for researchers to investigate various hypothesis and conjectures related to social behavior and social dynamics in our society [2], [3]. These networks in general, undergo several processes such as information propagation [4], marketing [5], spreading viruses [6] and community formation [7] which can be studied using analysis methods, network metrics, visualization methods and clustering algorithms on large realistic datasets which was not possible in yesteryears.
Substantial research has been conducted in modeling social networks where the objective has been to develop algorithmic models that can mimic structure and evolution of real world networks. More often than not, researchers have targeted structural characteristics such as high clustering coefficient, small geodesic distance, degree distribution following powerlaw, assortative mixing and presence of communities in these networks [8]- [12].
These models are quite useful in the study of networks as they help to generate large networks with desired structural properties. Thus, giving us a better understanding of how networks are organized, how they evolve overtime and how structural dynamics impact the overall network properties. Furthermore, these models are also useful for simulation studies to examine different network processes taking place such as epidemic spread, influence mining and formation of community structures [8], [13]. Another application area for these models is to test various sampling effects [14] as using these models, we can generate networks with different sizes and structural properties.
Apart from the structural characteristics, another aspect of these networks are the demographic characteristics of individuals that play an important role in the link formation. Demographic characteristics include attributes such as age group of an individual, gender, geographic location, professional activity sector, personal interests and hobbies [15]. Most of the network generation models proposed in the literature do not consider these demographic characteristics. Some models have been proposed in the literature with the concept of social spaces and distances to refer to the demographic properties of individuals but the details of these properties are often omitted in these papers [8], [16]. They directly utilise distances drawn from some distribution to refer to how close two individuals are, which in turn determines the probability of link formation among individuals. We argue that it is to some extent, pivotal to consider both structural and demographic characteristics to develop a better understanding of the evolution process and rationalize link formation between two individuals in a network.
In this paper, we propose a new network generation model, which considers both structural as well as demographic characteristics to generate social networks. The proposed algorithm is based on two steps: initialization and construction to generate networks with desired properties. We use different publicly available datasets from the famous social networking website Facebook to validate the proposed model as we were able to reproduce networks with similar properties. These results are documented in section VI.
The rest of the paper is organized as follows: We discuss a number of articles that propose network generation models in section II. In section III, we formulate an equation to incorporate demographic as well as structural characteristics to determine similarity among two nodes, which in turn drives the connectivity of the whole network. In section IV, we provide the details of the proposed model which consists of two steps, initialization and construction. Section V describes the experimental setup and the datasets used for comparative analysis followed by the results and explanation in section VI. Finally, we conclude in section VII giving possible future research directions.

II. RELATED WORK
The discovery of small world and scale free networks has revolutionized the way we study networks around us. Among other networks, social networks also exhibit small world and scale free properties. Watts and Strogatz (WS) [17] proposed a model to simulate the occurrence of triadic closures (clustering coefficient) and the small world effect (short geodesic distances) in networks. Starting from a regular lattice, random rewiring of links with a certain probability p, transforms a regular lattice into a network commonly known as small world networks. Albert and Barabasi (BA) [18] introduced preferential attachment to simulate how networks with degree distribution following power-law evolve in real networks, commonly know as scale free networks or networks with scale free degree distribution. Starting from a few nodes, new nodes are introduced in the network which connect to older nodes with a probability proportional to the existing connectivity of the nodes. Nodes with higher degree have higher probability of forming new links, and these networks are commonly called scale free networks.
Most of the early works followed by these two ground breaking models revolved around the idea of having a unified model to generate both small world and scale free networks. For example, Holme and Kim [12] proposed a modification to the BA model adding a triad formation step after the preferential attachment step to create triads in the network. This increases the overall clustering coefficient, thus generating a network with both small world and scale free properties. Other variants of the BA model such as [19]- [24] produce networks having high clustering coefficient by introducing triads one way or the other and nodes connect using the preferential attachment rule to have a scale free degree distribution.
Different researchers have used the idea of n-partite, and specially bi-partite graphs to generate social networks. The authors [25] introduce the idea to generate affiliation networks similar to co-authorship networks [26] using random bipartite graphs with arbitrary degree distributions . This idea is also used by Guillaume and Latapy [27] as they identify bipartite graph structure as a fundamental model of complex networks by giving real world examples. The authors call the two disjoint sets of a bipartite graph as 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. The bipartite graph is then projected as a unipartite graph to obtain a small world and scale free network. A more generalized model based on similar principles was proposed [28] 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). The authors discuss the example of sexual web [29] which is based on the bipartite structure. 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.
A growing network model [11] was proposed to incorporate the assortative mixing behavior in social networks. Assortative mixing here, refers to the structural property of individuals to connect with individuals having similar number of links. This model allows links to be added between existing individuals as well as new individuals on the basis of their degree thus forcing links between similar degree nodes, and inducing high assortativity in the network.
Models based on demographic attributes have also been proposed where the goal is to determine connectivity based on social attributes. The social similarity, in these artefacts is often referred to as the social distance and the approach in general is termed as spatial approach for network generation. One such model based on social distance between individuals was presented by [30] where the model aims to generate networks with high clustering coefficient, assortativity and hierarchical community structures. Social distance refers to the degree of closeness or acceptance that an individual feels towards another individual in a social network. The closer two individuals are, the higher they have a probability to form a new link. The authors used a real acquaintance network to demonstrate the correctness of the proposed algorithm. Another model [16] was proposed which uses spatial distance to model nodal properties and homophilic similarity among individuals. The model randomly spreads nodes in a geographical space such that the edge formation probability is dependent on the spatial distance among nodes. The network thus generated exhibits high clustering coefficient, small geodesic distance, power-law degree distribution, and the presence of community structures.
A three phase spatial approach [8] was proposed to generate networks with controllable structural parameters. This approach controls three important structural characteristics, the clustering coefficient, assortativity and degree distribution using input parameters making it quite useful to generate large networks. The model also takes as input, the degree sequence required in the final network. This static model uses a notational space to identify nodes closer to each other, a layout modification step to move nodes with similar degree closer and edge creation among nodes based on these spatial and layout modification step to achieve desired clustering coefficient and assortativity.
A very recent model focuses on the homophilic property of social networks [31]. The authors modify the BA model by introducing a homophilic term which creates regions where characteristics of individuals impact the rate of gaining links as well as links between individuals with similar and dissimilar characteristics. The model maintains five important network features, power-law degree distribution, preferential attachment, short geodesic distance, high clustering coefficient and growth over time.
Evolutionary network models with aging nodes have also been proposed in the literature such as [32]- [35]. For example [35], the authors study the dynamic behavior of weighted local-world evolving networks with aging nodes. Newly added nodes connect to existing nodes based on a strength-age preferential attachment and the results show that the network thus generated has power-law degree distribution, high clustering coefficient and small world properties.
There exists a number of models based on the localworld phenomena [35]- [38] where nodes only consider there neighbourhood in contrast to traditional network models that assume the presence of global information. For example [38] investigate a local preferential attachment model to generate hierarchical networks with tunable degree distribution, ranging from exponential to power-law.
Another class of graphs models, the exponential random graph models have gained a lot of popularity [39]- [41] also known as p * . These models are used to test, to what extent nodal attributes and structural dependencies describe structure of a network measured using frequency of degree distribution, traids and geodesic distances [42]. The possible ties among individuals are modelled as random variables, and assumptions about dependencies among these random tie variables determine the general form of the exponential random graph model for the network [41]. An important difference between network generation models and ERGMs is that network models try to explain how a network evolves whereas ERGMs do not explicitly explain network generation process [42].
Models to generate clustered graphs also exist in the literature where the goal is to have community structures embedded in the resulting networks [43]- [46]. Since we do not address the issue of having community structures in the current work, we intend to incorporate this structural feature of many real world networks as part of future work.
An exhaustive review of network generation models is out of scope in this text, yet we have tried to cite a wide spectrum of different network generation models. Partial surveys, reports and comparative analysis for different network generation models can be found in [8], [13], [19], [42], [47], [48]. None of the models to generate networks considers demographic and structural attributes during the network evolution process where as our contribution lies in considering demographic as well as structural characteristics as the driving force for link formation between individuals. The results we obtained from simulations using the proposed model demonstrate that the final networks obtained have small geodesic distances, high clustering coefficients and frequencies of degree distribution following power-law. We validate our model through comparative analysis as we generate networks similar to real world Facebook networks and the results are presented in section VI.

III. DEMOGRAPHIC AND STRUCTURAL CHARACTERISTICS
The proposed model is quite generic and aims to provide a general equation which can be further refined by adding more network specific details. First we introduce the equation, and then we provide details of the model implemented using the equation.
The premise upon which the proposed equation is developed is that, for individuals i and j, the link formation is a function f of two types of characteristics, demographic (D) and structural (S ). Mathematically we can represent this relation as: where D i,j and S i,j represent the demographic and structural similarities between individual i and j respectively, α and β represent equilibrium factors to control the balance between demographic and structural characteristics. Within this basic framework, different demographic and structural attributes can be considered. Specially for demographic characteristics, we propose a method to handle categorical, ordinal and numerical attributes separately, which can further be modified and tweaked depending upon the type of network to be generated, the available attribute information and other domain level knowledge that can be incorporated to justify link formation among pair of individuals. We discuss details of how demographic and structural characteristics are handled to calculate the possibility of link formation between two nodes below:

A. Demographic Characteristics
As discussed above, we consider different categorical, ordinal and numerical characteristics as demographic characteristics of an individual. For every categorical attribute C p where p represents different attributes, the similarity between individuals i and j is assigned using the following equation: Similarly for every ordinal attribute O q where q represents different attributes, the similarity between i and j is calculated using: where i q , j q are the ranking orders, | * | represents absolute value and O q is normalized using the maximum different ordinal values possible for attribute q denoted by ρ q in the above equation. Similar to ordinal attributes, we calculate the normalized difference between numerical attributes of i and j using the following equation: Using the above equations, we can calculate an accumulative similarity value using equations 1,2 and 3, based on weighted demographic characteristics as follows where ω represents weights associated to each attribute signifying its importance in the process of link formation.
The above equation shows a linear combination of a categorical, an ordinal and a numerical characteristic to give a general form where any number of such demographic attributes can be combined together.

B. Structural Characteristics
In case of structural characteristics, we consider two properties, the triadic closures (commonly known as friend-ofa-friend phenomena in sociology) which controls the global clustering coefficient, and preferential attachment to control the degree distribution of the generated network. Preference for formation of triadic closures as i and j have common friends is calculated using the following equation: where i ∩ j represents the common friends of i and j and min(i, j) represents the minimum number of friends of either i or j. The minimum value in the denominator ensures that a relationship is not penalized just because one of the individual has high number of links. The more friends two individuals have in common, the more chances they have of forming a new link among themselves. As the network continuously evolves and new edges are added among previously added individuals, this process results in increasing overall clustering coefficient. To handle the preferential attachment PA in link formation, we use the following equation: For an newly added node j (which initially will have zero connections), the probability of connecting to a node i already existing in the network is directly proportional to the normalized degree of node i. The degree is normalized using the maximum node degree in the current network represented by max(deg n ). We normalize this factor just to control the weight of each structural characteristic as all our characteristics are normalized between values 0 and 1.
Finally combining equation 5 and 8 as input to equation 1, we can calculate an accumulated similarity for link formation between two individuals where both demographic as well as structural attributes are taken into account. Collectively, we refer to demographic and structural attributes as similarity based link formation.

IV. PROPOSED MODEL
Apart from the distribution of demographic attributes, the model takes as input, the desired number of nodes in the network n, the minimum and maximum node degree m o and m f , the probability of similarity based link formation using equation 1 P (Sim), the probability of triad formation P (T ) and triad count t c to determine the number of links that would be used to form triads. We also take weights ω for each demographic and structural attribute which can eventually help us to tune each characteristic's role in the formation of links among individuals.
The model comprises of two basic steps, the initialization step and the construction step. Within the construction step, two steps are performed, similarity based linking and triad formation. All these steps are described below: 1) The initialization step randomly assigns demographic attributes in the given proportion to each of the n nodes of the network. This results in a set of initialized nodes as shown in figure 1. The nodes are numbered to associate a logical order which can be assigned randomly as the model is independent of this ordering of nodes. 2) To start construction of the connected network, the algorithm selects the first three nodes and connects them as a triad, irrespective of their similarity, as shown in figure 2(a). probability of the similarity based connection is 0.6, then the rest of the times n is connected to a randomly selected node. b) Based on the probability of triad formation P (T ), n is then linked to t c neighbors of the nodes it connected to in the previous step, selecting the most similar nodes using equation 1 forming triads. For example if the probability of triad formation is 1, and t c is 2 then n connects to two neighbors of the node it connected to in the previous step.
In case, there are no neighbors, it chooses nodes randomly. 4) The process is repeated from step 3 until all the nodes in the initialization set are processed in the construction step.
For clarification, we consider a small example with seven nodes. We consider the case of three demographic attributes, school (categorical), major (categorical) and age (numerical). Given as input, there are 3 possible schools in the proportion (2:2:3), there are two possible majors in the proportion (3:4) and the students have 3 possible age values in the proportion (3:3:1). These attributes are assigned randomly to all the seven nodes as shown in figure 1 where the color coding in the initialization set depicts a unique color for a combination of attributes. So for nodes 3 and 5, the same color means that these individuals have exactly the same values for all demographic characteristics.
During the construction step, nodes from the initialization step are iteratively added to the network as shown in figure 2.
Step (a) in figure 2 shows that nodes 1, 2 and 3 are connected as a triad.
Step (b) shows that node 4 is added to the network and connects to node 3 based on node similarity. Subsequently nodes 5,6 and 7 are added to the network where similar nodes form links on the basis of equation 1 and triad formation step introduces traids in the network.

V. DATA SETS AND EXPERIMENTAL SETUP
We used Facebook datasets provided by [49] which represent the structure of 100 different american colleges and universities at a single point in time. The demographic attributes present in the dataset are gender, class year, major and residence (housing). We used five randomly choosen networks out of these hundred datasets for comparative analysis. The five networks are named as Caltech (769 nodes), Reed (962 Formation mo m f P (Sim) P (T )  tc  Caltech  1  44  1  1  3  Reed  1  40  1  1  3  Simmons  1  43  1  1  4  Middlebury  1  83  1  1  4  American  1  72  1  1  4   TABLE I  PARAMETERS USED TO GENERATE GRAPHS EQUIVALENT TO ORIGINAL  DATASETS FROM FACEBOOK. nodes), Simmons (1518 nodes), Middlebury (3075 nodes) and American (6386 nodes) networks. We tested our model to simulate networks of exactly the same size as that of these five networks and the distribution of demographic attributes was kept exactly equal to the original datasets. As a result, the nodes have exactly the same distribution of demographic attributes as in the original networks. We perform a structural comparison the original and the generated networks using density, geodesic distances, clustering coefficient, power-law fit and assortativity. The power-law fit is calculated used the method proposed by [50]. The five graphs were generated using the parameters listed in table I.
For the current experiments, the ω for all attributes is kept 1, giving equal importance to all attributes. We plan to conduct an extensive study of the effects of varying these parameters and generating graphs with varying structural properties as part of future work.

VI. RESULTS AND DISCUSSION
We compared the generated graphs with the original graphs using five metrics, the node-edge ratio often called density, the clustering coefficient, the average geodesic distance, the power-law fit and assortativity. The results are shown in figure  3, 4, 5, 6 and 7 where the five datasets are compared to the generated networks using the proposed model.
In case of density, the values generated by the proposed model are very similar to the original networks as shown in figure 3. The proposed model uses the parameters m o and m f where the mean of the two approximately represents the overall density of the generated network. Increasing these values increase the overall density and vice versa. An important remark about these parameters is that this does not necessarily mean that the maximum degree of a node will not exceed m f . These parameters signify the number of connections that a new entering node will form, not with whom they form so it is normal that due to preferential attachment, a new node might connect to a node with very high degree which might have connections more than m f . Figure 4 shows the clustering coefficients of the original and the generated graphs. Again, we were able to generate values that are very close to the desired values. The clustering coefficient is controlled through the parameters P (T ) and   t c where P (T ) is the probability of triad formation taking place and t c represents the number of such triads to be formed. Increasing this number increases the overall clustering coefficient of the generated network.
In figure 5, we compare the geodesic distances of the networks again showing high similarity. We do not have any specific parameter to control this value but while calculating similarity based link formation, we consider preferential attachment based on degree connectivity, which results in both small geodesic distances for the generated graphs and their degree distribution following power-law as shown in figure  6. All the generated networks have a power-law fit between 1.9 and 3.1 suggesting scale free behavior of the proposed  model. We were not able to match the power-law fit with that of the original facebook networks, since we incorporated the preferential attachment model [18], which is known to result in scale free degree distributions with power-law fit around 2 or 3. This fact is also well known for social networks but with the facebook datasets we used, the values of power-law fit are not between 2 or 3. Our experimentation suggests that we need to modify the existing methods to generate degree distributions to have a better fit rather than using the known preferential attachment model. One way to achieve a matching degree distribution is to use the model proposed by [51] which generates a network given a degree distribution. Figure 7 shows the comparative assortativity values for the original and the generated networks. In case of Caltech and Simmons datasets, the original networks show a slightly negative assortativity, or disassortative mixing, where as generated networks although have also very small values, but they are still positive. In case of Reed, Middlebury and American datasets, the original as well as generated networks have all positive values. The differences between original and generated networks for all five datasets are negligible. The proposed model does not currently enforces any structural method to control assortativity in the generated networks but still the model was able to achieve very similar values to that of real Facebook datasets. We also performed a visual comparison of the Caltech dataset which is the smallest network among the five networks with 769 nodes. Figure 8 shows the layout of the the original network and the generated network using the proposed model. The nodes in the figure are colored with their degree. The nodes are placed on approximately the same locations in a circular layout. It is difficult to draw concrete conclusions about the similarity of each node but there are no major differences in the overall structure of the two networks. Since we did not intend to produce exactly the same network, we do not perform a node level comparison between the two networks. Furthermore, the proposed network model can be used to generate large size networks with similar structural and demographic properties, in which case, node level comparison will become meaningless.
Our comparative analysis shows high structural similarity among the original and generated networks apart from the power-law fit. The models is flexible any of the structural or demographic characteristic can be ignored (by assigning ω = 0), or given more importance (by reducing ω of other attributes). This flexibility is an important feature of the proposed model as it gives more control on how the network is generated as well as enables us to study the effects of different structural and demographic attributes.
To demonstrate the scalability of the proposed model, we generated different large size networks on a standard Intel i5 machine, 2.5 GHz dual core processor with 4GB memory. The Fig. 8. Visual layout of the original and generated networks for the Caltech data set. The algorithms are layed out using circular layout. Nodes are colored with respect to node degrees with a gradient from Blue (High degree nodes) to Orange (Low degree nodes). The images are generated using Tulip Software [52]. Nodes  Seconds  1000  1  10000  99  100000  10305   TABLE II  RUNNING TIMES FOR GENERATING LARGE SIZE NETWORKS USING THE   PROPOSED MODEL. running time in seconds for the generated networks are shown in Table II. VII. CONCLUSION In this paper, we have proposed a network generation model based on demographic and structural characteristics in order to better understand and rationalize link formation among individuals. We used different Facebook datasets to validate our model as it was successfully able to regenerate the same densities, clustering coefficients and geodesic distances. The model generated networks that are scale free using preferential attachment, but was unable to produce the same power-law fit as the original networks.

Dataset Size Running Time
Extensive study needs to be performed to study the effects of ω which were kept 1 through out our experiment as well as the balancing factors α and β. We intend to continue this study as part of future work to have a more generalized view of the proposed model. Furthermore, we have not included any structural characteristics to control assortative mixing of individuals and we plan to incorporate this feature as well, which will enable the current model to generate assortative as well as disassortative networks. Another important feature of social and other complex networks is the presences of community structures and we also foresee this amendment to the proposed model to generate more realistic networks.