Teng Zhang^{1}, Pan Sun^{2}, Lin Shi^{1}, Queenie Chan^{3}, and Defeng Wang^{4}

Random partition is the cornerstone of atlas-free brain network analysis which can be used for multiscale analysis and comparison of cohorts with different brain sizes. The random parcels should be uniform to avoid additional variability from different parcel areas. In this study a uniform random partition of meshed surface is proposed considering geodesic distances and parcel areas. The partition results showed that proposed method can partition surface into any given number of parcels with similar areas. With repeating network analysis using proposed uniform parcels, results showed low intra-subject variations of global network measures.

Proposed uniform random parcellation is depending on a graph clustering method using geodesic distances and parcel areas as shown in figure 1. Because shape of gray matter and white matter interface is very unconvex and complex, Euclidean distance is not appropriate for surface partition. For example, Euclidean distance between two points located at opposite side of sulcus is much shorter than the actual length of shortest curve connecting them. Therefore, geodesic distance, which is the length of shortest path between nodes, were employed in this study.

The gray matter and white matter interface surface was first constructed using FreeSurfer pipeline^{4}. And then a weighted graph was constructed from the triangle mesh of interface surface by converting mesh vertices as graph nodes, and building edges between nodes within same triangles. Edge weights were set as spatial distances between vertices, and node weights were assigned as 1/3 sum of areas of triangles containing corresponding vertices.

To avoid sometimes poor partition from random initiation, a modified *k*-means++ algorithm was used for choosing initial seeds (i.e. cluster centers)^{5}. The first seed was chosen randomly from all nodes followed by calculating geodesic distances between all the other nodes and the first seed using Dijkstra’s algorithm^{6}. Then the next seed was chosen from nodes with top 5% largest geodesic distances to existing seeds, in order to ensure that new selected seed was always far away from existing seeds. The seeds except the first one were chosen according to a probability distribution with probability proportional to squared geodesic distances. Each time after choosing a new seed, the Dijkstra’s algorithm was recalled from new seed to update geodesic distances.

Similar to *k*-means clustering and simple linear iterative clustering^{7}, the proposed graph clustering method is a two-step iterative optimization with an assignment step and an update step. In the assignment step, a cluster with minimal area and at least one unassigned neighbor node was first extracted. Then unassigned neighbor node with minimal tentative geodesic distance to the cluster center was allocated to this cluster. In the update step, a new cluster center was found using gradient descent search to minimize sum of geodesic distances between all cluster members and the new cluster center. The gradient descent search compared sums of geodesics distances from the old cluster center and its neighbors, and moved to the next node with minimal sum, and so on. The assignment-update loop was terminated until all seeds remained unchanged or iteration number reached a predefined limit.

The gray matter and white matter interface surface was segmented into 250, 500, 1000, and 2000 parcels. Figure 2 and figure 3 shows the partition result and the histogram of parcel areas with 1,000 parcels respectively. Table 1 shows the coefficients of variation (CV), i.e. ratio of standard deviation to the mean, of parcel areas with different numbers of parcels.

Structural networks were constructed from 1,000 parcels using counts of connecting fibers as edge weights by DSI-studio 100 times^{8}. Global network measures including global efficiency and mean strength were calculated as shown in figure 3. The CV of global efficiency and mean strength are 2.11% and 0.12% respectively.

1. de Reus MA, van den Heuvel MP. The parcellation-based connectome: Limitations and extensions. Neuroimage. 2013;80:397-404. doi:10.1016/j.neuroimage.2013.03.053.

2. Tymofiyeva O, Ziv E, Barkovich AJ, Hess CP, Xu D. Brain without anatomy: Construction and comparison of fully network-driven structural MRI connectomes. Hayasaka S, ed. PLoS One. 2014;9(5):e96196. doi:10.1371/journal.pone.0096196.

3. Tymofiyeva O, Hess CP, Ziv E, et al. Towards the “baby connectome”: Mapping the structural connectivity of the newborn brain. Ben-Jacob E, ed. PLoS One. 2012;7(2):e31029. doi:10.1371/journal.pone.0031029.

4. Fischl B. FreeSurfer. Neuroimage. 2012;62(2):774-781. doi:10.1016/j.neuroimage.2012.01.021.

5. Taghi M, Howard S. k-means++: the advantages of careful seeding. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery; 2007:1242. doi:10.1137/1.9781611973402.

6. Dijkstra EW, W. E. A note on two problems in connexion with graphs. Numer Math. 1959;1(1):269-271. doi:10.1007/BF01386390.

7. Achanta R, Shaji A, Smith K, Lucchi A, Fua P, SuÌˆsstrunk S. SLIC Superpixels Compared to State-of-the-Art Superpixel Methods. IEEE Trans Pattern Anal Mach Intell. 2012;34(11):2274-2282. doi:10.1109/TPAMI.2012.120.

8. Yeh F-C, Verstynen TD, Wang Y, Fernández-Miranda JC, Tseng W-YI. Deterministic Diffusion Fiber Tracking Improved by Quantitative Anisotropy. PLoS One. 2013;8(11):e80713. doi:10.1371/journal.pone.0080713.