This paper considers a society partitioned into ordered groups and examines the stable networks that players form. Four utility functions combining benefits and costs from network connections are introduced. The utilities significantly influence players’ incentives in the formation of links and, consequently, network structure. Costs are affected by a given partition in one of two different ways: (i) a link’s cost depends only on the distance between the types of groups players belong to (the larger the distance, the larger the cost), and (ii) cost is not affected only by distance but also by the composition of a player’s neighborhood (the more members of a group the player has in her neighborhood, the less the average cost of a link is within this group). We observe that a player may prefer linking with players in other groups with a higher average link cost and reject linking with players in her own group when the second type of costs is applied. This never occurs with the first type of costs. We examine when specific network structures (i.e., empty network, complete network, minimal and minimally connected network, inner star and inner complete network) are pairwise stable with different utility functions. Stable networks regarding a special class of partitions with a unique large group and many individual players are also examined.