LISTSERV mailing list manager LISTSERV 16.0

Help for SOCNET Archives


SOCNET Archives

SOCNET Archives


SOCNET@LISTS.UFL.EDU


View:

Message:

[

First

|

Previous

|

Next

|

Last

]

By Topic:

[

First

|

Previous

|

Next

|

Last

]

By Author:

[

First

|

Previous

|

Next

|

Last

]

Font:

Proportional Font

LISTSERV Archives

LISTSERV Archives

SOCNET Home

SOCNET Home

SOCNET  August 2013

SOCNET August 2013

Subject:

Algorithmic Puzzler Follow Up

From:

Edmund Chattoe-Brown <[log in to unmask]>

Reply-To:

Edmund Chattoe-Brown <[log in to unmask]>

Date:

Wed, 28 Aug 2013 23:55:26 -0700

Content-Type:

text/plain

Parts/Attachments:

Parts/Attachments

text/plain (70 lines)

*****  To join INSNA, visit http://www.insna.org  *****

Dear All,

Many thanks to Vladimir Batagelj, James Moody, Simone Gabbriellini and
Jen Badham for helpful thoughts and suggestions.

What I was trying to do was create a network with a mixture of mutual
and non-mutual ties where each agent had a capacity constraint and
"obvious" constraints on tie structure also applied (you can't be
friends with yourself or with someone else more than once). The problem
was that, sometimes, the algorithm could not create a workable network
in the sense that some agents "wanted" mutual ties but nobody had the
capacity to provide them so the program crashed.

Interestingly, the consensus definitely seemed to be that I would need
some rewiring algorithm to do this (and thus there was only "one pass"
solution proposed which is what I was hoping for.)

This solution was not to allow agents to choose tie partners randomly
from any who have capacity but to compel them to choose only from those
with the _most_ capacity. I suspect this would work by preventing a
situation towards the end of network construction where (for example)
there was capacity for 4 ties but it was "no use" because it was all on
one agent. I was also a bit nervous that removing nearly all the
randomness from network creation _might_ create artefacts of structure
that could affect the simulation outcomes. (My version keeps the maximum
randomness compatible with the constraints.)

However, after getting the bugs out, I decided that my algorithm "nearly
works" and that a non algorithmic solution was needed. What the code now
does is prints a warning when a mutual tie can't be made and makes a one
way tie instead. The user can thus decide whether to throw away runs
with warnings or (if there are very few warnings) just keep the run and
assume negligible difference to the outcome.

This isn't elegant but experiments suggest that a) the system barely
fails except when the percentage of mutual ties is so high it is
probably empirically implausible, b) the system barely fails for
"sensible sized" networks. (Debugging on small case must be done with
caution!)

I think the issue is basically that for small tie capacity (and small
numbers of agents) "laws of large numbers" fail. If the chance of a
mutual tie is 70% per tie then, in practice, agents "far too often" end
up with all mutual ties (and thus "use up" their capacity) and/or ties
end up very unequally distributed across agents (so towards the end you
can have all spare ties on one agent). With many more agents and less
"extreme" chances of mutual ties, the distribution of ties and the
actual number of mutual links per agent end up far more workable.

I have the code (in NetLogo) for this if anyone wants it ...

Thanks again,

Edmund

-- 
  Edmund Chattoe-Brown (Department of Sociology, University of
  Leicester, UK)
  [log in to unmask]

-- 
http://www.fastmail.fm - A fast, anti-spam email service.

_____________________________________________________________________
SOCNET is a service of INSNA, the professional association for social
network researchers (http://www.insna.org). To unsubscribe, send
an email message to [log in to unmask] containing the line
UNSUBSCRIBE SOCNET in the body of the message.

Top of Message | Previ