Dynamic intimate contact social networks and epidemic interventions Page: 10
The following text was automatically extracted from the image on this page using optical character recognition software:
10 C.D. Corley, A.R. Mikler, D.J. Cook and K. Singh
Algorithm 2 optimizes matching on the bipartite graph in polynomial time (E log V)
with the following constraints : every node has at least one connected edge and
the resulting graph's cardinality is optimized so that a minimal number of edges
remain to be connected (see Figs. 2 and 3).
subset Gm subset Gf
Unidrected Bipartite Graph G
Figure 2 Initial graph G
Figure 3 Optimized graph, with minimal remaining set cardinality
Let G be an undirected bipartite graph, that contains two bipartition subsets,
GM and GF. The vertices in each subset have a pre-assigned degree associated
with it; specifically, a random, power-law distributed number which is the maxi-
mum possible number of edges connected that vertex. For the constraint that each
node is to have at least one edge the following bounds must hold N(GIf) > Gm
or N(Gm) > Gf. Note, the distribution of male and female vertices is not sig-
nificant if the previously mentioned constraint holds. Edges are attached to the
graph as follows: in vertex order of each subset, one edge is attached from a male
vertice to a randomly chosen female vertice in the opposing subset, link attachment
is determined by preferential attachment and cosine similarity of each vertices's de-
mographic vector. A threshold is set to arbitrarily choose a vertex in the opposite
subset when a large number of vertices have been chosen but no edge has been
placed. The simulator's threshold is set to 200 attempts before an arbitrary ver-
tex in the opposite subset is chosen for edge placement. When a node randomly
chooses a node in the opposite subset and it stochastically fails to create a link,
the model will draw a random node 200 times before arbitrarily choosing a vertex
for edge placement; the number 200 is arbitrarily chosen and sensitivity on this
threshold is left for future work. Next, an edge is attached from a female vertex to
a male vertex, also determined by preferential attachment and cosine similarity of
each vertices's demographic vector. The edges are added one per subset until one
of the subsets maximum cardinality is reached. The exact algorithm is described
in greater detail in Alg. 2. A sample network generated by our simulator that
contains 100 nodes, 50 females and 50 males is displayed in Figure 4.
Here’s what’s next.
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Corley, Courtney; Mikler, Armin R.; Cook, Diane J., 1963- & Singh, Karan P. Dynamic intimate contact social networks and epidemic interventions, article, 2008; [Geneva, Switzerland]. (digital.library.unt.edu/ark:/67531/metadc132993/m1/10/: accessed July 28, 2017), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT College of Engineering.