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