Heuristic methods for synthesizing realistic social networks based on personality compatibility

The details vary by specific application, but in their simplest form, in a social network the nodes may correspond to people in a group, organization, or population of interest. The presence of a link connecting two nodes represents some relationship, such as kinship, friendship, collaboration, or information exchange, between the people corresponding to the nodes the link connects. For example, social networks are used to represent social distance in (Li et al., 2018) and information spreading in (Bouanan et al., 2018). The study of the structural properties of such social networks can provides insight into the group, organization, or population it represents. As an example, Fig. 1 shows a real world social network found to exist within a corporate law firm in the northeastern United States (Lazega 2001).

Not all social networks have the same structural characteristics and properties. Social networks that represent communications in terrorist organizations might be expected to differ in structure and activity from those that represent collaborations in a scientific community. A set of social networks that represent instances of some well-defined category of group of organization will be termed a class. Some examples of classes of social networks are listed in Table 1; several of the examples in the table are based on (Easley and Kleinberg, 2010). The examples in Table 1 are all social networks, but intuitively they are not the same in terms of structure.

Note that in the last example in Table 1, the nodes of the social network correspond to organizations, not individual people. That example is included in order to draw attention to this distinction. This work focuses on social networks where the nodes correspond to people. The potentially different structure of an organizational-node network as compared to a people-node network will become of interest later.

A particular social network may be an element of one class, but not of another, by virtue of its structural properties. Therefore, two operations are of interest: (1) Membership; given a social network, how can it be tested for membership in a particular class of social networks? (2) Generation; given a description or example of a particular class of social networks, how can a synthetic social network that is a member of that class be generated? This work focuses on the second operation.

In the implementations described later, social networks were stored internally using adjacency matrices (Gersting 2014). More sophisticated data structures for social networks are available, but the networks used in this work were relatively small and simple adjacency matrices were sufficient. As for the attributes of the networks, two are important. First, networks may be weighted or unweighted. This work is concerned solely with the absence or presence of links, and therefore only unweighted networks were used. Second, networks may be symmetric or asymmetric. Links in symmetric networks typically represent mutual or two-way relationships, whereas links in asymmetric networks represent one-way relationships. This work is concerned solely with mutual relationships, and therefore symmetric networks were used.

In this context, metrics are numerical measurements of a social network’s structure. A wide range of different metrics are available. Graph theory provides a number of abstract metrics, sometimes known as graph invariants, that quantify some aspect of a network’s structure without attaching any specific semantic meaning to the metric’s values. Examples include maximal degree, girth, or vertex chromatic number (Bang-Jensen and Gutin, 2008). Social network analysis has defined additional metrics that are intended to measure something about the network that has semantic meaning in the context of the social application of the network. These metrics include centrality (Scott 2000), reciprocity (Newman 2010) (Scott & Carrington, 2011), and clustering coefficient (Easley and Kleinberg, 2010). Finally, overarching empirically-derived structural properties common to categories of networks, such scale-free and cellular, may apply to social networks (Tsvetovat and Carley, 2005). All are intended to measure in an objective and quantitative way some aspect of a network’s structure that may be useful for a particular application. The intent is that realistic synthetic social networks would have metric values similar to those of the real-world social networks they were intended to mimic, without having identical structures.

Many network metrics have defined, and clearly not all could be used in this work. From those available, 20 were carefully selected to assess the similarity of real-world and synthetic social networks in this work. That selection was made in part based on the motivation of studying the social networks of future space colonies. Thus metrics that characterize information flow, integration of individuals into the network, level of camaraderie indicated by clustering, and level of influence among the individuals are of interest. Because this work used only undirected symmetric networks, only metrics suitable for those networks were considered.

The metrics selected include both standard metrics of graphs’ structural characteristics (nodes, links, components, degree, radius, and eccentricity) and metrics considered to be relevant to social network structure, per (Rapoport 1957) (Freeman 1978) and (Bonacich 2007). In the former category, the number of nodes, links, and components, the network’s radius and eccentricity, and the nodes’ degrees fundamentally characterize a network’s structure.

In the latter category, metrics found useful to study team structure and interaction were of special interest. Global clustering coefficient, average clustering coefficient, Gini coefficient, and number of communities provide some insight to the tight knit groups and the distribution of nodes among the communities. Average betweenness serves as a basis of comparison for maximum betweenness to identify the information brokers or potential bottle-necks in the network. Likewise, average closeness serves as a basis of comparison for minimum closeness to identify the nodes that are at the heart of communities. Mean path length, network radius, average eccentricity, and network diameter are geodesic distances that can be used estimating the rate of information flow across a network. Eigencentrality indicates the level of influence that a node may exert on other nodes. In some similar applications, clustering, path length, betweenness, closeness, and diameter were used in a study of information sharing and collaboration in small groups (Manso and Manso, 2010), betweenness was used in a study of interaction in programming teams (Gloor et al., 2011), density and diameter were used in a study of authorship collaboration (Gajewar and Das Sarma, 2012), eigencentrality was used in a study of leadership in social groups (Bullington 2016), and Gini coefficients have been used as a measure of inequality of participation in digital health social networks (van Mierlo et al., 2016). Table 2 lists and defines the metrics used.

In 1923, Jung described distinct human personality types based upon his clinical observations (Jung 1971). Using Jung’s ideas, in 1944 (Myers, 1962) developed a structured approach to identifying personality types and published a manual describing a personality typing process that later became known as the (Myers & McCauley, 1985) Type Indicator (MBTI) (Smathers 2003). In the MBTI typing scheme, each person is categorized on four “dichotomies” or dimensions, held to correspond to different aspects of personality. Two “preferences” or values are possible on each dichotomy, yielding a total of 16 different personality types. The four dimensions and their two preferences each are:

Table 3(a) shows the estimated proportion of the United States population who would be categorized into each preference, with each dimension considered separately (Marioles et al. 1996; Mitchell, 1996). Table 3(b) shows the result of calculating a proportion for each personality type, based on the dimensions’ proportions. A detailed description of the 16 Myers-Briggs types is beyond the scope of this article; for details see (Keirsey 1998). The important ideas here are that each person may be categorized as having one of the 16 types and that the likely compatibility of two people may be estimated from their personality types.

Critics of the MBTI personality model point to apparent problems. Metzner et al. suggested that the “rigid” dichotomies of the Jungian personality types constitute a “conceptual straight jacket” and proposed a reformulation of the dichotomies as pairs of primary and inferior psychological functions (Metzner, Burney, and Mahlberg, 1981). Additionally, McCrae and Costa commented that the MBTI lacks a neuroticism factor, perhaps because emotional instability was not part of Jung’s type definitions, and it appears that Myers and Briggs believed that each personality type was positive. The lack of a negative factor may make the interpretation of MBTI results easier to accept. However, it could also allow the omission of information that would be useful to employers, coworkers, counselors, and individuals (McCrae and Costa, 1989).

Nonetheless, the MBTI model is used and accepted at the U. S. National Aeronautics and Space Administration, the organization from which this work’s motivating application is drawn, e.g., (Nelson and Bolton, 2008). It is also widely used in industry in the United States, including 89 of the Fortune 100 companies (Grant 2013), for applications that include increasing self-awareness to support decision analysis (Malik and Zamir, 2014) (Weiler 2017), improving team performance by explaining communication styles (Choo, Lou, Camburn, et al., 2014), identifying correlations between performance and personalities (Felder 2002) (Felder 2005) (Kiss, Kun, Kapitány, and Erdei, 2014) (Furnham and Crump, 2015a) (Furnham and Crump, 2015b), and identifying correlations between professions and personalities (MH, 1977) (Freeman 2009) (Jafrani et al., 2017) (Rosati, 1993) (Capretz, 2002) (Cohen et al, 2013) (Loffredo et al, 2008) (Moutafi et al, 2007) (Emanuel, 2013).

Other personality models exist. Arguably among the best known is the Five Factor or OCEAN model. After analyzing correlations among 35 personality traits, Tupes and Christal identified five personality factors: Surgency (Extraversion), Agreeableness, Dependability (Conscientiousness), Emotional Stability (versus Neuroticism), and Culture (Openness) (Tupes and Christal, 1992) (John and Srivastava, 1999). Goldberg referred to these factors as “The Big Five” (Goldberg 1990). McCrae and Costa interpreted the factor Culture as Openness to experience (McCrae and Costa, 1987). Ruston and Irwing rearranged the first letters of the factors to form the mnemonic OCEAN (Rushton and Irwing, 2008).

The National Aeronautics and Space Administration (NASA) defines Team Risk as the risk associated with a decrease in performance and behavioral health due to inadequacy of a team’s cooperation, coordination, communication, and psychosocial adaption (DeChurch et al., 2015). “Currently, NASA has no formalized process to compose mission teams from a scientific perspective, but this is an identified need for future exploration missions” (Landon 2015). Anania asserts that “crew compatibility on an interpersonal level will need to be a major factor in order to ensure optimal communication and coordination within the team” (Anania et al., 2017). Brandley and Herbert applied MBTI to their study of Information Systems teams and found that a team’s personality type composition is partially related to performance (Bradley and Hebert, 1997).

Personality compatibility may play a significant role in link formation in real-world social networks. Back asserted that “personality differences influence social relationships”, but noted that social network research rarely considers the effects of individual personalities (Back 2015). With that in mind, the algorithms described here both make use of inferred personality types for the people represented by the network’s nodes and base the probability of a link forming between two nodes on the compatibility of the personality types associated with those nodes.

Table 4 is such a personality compatibility table for the MBTI personality types. The rows and columns are the 16 MBTI personality types. Each entry in the table is the probability of a link forming in a social network between two nodes if the nodes’ associated personality types are those of the entry’s row and column. Note that the table is symmetric, i.e., the two entries for two personality types are the same regardless of which type is on the row and the column. Table 4 was constructed from the personality type descriptions in (Keirsey 1998); the process for doing so is detailed in Appendix 1.

Homophily and heterophily can be modeled as likelihoods of link formation among personality types. In Table 4, values on the diagonal of the table represent a level of homophily because cells on the diagonal are the intersections of rows and columns identifying the same personality type. Values in the cells other than the diagonal represent some level of heterophily because those cells are at the intersections of rows and columns that identify different personality types.

MBTI was used in this work because of its wide application in practical settings. However, the social network generation algorithms presented later do not depend on any particular personality compatibility table or even on a particular personality model. Any personality model that satisfies the following two criteria could be used: (1) it has personality types that are discrete, or could be discretized; and (2) it provides, or enable the development of, a quantitative measure of the relative compatibility of different personality types that can be encoded as a personality compatibility table. In fact, a different personality table was used in the early stages of this work, with similar results to those reported here.

Social network analysis research requires real-world social networks to use as input data. First developed in the early 1980s, UCINet is a social network analysis application that calculates a variety of network metrics (Freeman 1988). UCINet includes functions for discovering cohesive subgroups in a network (Borgatti et al., 2014). An associated archive of social networks, represented as adjacency matrices, is maintained in the UCINet format (Freeman, 2009) (Freeman, 2016).

Table 5 lists the real-world social networks used in this research as source data; they are from the UCINet archive. In all but one of the networks, the nodes of the network correspond to individual people and the links to a relationship of some kind between them. (The exception is the Schwimmer Taro Exchange Network., where the nodes correspond to Orokaiva households within the Papaun village Sivepe and the links represent the mutual exchange of gifts, such as cooked taro (Schwimmer, 1979) (Schwimmer 1973).)

The real-world social networks used in this research include both symmetric and asymmetric and both unweighted and weighted networks. The new network synthesis algorithms to be described produce symmetric unweighted networks. Therefore the real-world networks were converted to symmetric and unweighted if necessary before being used as exemplar networks. The conversions were done in the obvious ways; if an asymmetric network had directed link(s) in either or both directions between two nodes, the converted network had an undirected link between those nodes, and if a weighted network had a weighted link of any weight between two nodes, the converted network had an unweighted link between the nodes.

Current trends in social network analysis include social networks developed from massive data sets captured from online social media and communities, such as FaceBook, Twitter, and Wikipedia; (Mislove et al., 2007), (Crandall et al., 2008), (Kwak et al., 2010), (Catanese et al., 2011), (Yang and Leskovec, 2015), and (Grandjean 2016) are examples. Common interests in careers, pastimes, politics, popular culture, and societal trends serve as the motivation for joining groups within these online communities, so personality types may be one of many factors determining how links form in real-world social networks. However, according to Krebs social networks expressed as connections via Facebook and LinkedIn can be misleading because site members may try to connect with as many people as possible and others acquiesce to the creation of apparent links with no real connection. “Two people might show to be connected but they really are not – one person was too embarrassed to turn down a ‘friend request’ from a total stranger. These ‘false positives’ tend to pollute the data of these social networking services” (Krebs 2008).

Generating synthetic social networks that are more realistic than random graphs, such as those generated by the classic Erdős-Rényi G(n, p) algorithm, also known as the random graph model (Erdős 1959) (Erdos and Rényi, 1960), requires attention to the properties of social networks that distinguish them from random graphs. Since 1960, several social network generation models have been developed. A selection of existing social network generation models that consider or exploit various structural characteristics of networks includes the following; each will be described following the list:

In random graphs, the nodes’ degrees tend to follow a Poisson distribution (Bollobás 1998). This can be unrealistic; real-world networks’ node degree distributions are more often non-Poisson and heavy-tailed. The configuration model extends the random graph model to address that inconsistency (Bender and Canfield, 1978) (Bollobás 1980) (Molloy and Reed, 1995) (Molloy and Reed, 1998) (Newman et al., 2001) (Milo et al., 2003) (Newman 2003) (Viger and Latapy, 2005). In the configuration model, network generation is initialized with both the number of nodes n and a specific degree sequence K = {k₁, k₂, …, k_n}, where k_i is the degree of node v_i. The degree sequence K may be random variates drawn from a suitable distribution (checked to ensure that Σ k_i is even), or more simply, the actual degree sequence of a real-world network serving as an exemplar of the class of networks to be generated. Given n nodes a degree sequence K, links are added by randomly connecting each node v_i to k_i other nodes, with each link uniformly possible. This produces networks with a realistic degree distribution, but if a single exemplar is used for multiple synthetic networks, all the generated networks will have the same node degrees.

The exponential random graph models (ERGM), also known as the p* model, assembles a network from subgraph structures, such as stars, triangles, paths, and cycle patterns (Wasserman and Pattison, 1996) (Snijders 2002) (Robins et al., 2007). Holland and Leinhardt developed an exponential family of probability distributions for directed graphs, which derived from empirical observations of stars (nodes with multiple links), isolates (nodes without links), and their triad census (the sixteen possible configurations of a directed triad) (Holland and Leinhardt, 1977) (Holland and Leinhardt, 1981). Frank and Strauss developed a family of distributions for directed and undirected Markov graphs wherein there existed dependence among the links (Frank and Strauss, 1986). Snijders applied Monte Carlo Markov Chains to estimate network metrics such dyads, undirected and directed two paths, and directed and undirected triangles (Snijders 2002). Hunter distinguished between ERGM and p* by associating the maximum pseudo-likelihood estimation (Wasserman and Pattison, 1996) with p* and maximum likelihood estimation (Geyer and Thompson, 1992) with ERGM (Hunter 2007).

Among the existing methods, the stochastic block model (SBM) may have the most similarity to the new methods developed in this work, and so we describe it in a bit more detail. The SBM can be used to generate networks and to detect communities within large scale networks (Holland et al., 1983) (Anderson et al., 1992) (Faust and Wasserman, 1992) (Newman and Girvan, 2004) (Bickel and Chen, 2009) (Fortunato 2010) (Decelle et al., 2011) (Abbe 2017). The set of actors or agents involved is first partitioned into B communities or clusters known as blocks. This partitioning is often done by manual analysis, based on observation or data. Tightly interacting groups of actors are placed into the same group. A B × B preference matrix W specifies the probabilities of link formation both within and between the blocks (Nowicki and Snijders, 2001). The probabilities may be provided manually or by automated analysis of the source data. The on-diagonal entries in W specify the probabilities of links forming between nodes in the same block, whereas the off-diagonal entries in W specify the probabilities of links forming between nodes in different blocks. If the on-diagonal probabilities are higher than the off-diagonal probabilities, then the intra-block link density will be higher than the inter-block link density; such a network is known as assortative. Conversely, if the off-diagonal probabilities are higher than the on-diagonal probabilities, then the resulting network will have a higher inter-block link density; such as network is known as disassortative. In an SBM implementation, the number of nodes in each block may be stored in an integer vector with B entries. If the blocks are assumed to be disjoint, the sum of the vector’s entries is the total number of nodes in the network. To generate a synthetic network, the probability of link formation in W between each pair of nodes is used to stochastically determine if a link is formed between those nodes.

The small world model starts with a one dimensional regular ring lattice where each node has links to its k nearest neighbors (Watts and Strogatz, 1998) (Strogatz 2001). Several iterations of random rewiring produce a network with a desired density. For each node, rewiring involves stochastically determining whether an existing link is deleted or a new link is formed between the current node and another randomly selected node.

The preferential attachment model starts with a small set of nodes and then adds nodes and links in an iterative process based upon the connectivity of the nodes (Barabási and Albert, 1999) (Barabási, 2003). The number of nodes in the initial set determines the maximum degree for new nodes. In each iteration, or “time step”, a new node is added to the network and then links from the new node to the existing nodes are stochastically added, up to the maximum degree. The process depends upon the existing nodes’ current connectivity, which is calculated as k = m · (t / t_i)^1/2 where m is the node’s current degree, t is the current iteration (or time step), and t_i is the initial time step when the node was added. The probability of link being added from the new node to existing node i is k_i / (Σ k) where k_i is the connectivity of node i and (Σ k) is the sum of the connectivity of the other existing nodes. New nodes, and links from them to existing nodes, are iteratively added until the network has the desired number of nodes. This process produces a scale-free network.

The Popularity Similarity model bases the probability of link formation on hyperbolic distances between nodes (Papadopoulos et al., 2012). In this model, the network grows as nodes are added at successive time steps. Older (earlier added) nodes tend to be popular because they have had more time to connect to other nodes. To model similarity, new nodes are randomly placed on a circle; a node’s birth time determines the radial coordinate r_t = ln(t). Two nodes, with polar coordinates (r_s, θ_s) and (r_t, θ_t), have an approximate hyperbolic distance x_st = r_s + r_t + ln(θ_st/2) = ln(stθ_st/2) where s and t are the nodes’ respective birth times. This hyperbolic distance serves as a convenient metric that represents both radial popularity and angular similarity.

The Chung-Lu model uses an exemplar degree sequence to set the probability of link formation between two nodes. For a pair of nodes, the link formation probability is proportional to the product of corresponding degrees in the sequence (Chung and Lu, 2002).

The degree correlation dK series model uses probability distributions for node degree correlations for subnetworks of size d to generate networks. A generated 0 K-graph reproduces the average node degree of an exemplar network. A 1 K-graph reproduces the degree distribution of an exemplar network. A 2 K-graph reproduces the joint degree distribution and a 3 K-graph reproduces similar interconnectivity among triangles as an exemplar network (Mahadevan et al., 2006).

The Block two-level Erdős-Rényi model introduces community structures by generating a set of independent networks and then randomly linking nodes among the communities (Seshadhri et al., 2012). Typically, algorithms that implement this model include input parameters for nodes and density and the algorithm returns a network with the number of links based upon the density.

(Staudt et al., 2017) describes the replication of complex networks (ReCon) model that generates scalable synthetic social networks based on an exemplar network. An objective of ReCon is to generate networks of different sizes, up to 32 times larger than the exemplar. The ReCon algorithm first detects communities in the exemplar network using the parallel Louvain method. It then generates a working graph as a disjoint union of x copies of the exemplar, where x is a scaling factor. For each detected community in the working graph, the algorithm preserves the degree distribution and rewires the intra-community links through random edge switching. After rewiring the intra-community links, it rewires the inter-community links and generates links among the copies of the network (Staudt et al., 2017). In this work a realistic replica of an exemplar social network was defined as a network that has similar metric values as the exemplar. The metrics that were compared to the exemplar included sparsity, i.e. number of links versus number of nodes, the degree distribution’s Gini coefficient, maximum degree, average clustering coefficient, diameter, number of connected components, and number of communities. ReCon produces replicas that are realistic under this definition because it preserves the exemplar’s community structure and node degrees.

In contrast to the algorithms reported later, with only one exception the existing social network generation methods do not use any actual or inferred attributes of the persons represented by the nodes to determine or influence the generation of links between the nodes. The exception is the stochastic block model, which uses a group attribute associated with each node to determine the probability of link formation with other nodes within the same group. None of the prior methods use personality type or compatibility, as is done in this work, to produce synthetic social networks. This idea was hinted at in (Staudt et al., 2017), which described a potential application of synthetic social networks as showing interactions that are “determined by implicit psychological and social rules”, but those “rules” were not used to generate networks.

The desirable features of a synthetic social network generation algorithm include parsimony (i.e., few parameters), speed of execution, and network realism. Realism, in particular, is a very important characteristic of synthesized social networks. Realism in social networks has been defined in terms of network structural features, dynamics, and evolution (Staudt 2017). The similarity, or lack thereof, of metric values between a synthetic network and a real network is understood as a measure of realism. (Chakrabarti et al., 2004) (Leskovec et al., 2010). A quantitative assessment of realism is central to the current work.

Figure 2 shows the algorithms and dataflow in the network synthesis process. That process starts with a real-world social network T, which serves as an exemplar of the class of social networks to be generated. (In this work, T is any of the fourteen real-world networks listed in Table 5). Network T is input to three different algorithms. The two algorithms developed in this work, Probability Search (PS) and Configuration-Degree Matching (CDM), each construct an assignment A of personality types to the nodes of T. Both employ heuristic methods to find A, albeit in completely different ways. The resulting personality type assignment A is then input to a network generator algorithm (GNAC), which generates a set of synthetic social networks (denoted P for the PS algorithm or M for the CDM algorithm), using the personalities in A and the compatibility information in personality compatibility table C.

The challenge is to find a personality type assignment A which, when the GNAC algorithm is used with personality compatibility table C, will produce realistic synthetic social networks. A personality type assignment that produces realistic synthetic social networks will be referred to in this context as effective.

Real-world exemplar network T is also be input to a standard network generation algorithm, the Configuration Model (CM). CM also generates a set F of synthetic social networks based only on the structure of T and without using and personality compatibility information.

The three sets of synthetic networks are then input to a process that calculates the network metrics listed in Table 2 and compares them to the exemplar T.

Synthetic social networks are generated by an algorithm that considers personality compatibility by using a personality compatibility table C (e.g., Table 4) and a personality assignment A to the nodes of the network. The network generation algorithm is denoted the G(n, A, C) (GNAC) algorithm, where n is the number of nodes, A is an assignment of personality types to the n nodes, and C is a personality compatibility table that includes the personality types in A. Given an assignment A of personality types to nodes and a compatibility table C, as many synthetic social networks as needed can be generated using the GNAC algorithm. They will likely differ due to the randomness in the algorithm, but they will be related in that all were produced using the same assignment A and compatibility table C.

The GNAC algorithm first determines the degree sequence of an exemplar network T. The degree sequence is used to initialize a link budget for each of the nodes in the synthetic network. The algorithm then randomly selects two triads of nodes in the synthetic network as candidates for triangles. The personality types assigned to the triads’ nodes by A and the personality compatibility table C are used to find the probability of link formation between each pair of nodes in the triads, and the probabilities for each triad are summed. The triad with the larger sum is then converted into a triangle by connecting all unlinked pairs in the triad and the link budgets of any newly linked nodes are decremented. This procedure repeats until the number of triangles in the synthetic network is the same as the number of triangles in the exemplar network.

In the following pseudocode, T is an exemplar network, A is a personality assignment, C is a compatibility table, S = (V, E) is a synthetic network and u and v are nodes in the network. At three points in the gnac function links may be added to the network. The addlink function, shown first, is called by the gnac function; it adds a link between nodes u and v if they are not already connected.

The overall computational complexity of the GNAC algorithm is O(n⁴). To see this, consider first the function addlink; it does not loop over the nodes or edges and so is O(1). The GNAC algorithm itself begins with some housekeeping that includes an O(n log n) sort of the nodes’ degree sequence (line 3). The first main loop (lines 7–25) is over the triangles of T. A network with n nodes may have as many as C(n, 3) triangles; C(n, 3) = n!/(3!(n – 3)!) ∈ O(n³). Within that loop, the do while loop (lines 8–11) may execute an arbitrary number of times, but on average is O(1). The set membership tests (line 19) are O(1) if the edge set is stored in a suitable data structure, such as an adjacency matrix. All of the remaining computation in the first main loop is also O(1). Thus the second main loop is O(n³). Finding all the potential dyads the first time (line 27) is O(n²). There are potentially as many as C(n, 2) such dyads; C(n, 2) = n!/(2!(n – 2)!) ∈ O(n²). The second main loop (lines 28–33) iterates once for each of the O(n²) dyads, and in each iteration it again finds all potential dyads O(n²), thus the second main loop is O(n⁴). The third and final main loop iterates at most once for each node, i.e., O(n) iterations. Each iteration scans O(n) nodes to find those with remaining link budgets, so the third main loop is O(n²). Thus the complexity of the GNAC algorithm as a whole is O(n⁴).

The Probability Search (PS) algorithm is based on the idea that the probability of a given social network being generated algorithm from a given personality type assignment A and personality compatibility table C can be calculated. That calculation can be done in either of two ways that differ in whether or not nodes are assumed to be distinguishable. For this work, it is assumed that the nodes are uniquely identified and are thus always distinguishable from each other. This assumption is appropriate for many social network applications, where nodes correspond to specific known persons. The implication of uniquely identified nodes is that a different network, with the same connection structure (i.e., isomorphic in graph theory terminology) but connecting different specific nodes, would not be equivalent as a social network because different people would be connected.

The probability of the network will be calculated using a simple extension of the Erdős-Rényi G(n, p) algorithm. In the G(n, p) algorithm the probability of link formation p is constant for the entire network. In the PS algorithm’s probability calculation the constant p is instead replaced for each pair of nodes with the probability of a link forming between those nodes, given a personality type assignment A and a personality compatibility table C. Let p(i, j) be the probability given in C of a link being present between two nodes i and j for the personality types assigned to nodes i and j by A. The probability of a network G = (V, E) being formed is therefore given by Eq. (1); we will call this the network probability.

Given an exemplar network T and a compatibility table C, the network probability can be used to search for the personality type assignment A that has the highest probability P(T) of producing the exemplar. Once found, that personality type assignment can be used by the GNAC algorithm to generate synthetic networks that are likely to be similar to the exemplar.

In theory, the optimum personality type assignment, i.e., the assignment that has the highest possible probability of producing the given exemplar network T, could be found by methodically generating every possible personality type assignment and calculating P(T) for each one. Unfortunately, this is not practical for any but the smallest networks. If a personality type scheme has k different personality types and exemplar network T has n nodes, there are kⁿ different possible type assignments. For the MBTI personality type scheme using in this work k = 16, thus for even the smallest real-world exemplar network used in this research, the Robins Australian Bank network with 11 nodes, there are 16¹¹ ≈ 1.76 · 10¹³ possible personality type assignments. Calculating P(T) for that many assignments at the rate of one per millisecond would require over 500 years. Thus an exhaustive search is impractical.

Instead, the new Probability Search (PS) algorithm performs a heuristic search through the space of possible personality type assignments. After generating an initial personality type assignment randomly, it iteratively changes the assignment, one node at a time. To do so, it uses node probability, a quantity similar to network probability, but calculated for a single node. Given a network G, a personality compatibility table C, and a personality type assignment A, the node probability of a single node i in G is given by Eq. (2).

At each iteration, the PS algorithm selects a node i, either the node with the smallest node probability P(i) under the current personality type assignment (with probability 0.95), or a random node (with probability 0.05). It then calculates P(i) for that node i for each of the possible personality types, holding the network structure and other nodes’ personality types fixed. The personality type that gives the highest node probability P(i) is assigned to node i. This process repeats until the overall network probability improvement achieved in an iteration is less than a threshold, subject to a required minimum number of iterations. Finally, to prevent non-productive repetitive changes to the same node’s personality type, when a node’s personality type is changed it is added to a list of nodes excluded from adjustment in the next iteration and remains in that list for a certain number of iterations. The improvement threshold, the minimum number of iterations, and the number of iterations a node remains on the excluded list are all parameters to the algorithm. (For the results reported here, the values 0.0001, n · k · 1000, and ⌈n / 10⌉ respectively were used for those parameters. Those values were found empirically.)

In the following pseudocode for the PS algorithm, V is a set of nodes, E is a set of links, C is a personality compatibility table, A is a personality type assignment, n is the number of nodes, and k is the number of different personality types. In the pseudocode, two subroutines (functions) precede the main logic of the PS algorithm.

The overall computational complexity of the PS algorithm is O(n³). To see this, consider first the functions vprob and gprob; vprob loops once over the n elements of V (lines 3–9), and so is O(n), whereas gprob has two nested loops (lines 3–11), each over the n elements of V, and so is O(n²). The main body of PS begins with some O(1) housekeeping (lines 2–9) and an O(n²) call to gprob. The main loop (lines 10–49) executes O(n) times. Within the main loop, the search for the lowest probability vertex (lines 15–23) begins with an O(n) call to vprob (line 16), then loops over the available nodes O(n) times; within that loop is an O(n) call to vprob, thus this portion of the main loop is O(n²). Next the search for the highest probability personality type (lines 25–35) calls gprob once, and then enters a while loop that iterates k times, each time calling gprob, which is O(n²). Because k is a constant and not a function of n, this portion of the loop is O(n²). The last part of the while loop includes two operations on the excluded list (lines 37 and 39) which can be accomplished in amortized O(1) time if implemented as a deque, and another O(n²) call to gprob. Thus the complexity of the main loop, and PS algorithm as a whole, is O(n³).

The Compatibility-Degree Matching (CDM) algorithm first determine the degree sequence of a given exemplar network T. It then generates a personality type assignment A in accordance with an empirical distribution based the frequency of each personality type in the U. S. population (Table 3). The columns of personality compatibility table C provides an overall compatibility of each personality type. The CDM then orders the personality types by overall compatibility and the nodes of the exemplar network T by decreasing order of degree. Using those two orderings, the CDM personality types to the nodes so that the personality types with the highest overall compatibility are assigned to the nodes with the highest degree. In the pseudocode, personality type assignment A is a vector of size n.

The overall computational complexity of the CDM algorithm is O(n log n). The n nodes are sorted (line 3), which is O(n log n). The summing of the compatibility values (lines 4–6) is O(k²), where k is the number of personality types, and the sort of the sums (line 7) is O(k log k), but for most networks k < < n. The assignment of personality types (lines 8–10) is O(n) and the sort of the assigned types (line 11) is O(n log n). The final loop (lines 12–14) is O(n). Thus the complexity of the CDM algorithm as a whole is O(n log n).

In order to assess the effectiveness of the personality-based algorithms (PS and CDM), they were compared to an existing network generative model that was not personality-based. Two were considered for the role of baseline. Because of its abstract representation of popularity, the Popularity Similarity model (Papadopoulos et al., 2012), as implemented in the R package NetHypGeom (Alanis-Lobato et al., 2016), was examined. However, perhaps because of that model’s orientation to large scale-free networks, the implementation sets certain bounds on its input parameters; in particular, the average degree must be ≥2 and the scaling exponent must be ≥2 and ≤ 3. Of the fourteen real-world networks to be used as exemplars in this work (see Table 5), only one (Zachary Karate Club) had values for these metrics that satisfied both of these bounds; the other thirteen had an average degree < 2, a scaling exponent either < 2 or > 3, or both. Thus the exemplars to be used did not seem well suited to the capabilities of the Popularity Similarity model, or its implementation.

On the other hand, the Configuration Model (CM), which was described earlier, produces synthetic networks based upon the degree sequence of an exemplar network, and does not consider personality. Because it is based on degree sequence, is usable with the exemplars. Furthermore, it is considered by some to be a standard basis of comparison: “Following the works of Barabási et al., the degree distribution has become accepted as the most fundamental network characteristic… [I]t has become a standard to compare network quantities to a null-model where the degrees of the network (the degree sequence) is fixed and everything else random” (Barrenas et al., 2009).

The two new algorithms for finding effective personality type assignments (PS and CDM), as well as the network generator GNAC algorithm, were implemented in the R language. R is an open-source programming language and environment with powerful and extensive features for data analysis, data visualization, and statistical computing (R Core Team 2016). R also includes a full range of general purpose programming language features, including control structures, mathematical operations, and file input/output. It should be noted that for medium and large networks, the network probability value P(G) computed by the PS algorithm can become quite small, as it is the product of n(n – 1)/2 probabilities, all of which are ≤1. A computer implementation of P(G) meant to handle medium and large networks must take care to avoid numeric underflow. In our implementation, we used the R gmp (GNU Multiple Precision) package for arbitrary precision arithmetic.

As already mentioned, CM is an existing algorithm for generating synthetic social networks. A prior implementation of CM in the R language is available in the R igraph package, which is a collection of R functions for network analysis and visualization (Csárdi and Nepusz, 2013). In that package function sample_degseq produces networks using CM. That function was used for this work without modification.

Because R is an interpreted language, R programs often execute more slowly than comparable programs written in a compiled language. In addition, the two algorithms to find effective personality type assignments (PS and CDM) both involve numerous iterations, especially the PS algorithm. Consequently, the algorithms’ run times during testing and analysis were sometimes quite lengthy. To keep the executions manageable, the programs were run on supercomputers provided and supported by the Alabama Supercomputer Authority. Typical run times for the two algorithms were highly dependent on the number of nodes in the exemplar graph; for the PS algorithm the run times ranged from a few minutes for the smallest real-world network (Robins Australian Bank, 11 nodes) to several hours for the largest real-world network (Lazega Law Firm, 71 nodes). Although the algorithms’ implementation code was not parallelized, scripts were used to initialize and initiate multiple instances of the programs to execute concurrently.

The PS and CDM algorithms differ from most prior work on generating synthetic social network in a significant way. Most prior algorithms do not consider the attributes of the nodes, or of the people or entities the nodes represent, when adding links; instead they are based on retaining or replicating some of the structural characteristics of the exemplar network in the synthetic networks. For example, CM is given a degree sequence, which may be the actual degree sequence of the real-world network serving as an exemplar (Newman 2003). In contrast, the PS and CDM algorithms use the attributes of the nodes, in particular the personality types assigned to them, as the primary driver of their calculations.

From the quantitative results, it is evident that both the PS and the CDM algorithms, which use personality compatibility information, generate more realistic synthetic social networks than the CM algorithm, which does not. The PS and CDM algorithms are quite similar in terms of realism. However, the CDM algorithm is much more computationally efficient, requiring substantially shorter execution times for large networks. Either PS or CDM could be used with small to medium exemplars; for exemplars with more than ~ 40 nodes, PS becomes impractical, at least in its current implementation.

Close examination of the results in Table 6 show that the PS and CDM both performed worst on the Schwimer Taro Exchange exemplar. It is unlikely to be a coincidence that in that network only among the fourteen exemplars the nodes correspond not to individual people, but to households, which is intuitively not as good a fit with personality-based algorithms. Thus PS and CDM, or future enhancements of them, should be considered when the nodes correspond to individual people and personality compatibility is expected to have a significant effect on whether two people have the relationship that a link represents.

In this work all of the social networks were treated as symmetric and unweighted. As an obvious generalization, applying these methods to asymmetric and/or weighted social networks is an opportunity for future work. Because multiple metrics generated in a single experiment are analyzed, the multiple comparison problem may be present, and suitable methods to compensate for it could be employed. Finally, the assumption in the PS algorithm that the nodes can be distinguished could be changed to consider networks that connect the same personality types in the same way, as opposed to connecting the same nodes in the same way, as equivalent. (This is analogous to color isomorphism in graph theory terms.) Changing the assumption would change the formula for calculating the network probability P(G).

Finally, according to (Aiello et al., 2012), there has been considerable research aimed at predicting the overall evolution of social networks, but very few attempts to predict future connections of individual people within such networks. Within an organization, managers may wish to create a new project team or work group. The methods developed in this work could be applied to simulating the potential formation of social networks within the team or group, given a set of personality types and a compatibility table. We speculate that generating synthetic social networks using individuals’ personality types has the potential to lead to a predictive or semi-predictive capability to anticipate the future social network that could emerge in a team or group. If such a capability was sufficiently reliable, managers could use its predictions when considering personnel assignments. This idea requires of careful validation, perhaps by comparing predicted social networks to actual social networks for existing teams or groups.