Print

Print


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

Dear Adam,

thanks for the suggestion, I will check that paper an let you know if
I manage to find an efficient solution!

Best,
Simone

2012/10/15 Adam Obeng <[log in to unmask]>:
> Dear Simone,
>
> This is an interesting problem!
>
> Assuming this is a simple graph, if you invert the presence of all of the
> ties, the problem is of finding all the connected power sets, which might be
> a more common phrasing of the problem (and so easier to search for).
>
> The most obvious way I can think of doing that is to find all maximal
> cliques of the graph in question, then find the power sets of those.
> Unfortunately, the first step still takes exponential time if I understand
> correctly.
>
> You may be able to modify the algorithm from Tsukiyama et al. (1977), which
> during its operation seems to recurse through (some? all?) of the subsets of
> the maximal cliques.
>
> Best wishes,
>
> Adam
>
>
> --
>
> Ph. D. Candidate
>
> Department of Sociology, Columbia University
>
> adamobeng.com
>
>
> On 15 Oct 2012 04:33, "Simone Gabbriellini"
> <[log in to unmask]> wrote:
>>
>> *****  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...
>>
>> does someone happen to have some suggestions or advices?
>>
>> Best regards,
>> Simone
>>
>> --
>> 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.



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