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