**Network Segmentation Based on Homogeneity**

# Problem Description

To segment a network according to homogeneity is to segment a network into sub-networks such that each sub-network is formed by nodes with similar attributes. See the following two examples of segmenting a sensor network and a 2D mesh.

Fig.1 Segmenting a sensor network based on the homogeneity of sensor readings. The color of each node indicates the value of the sensor reading. Fig.2 Segmenting a 2D mesh according to the homogeneity of local nodes density. (a) is the original mesh. (b) is the partitioning result based on spectal partitioning, (c) is the netowrk segmentation result.(a) and (b) are taken for courtesy from M. NewmanWe propose a new graph partitioning method for community discovery that combines both attribute information (i.e., the sensor measurement information in the nodes of the graph) and the topological structural information of the graph in the sense that we focus on the attribute information in developing the partitioning solution but at the same time watching the graph cut size to avoid any potential over-segmentation. This way, we are able to develop an optimal solution to the community discovery in such sensor networks. The specific idea in this new approach is to conceptualize the homogeneity in developing the graph partitioning method.

# Resource download

**Methodology description download**

This pdf file contians problem formulation, theoretical proofs, and various experimental results.