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