Schelling (1969, 1971a,b, 1978) considered a simple model with individual agents who only care about the types of people living in their own local neighborhood. The spatial structure was represented by a one- or two-dimensional lattice. Schelling showed that an integrated society will generally unravel into a rather segregated one even though no individual agent strictly prefers this. We make a first step to generalize the spatial proximity model to a proximity model of segregation. That is, we examine models with individual agents who interact ’locally’ in a range of network structures with topological properties that are different from those of regular lattices. Assuming mild preferences about with whom they interact, we study best-response dynamics in random and regular non-directed graphs as well as in small-world and scale-free networks. Our main result is that the system attains levels of segregation that are in line with those reached in the lattice-based spatial proximity model. In other words, mild proximity preferences can explain segregation not just in regular spatial networks but also in more general social networks. Furthermore, segregation levels do not dramatically vary across different network structures. That is, Schelling’s original results seem to be robust also to the structural properties of the network.