## 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: power-sets in networks

From:

Date:

Thu, 18 Oct 2012 11:18:42 +0200

Content-Type:

text/plain

Parts/Attachments:

 text/plain (88 lines)
 ```***** To join INSNA, visit http://www.insna.org ***** Dear Vlado, maybe a rough example can clarify what I would like to achieve... take a first network A, with nodes={a,b,c} and no links, then possible power-sets are of course: a b c ab ac bc abc take a second network B, with nodes={a,b,c} and one link={a<->b}, then possible solutions to my problem, let's call them "conflict-free" sets, are: a b c ac bc is this sufficient to answer your question? Thanks for your time! Best, Simo 2012/10/18 Vladimir Batagelj <[log in to unmask]>: > > <<<-------- Simone Gabbriellini-------->>> >> ***** To join INSNA, visit http://www.insna.org ***** >> >> Dear List, >> >> I have a rather unusual question regarding power-sets in networks. I >> would like to find all the power-sets in a network under the >> constraint that the nodes are not linked together, i.e. the >> calculation should happen only for set of nodes that are not neighbors >> of each others. >> >> the point is that finding all power-sets and then dropping the ones >> where nodes are linked is computationally very costly, and I am in >> looking for some other strategy... > > It should be relatively easy to write a procedure to generate / list > all the required sets. But there can be many - I guess that their > number is growing exponentially with the size of network. Therefore > this approach is feasible only for very small networks (some tens - > may be up to 30 nodes). > > There is another question - should the sets be maximal in the sense > that they are not contained in any other set that satisfies the > constraints. In other words are the sets that contain a single > node also solutions ? > > Vlado > -- > Vladimir Batagelj, University of Ljubljana, FMF, Department of Mathematics > Jadranska 19, 1000 Ljubljana, Slovenia > http://vlado.fmf.uni-lj.si > -- Simone Gabbriellini, PhD PostDoc@DISI, University of Bologna mobile: +39 340 39 75 626 email: [log in to unmask] home: www.digitaldust.it DigitalBrains srl Amministratore mobile: +39 340 39 75 626 email: [log in to unmask] home: www.digitalbrains.it _____________________________________________________________________ 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.```