What you describe in your example is not only a network of relationships, but a network of "flows" between all groups.
Like you suggested in a) (and as Jeromy said as well) your graphic will likely be a visualization of one group (or node) linked to other groups. Most of my knowledge of this subject is visualizing flows between geographic spaces, but many of the same issues still apply.
I think this paper does a good job summarizing visualization techniques in regards to mapping flows.
From spatial interaction data to spatial interaction information? Geovisualisation and spatial structures of migration from the 2001 UK census
by: Alasdair Rae
Computers, Environment and Urban Systems, Vol. 33, No. 3. (May 2009), pp. 161-178. (PDF here)
Typically visualizing flows in geographic space has three main problems. One is that it is difficult to distinguish between in-flows and out-flows. The second is that long lines tend to dominate the graphic. Three is that over-lapping or too many flows tend to make the graphic look very noisy.
The second problem may be solved by however you organize the nodes on your graphic (like Jeromy suggested cluster nodes together with strong relationships). It may also be easier to use small multiple graphs to distinguish between in-flows, out-flows, and reciprocal flows (i.e. map your nodes to a specific space and then have seperate graphics displaying in-flows, out-flows). I have not seen any examples of flows in networks like you describe, so I do not know if the self-organizing graphics have the problem of over-lapping lines.
If you have experience programming in Python you may want to check out the NetworkX package. (The Gephi package Ars linked to looks pretty awesome as well).
This is similar in nature to questions brought up on the GIS stackexchange forum, and here is a question with answers you may be interested in.