Print

Print


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

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)<http://epubs.siam.org/doi/abs/10.1137/0206036>,
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.
>

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