Isotropic homogeneity does not hold in urban areas. Street networks exert a great influence on human mobility. As a result, city structure is largely shaped by this network, especially the streets that carry a higher volume of traffic. In practice, small areas along network edges often need to be grouped into regions for management purposes. This work formalizes the extension to the P-regions problem that takes the network as the underlying constraint and proposes a heuristic-based approach to solve the problem to near optimality. The network is subdivided into aggregator edges that attract regions and separator regions that divide areas apart. Two types of regions emerge in the region formation process: regions that grow along a certain network edge (network regions) and regions that grow from areas that are far away from all the network edges (planar regions). The heuristic solution effectively uses pre-computed spatial contiguity and distance matrices. The global objective function consists of the original heterogeneity factor and the discounted network proximity factor. This approach is elaborated with both a simulated and a real-world dataset. The regionalization results help design, study, and service regions that explicitly consider the network configuration with flexible parameter controls.