Print

Print


*****  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.