key: cord-0060582-kgn9p43z
authors: Samonenko, Ilya; Voznesenskaya, Tamara; Yavorskiy, Rostislav
title: How the Minimal Degree of a Social Graph Affects the Efficiency of an Organization
date: 2021-02-20
journal: Recent Trends in Analysis of Images, Social Networks and Texts
DOI: 10.1007/978-3-030-71214-3_15
sha: f1982eb536cbac32f80d7b5dad1836bc8fc7c917
doc_id: 60582
cord_uid: kgn9p43z

This paper continues our research on how the communication structure of an organization affects its efficacy. We assume that the organization consists of several types of professionals (researchers, engineers, testers etc.) and each project team must include at least one professional of each type. We study a dynamic simulation model, which defines a team creation process, based on the social graph of the organization. The greatest lower bound of the average utilization rate is found under (is based on) the assumption that each node in the social graph has a degree of at least [Formula: see text] . This theoretical result is supported by a series of computer simulations.

The topic of team modelling and performance analysis generates regular interest among researchers, see [5] . Analysis and improvement of employee utilization are widely covered in business administration literature, but papers, which use mathematical modelling for that are quite rare. In our previous paper [8] a literature overview of team modelling approaches and the utilization rate analysis was presented. An important insight of the literature study is that a meaningful modelling approach should take into account the skill profiles of the employees, their roles and communications.

A simple example which we have in mind is a group of researchers and engineers working at a rather big academic research center, see [7] . Some of the group members know each other, and these connections are used to form project teams when information about a new grant, a call for papers or other opportunity occurs. We use a simulation modeling approach to study the process of information distribution and team forming in response to that new opportunity. We are especially interested in the efficiency of such organization as the average number of well-formed project teams per opportunity. The same model type could also be applied to other cases, where the project teams are self-organized by the employees on the basis of existing social connections.

An average utilization rate of a group is the proportion of specialists involved in projects to the total number of specialists. We are interested in studying this important aspect of the organization performance. In particular, we want to analyze how the minimal degree of the social graph affects the utilization rate of an organization.

The horizontal connection between members of an organization is an important factor. Many researchers consider different characteristics of these connections in team modeling. For example, team sports performance analysis (see e.g. [4] ) pay attention not only to social graph topology but also to the complexity of interpersonal interactions of players. In [2] , a model of multi-agent team performance for the RoboCup Rescue domain is considered. The authors simulated the behavior of small teams of 2-3 robots, working on civilian rescue tasks to study the synergy among them. The different characteristics of intra-team interaction are considered in [3] . Computer simulation to support the systematic design of organization was also studied in [1] .

The paper is organized as follows. In Sect. 2, we provide formal definitions, then different restrictions and conditions on the model are considered. The main part of the paper consists of theorems in Sect. 3, which formalize some properties of the model with respect to these conditions. Section 4 provides the simulation analysis and Sect. 4 concludes.

We consider here a simplified version of a more general simulation model developed for analysis of team performance in a research centre [7, 8] . Input parameters of the model are the following: -P = A B is a finite set of group members (employees, professionals) of two categories: type A (researchers) and type B (engineers), where |A| = n 1 and |B| = n 2 ; -G ⊆ P × P is an undirected social graph of an organization, so G(p 1 , p 2 ) indicates that employees p 1 , p 2 ∈ P have established relations enough to invite each other to a new project.

In general, we assume that for a successful project one needs a team, which includes k 1 researchers and k 2 engineers. The focus of this paper is where k 1 = k 2 = 1.

The simulation process is executed in the following way (it is described in detail in [6] ):

-Team initialization. When an employee decides to initiate a new project, a new team is created, which consists of only the initiator.

-Invitation process. Each team member sends an invitation to join his project to each of his contacts in the social graph of the organization. An employee always accepts the invitation if their competencies are needed for this team and they have time available. Each employee can only join one project. -Team finalization:

• Success. A project team is formed where k 1 researchers and k 2 engineers have joined it. • Failure. It may be that the combined skills of members are not sufficient and there is no one else available with the required skill set. Then the team formation process is stopped and members who already joined become available again.

We assume that the receiver of an invitation makes the decision and responds immediately (from a practical point of view this means that all the communications are fast and decisions are instant in comparison to the duration of projects). The simulation process sequentially runs the rules above for all the agents (employees) until the formation of new teams is impossible.

For a given graph G, let w denote the number of employees who are finally involved in a project team. Then the utilization rate is defined as a fraction:

Note that the team building is a non-deterministic process, so value ρ(G) will differ for different simulations, see detailed [6] .

We assume that each project needs exactly one researcher and one engineer.

The upper bound for ρ(G) is rather straightforward. Since any project needs exactly one researcher and one engineer, if n 1 = n 2 then at least |n 1 − n 2 | employees will always be idle. So,

This upper bound is the lowest, see [8] for the detailed proof. Next we prove the lower bound for the utilization rate for the model defined above under the assumption that each node in the social graph has a degree greater than δ. This generalizes our previous results, see Fig. 1 and [8] , which correspond to case δ = 1.

For k 1 = k 2 = 1 connections between employees of the same category do not affect the team formation. So, we assume that the social graph is bipartite. Fig. 1 . Social graph with the worst utilization rate, see [8] Theorem 1 (lower bound for the utilization rate). Let G = (A B, E) denote a bipartite social graph of an organization, |A| = n 1 , |B| = n 2 . Assume that each node in G has a degree equal to or greater than δ, then:

and this lower bound is the greatest.

Proof. Under the assumption of the two skills model, every project team consists of exactly two members, a researcher (from A) and an engineer (from B). First, we explicitly construct a social graph and a simulation run for which

Then, it will be shown that for any graph and simulation, ρ(G) cannot be lower. Consider Fig. 2 . It is a bipartite graph with n 1 nodes of type A and n 2 nodes of type B. The nodes are divided into four groups:

-group I consists of (n 2 − δ) nodes of type B; -group II consists of δ nodes of type A; -group III consists of δ nodes of type B; -group IV consists of (n 1 − δ) nodes of type A.

Each node from group I is linked to each node from group II. Similarly, each node from group II is linked to each node from group III, each node from group III is linked to each node from group IV. It is clear that the degree of nodes in groups I and IV are equal to δ, and the degree of nodes in groups II and III are equal n 2 and n 1 correspondingly, which is greater that δ.

For this structure of the social graph, it may happen that nodes from groups II and III form δ pairs and all the remaining nodes will be idle. For this run the utilization rate equals

Let's now show that this is the strict lower bound and any simulation makes at least δ teams. This could be shown by induction on δ. Case δ = 1 is trivial, Fig. 2 . The worst case social graph of a two-skilled organization: group I consists of (n2 − δ) nodes, groups II and III contain δ nodes, group IV consists of (n1 − δ) nodes since each node has at least one connection, at least one pair will be formed. Consider any bipartite graph such that each degree of every node is equal or greater than δ. Take an arbitrary node of any type, and any one from it's connections to form a team. In the subgraph, all the nodes have a degree δ − 1 or greater, so at least δ − 1 teams will be formed according to the induction hypothesis.

From a practical point of view this result looks quite frustrating. For example, assume n 1 = n 2 = 15 and δ = 3, this has a balanced group of 30 workers in which everyone is linked to at least three potential collaborators. According to the reason above it may happen that only 6 teams are formed and the remaining 18 members are forced to be idle. The group utilization rate for this example is ρ = 40%, which is far from intuitively expected ρ = 100%, which is potentially reachable when the social graph is more dense.

One of the useful implications is the fact that measures aimed at establishing more connections in a team do not always guarantee a substantial growth of the average utilization rate.

In this section we describe in detail the simulation process because its parameters strongly influence the observed results.

We implement function GetRandomGraph(n, δ) that creates a random bipartite graph in the following way. First, for given n and δ graph G = (A B, ∅) with n vertices and no edges is created, where A stands for a set of vertices corresponding to researchers, B is the set of vertices corresponding to engineers, and |A| = |B| = n/2. Then, each vertex a ∈ A is connected to δ different vertices from B with equal probability, and vice versa. Each vertex b ∈ B is connected to δ different vertices from A with equal probability. It may happen that some edges are created twice, so we remove the duplicates. Such a procedure guarantees that every researcher is connected with no less than δ engineers, and every engineer is connected with no less than δ researchers. As a result we have a random bipartite graph

with the degree of each vertex not less than δ.

The first series of experiments was aimed at finding dependencies between guaranteed minimal node degree δ and utilization rate ρ(GetRandom Graph(n, δ)) for different values of n = 20, 30, 40 and 50, see Fig. 3 . The second series of experiments was aimed at finding dependencies between the size of graph n and the utilization rate ρ (GetRandomGraph(n, δ) ) for different values of δ = 1, 2, . . . , 6, see Fig. 4 .

For each fixed value of n and δ, T = 500, graphs G i (n, δ) where i = 1, . . . , T , were generated randomly. Then, for each graph G i (n, δ) we have run N = 200 simulations ρ sj (G i (n, δ)), j = 1, . . . , N, and compute the following characteristics. (G i (n, δ) ).

The virtual design team: a computer simulation framework for studying organizational aspects of concurrent design

Weighted synergy graphs for effective team formation with heterogeneous ad hoc agents

Correlations in bipartite collaboration networks

Team sports performance analysed through the lens of social network theory: implications for research and practice

Team Effectiveness in Complex Organizations: Cross-disciplinary Perspectives and Approaches

The influence of self-organizing teams on the structure of the social graph

Modeling self-organizing teams in a research environment

Effect of social graph structure on the utilization rate in a flat organization

As a result, we found the following.1. Typically, random simulation results are far better than the worst possible bound established, according to our theorem. For δ = 1, the average value of utilization rate ρ(n, δ) is around 80%, while the theoretical minimum is below 10% for n > 20, see blue and dashed graphs on Fig. 3 and Fig. 4 . 2. Average ρ(n, δ) increases with δ, which complies with the intuition that adding more connections increases utilization, see Fig. 3 . The graphs show that for δ = 3 (each employee knows at least three colleagues from the other category), the average utilization is almost certainly greater than 80%. 3. For a fixed δ ∈ {3, 4, 5, 6} average the utilization ρ(n, δ) is rather stable and does not depend on n, see Fig. 4 . 4. At δ ≥ 3, the average value is about 90%, and with the increase of δ, does not grow significantly. Therefore, for a high probability of getting on a team, it is enough for an engineer or researcher to have three contacts. This means a simple practical recommendation: build a team so that each specialist has at least three contacts with specialists with other skills.

In this paper, an analysis of the utilization rate for an organization with a guaranteed minimum degree of a bipartite social graph has been provided. We generalized our previous results [8] for the greatest lower bound of the utilization rate. Simulation analysis gave us some ideas and possible directions for future research. In particular, we plan to consider different distributions of node degrees for this graph generation algorithm. Besides, it is interesting to study the generalization of this model with a larger number of skills and the evolving topology of social graphs.