Basically, what I have is a list of cities, people, and whether or not those people have been to each city. I have no data on how frequently a person visits a city, the order they visit cities in, or time between visits. Just whether or not they were there (technically speaking, a 0 does not guarantee they weren't there, just that they weren't detected there. For simplicity, I think it might be best to not worry about this at this point).
What I'm trying to do is use this information with community detection algorithms to see if I can identify how cities are clustered together without using any kind of geographic data. If you think about it, at the highest level, you might expect some kind of regional clustering of cities at the scale of a state or country. Then if there is some kind of regional clustering, then within each of those regions, the next level might be clusters of major urban areas made up of lots of cities. And of course, there might be solitary rural cities. My expectation is that people are more likely to visit areas that are more convenient to travel to, whether it's for work, recreation, shopping, etc, and that this can be used to identify community structure.
I look at this data and can see it being visualized as a graph in several different ways. It could easily be viewed as a hypergraph, or as a multigraph, or as a bipartite graph. For some of the stuff I've tried, I'm collapsing it into a complete weighted graph. What I've tried so far is creating a pairwise adjacency matrix of the cities with a single similarity or distance metric for each pair of cities (in my case, I've been using the Jaccard index). I have then been using this adjacency matrix with community detection algorithms in iGraph that try to maximize modularity. To a degree, this works. I can see the regional clustering that makes sense based on geographic features. However, trying to perform the same process within these regions does not seem to work as well. I also notice that individuals that occur at more cities tend to make things worse, and the community detection process works better when they are removed. However, from a randomized sampling standpoint, arbitrarily removing these people is terrible. I'm also not sure if these community detection algorithms are really intended to be used with complete graphs. On top of that, I don't understand modularity well enough yet to know if its limitations are coming into play.
Another interesting approach I've seen but haven't tried is using a simulated annealing algorithm with the data in a bipartite graph to maximize modularity.
I guess my question is, what approaches would you recommend for community detection with this type of data, and where there is the potential for hierarchical structure?