Build clusters from connections (virus propagation)
I always feel odd reviewing code like this, because there is no API. You should really pull out the clustering code into it's own method, with a nice signature, something like:

IEnumerable&lt;IReadOnlyCollection&lt;string&gt;&gt; Cluster(IEnumerable&lt;Person&gt; people);


This will make it reusable (and so testable).

You ask "Am I doing here something potentially dangerous or excessive with the collections?". I'm not entirely sure what you mean... but I think no. Collections are efficient, and it's hard to do anything dangerous in C# by accident. If anything, you should probably be using more powerful collections.

Tuples

What is Tuple&lt;string, List&lt;string&gt;&gt;? What are Item1 and Item2? Give it a meaningful type, with meaningful member names!

public class Person
{
    public Person(string name, IReadOnlyCollection&lt;string&gt; places)
    {
        Name = name;
        Places = places;
    }

    public string Name { get; }
    public IReadOnlyCollection&lt;string&gt; Places { get; }
}


Complexity

Never been much good at complexity... but here's an attempt at answering your second question. Take it with spoonful of salt. Hopefully someone will poke holes in it promptly.

First you need to identify the parameters you care about. Let's say n for the number of people and 'b' number of places. You iterate over pairs of people, which gives you n^2 (just to enumerate the pairs).

Inside that loop you are looking for an intersection between 2 sets of up to b elements, which can be no better than O(b) (that's the case where the hashes turn out perfectly, assuming Intersect converts one of the lists to a HashSet internally). cluster1.AddRange(cluster2.Where(x =&gt; !cluster1.Contains(x))) is O(b^2). You ought instead be using HashSets from the outset, which will get the inner working down to something more like O(b) again (i.e. HashSet&lt;T&gt;.UnionWith(HashSet&lt;T&gt;) is kind of just about linear most of the time). ... but then that matching can only happen n times... so it's a separate concern.

Then there is the outer most loop... which I don't want to think about... but in the worst case it will be run n times, giving you a worst-case complexity of O(n*n*n*b + n*n*b*b), or just about O(n*n*n*b) if you use HashSets.

I can't think how the space complexity of your code could be anything other than the input space complexity of O(b + n).

Technically, your printing out at the end has third order time complexity: O(m*k*k) in number of clusters m, and number of places per cluster k. Consider using a StringBuilder or string.Join instead of Aggregate and repeated concatenation (that will make it O(m*k)).

Disjoint Sets

Any problem like this I would solve with disjoint sets, and even a poor implementation should get you O(n*b) time-complexity (max tree-depth is O(n)) on this problem.

The basic idea is that you maintain a table pointers which describe a set of trees, each tree being an independent (disjoint) set. You can follow the pointers from any member of a set to the root member, and by assigning the parent of one root node to the root of another you join the two sets together. You can throw an implementation together in no time, with very little code.

Some very unscientific benchmarking suggests that a somewhat untested disjoint sets implementation I just threw together is a couple of orders of magnitude faster than your implementation (using HashSets and with reduced Pair count, as suggested in Paparazzo's answer) on randomly generated problems. Your implementation is taking over 10seconds on my machine to solve a problem with b=4000, which the disjoint sets solve in a few milliseconds. The disjoint set version seems to be linear in n*b (easier to scale than just b in random problems); yours is taking a while for larger problems larger than n*b=5000, and I wouldn't wish to comment on the experimental time-complexity with these few (noisy) results.

A gist of the disjoint sets implementation and cluster method is provided so that people can find juicy bugs in it: 1 bug fixed so far (2018-06-26)