## 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

Subject:

Re: Algorithmic Puzzler

From:

Date:

Sat, 17 Aug 2013 08:32:40 +0200

Content-Type:

text/plain

Parts/Attachments:

 text/plain (57 lines)
 ```***** To join INSNA, visit http://www.insna.org ***** <<<-------- Edmund Chattoe-Brown-------->>> > ***** To join INSNA, visit http://www.insna.org ***** > > Dear All, > > I am trying to construct (by simulation) a network with a given > percentage of two way ties (the rest one way). Each social actor has a > limit on the number of ties they can support. (Call this "capacity".) > The programme works by doing all the two way ties first and then > "filling up" any unused capacity with one way ties.   Are the capacities equal for all nodes?   Are the capacities just upper bounds or they have to be realized   by a constructed graph?   I think you have to distinguish between input and output capacities.   Your problem can be related to "graphic(al) sequences"   http://en.wikipedia.org/wiki/Degree_(graph_theory)   http://mathworld.wolfram.com/GraphicSequence.html   http://www.combinatorics.org/Volume_17/PDF/v17i1r66.pdf   You can also consider the idea of generating some graph (may be   with multiple links and loops) that realizes your conditions   (look at the approach used for preferential attachment in   http://vlado.fmf.uni-lj.si/vlado/papers/rndgen.pdf )   and correct it afterward using the Z2И transformation:        u--v u v          / ---> | /|         / |/ |        w--t w t     replace subgraph       (u:v), (v:w), (w:t)     with       (u:w), (v:w), (v:t)   (see the rule P3 on page 3 in    http://vlado.fmf.uni-lj.si/vlado/papers/indcla.pdf )   adapted for directed graphs and loops (you get a set of possible   transformations, you can also impose some restrictions such us   (u:w) is not a link). These transformations preserve the degrees of   nodes and the graph connectivity.   Vlado -- Vladimir Batagelj, University of Ljubljana, FMF, Department of Mathematics   Jadranska 19, 1000 Ljubljana, Slovenia http://vlado.fmf.uni-lj.si _____________________________________________________________________ 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.```