本研究將網路結構式分群演算法（Structural Clustering Algorithm for Networks, SCAN）延伸至無向加權圖。SCAN 根據節點的局部鄰域結構進行分群，並將節點分類為核心、樞紐與離群點。現有的精確加速演算法與動態維護方法多半針對未加權圖設計，在未加權圖的設定中，每個共同鄰居對結構相似度的貢獻相同。然而，在加權圖中，邊權重可能包含圖拓撲本身無法呈現的量化資訊。若忽略邊權重，可能造成有用量化資訊的流失。所提出的架構根據共同鄰居及其邊權重，定義節點間的加權結構相似度。在靜態圖的情境下，本研究首先提出基準演算法 WSCAN，以計算加權結構相似度並產生分群結果。為減少不必要的加權共同鄰居計算，進一步提出結合邊定向與安全剪枝的索引式方法。安全剪枝規則由正規化權重下的上界推導而得。上述安全剪枝不會改變相似度判定，因此索引式方法可產生與基準演算法相同的相似鄰居列表與分群結果。在動態圖的情境下，本研究提出局部維護方法 LOCAL，以避免每個更新批次後重新計算圖中所有相鄰節點對的相似度。LOCAL 只重新計算可能受影響的節點對，並維護與完整靜態重算相同的相似鄰居列表。此外，靜態架構也延伸至直接使用原始權重的情境，並推導基於 Q 值的上界，使演算法無須進行權重正規化即可執行安全且精確的剪枝。實驗結果顯示，所提出的方法可在維持精確性的同時減少不必要的相似度計算。索引式方法在所有測試門檻下皆可降低鄰域交集工作量，且在較具選擇性的門檻下，其查詢時間短於靜態基準方法。在主要動態實驗比較中，LOCAL 的執行時間明顯少於採用全域重算的方法。批次大小實驗進一步顯示，其優勢在小型與中型批次下最為明顯。此外，一致性檢查未發現相似鄰居列表或分群結果不一致的情形。

We propose a weighted extension of the Structural Clustering Algorithm for Networks (SCAN) for undirected graphs. SCAN compares local neighborhood structures to identify clusters and vertex roles, including cores, hubs, and outliers [17]. Several existing exact acceleration and dynamic maintenance methods focus on unweighted graphs, where each common neighbor contributes equally to structural similarity. In weighted graphs, edge weights may contain quantitative information that is not represented by graph topology alone. Ignoring edge weights may result in the loss of useful quantitative information. The proposed framework defines weighted structural similarity based on common neighbors and their edge weights. For static graphs, we introduce WSCAN, a baseline weighted extension of SCAN. An index-based variant uses edge orientation and safe pruning to reduce unnecessary weighted common-neighbor computations. The pruning rule is derived from upper bounds based on normalized weights. The index-based method preserves the same similarity lists and clustering results as the baseline. For dynamic graphs, we introduce a local maintenance method called LOCAL. Instead of recomputing all similarities after each update batch, LOCAL recomputes only the affected vertex pairs. The maintained similarity state is identical to that obtained by full static recomputation. The static framework is further extended from normalized weights to raw weights. A Q-based upper bound enables safe and exact pruning without weight normalization. Experimental results show that the proposed methods reduce repeated similarity computations while preserving exactness. The index-based method reduces intersection workload at all tested thresholds and is faster than the static baseline at more selective thresholds. In the main dynamic comparison, LOCAL is faster than methods based on global recomputation. The batch-size experiment further shows that its advantage is strongest for small and moderate batches. The consistency checks identify no mismatches in the similarity lists or clustering result.

[1] Alain Barrat, Marc Barthélemy, Romualdo Pastor-Satorras, and Alessandro Vespignani. The Architecture of Complex Weighted Networks. Proceedings of the National Academy of Sciences, 101(11):3747–3752, 2004.
[2] Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008, 2008.
[3] Lijun Chang, Wei Li, Lu Qin, Wenjie Zhang, and Shiyu Yang. pSCAN: Fast and Exact Structural Graph Clustering. IEEE Transactions on Knowledge and Data Engineering, 29(2):387–401, 2017.
[4] Yulin Che, Shixuan Sun, and Qiong Luo. Parallelizing Pruning-based Graph Structural Clustering. In Proceedings of the 47th International Conference on Parallel Processing, pages 77:1–77:10, 2018.
[5] Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, pages 226–231. AAAI Press, 1996.
[6] Santo Fortunato. Community Detection in Graphs. Physics Reports, 486(3–5):75–174, 2010.
[7] Sung-Su Lim, Seung-Woo Ryu, Sejeong Kwon, Kyomin Jung, and Jae-Gil Lee. LinkSCAN*: Overlapping Community Detection Using the Link-Space Transformation. In Proceedings of the 30th IEEE International Conference on Data Engineering, pages 292–303, 2014.
[8] Lingkai Meng, Long Yuan, Zi Chen, Xuemin Lin, and Shiyu Yang. Index-based Structural Clustering on Directed Graphs. In Proceedings of the 38th IEEE International Conference on Data Engineering, pages 2831–2844, 2022.
[9] M. E. J. Newman. Analysis of Weighted Networks. Physical Review E, 70(5):056131, 2004.
[10] M. E. J. Newman and M. Girvan. Finding and Evaluating Community Structure in Networks. Physical Review E, 69(2):026113, 2004.
[11] Jukka-Pekka Onnela, Jari Saramäki, János Kertész, and Kimmo Kaski. Intensity and Coherence of Motifs in Weighted Complex Networks. Physical Review E, 71(6):065103, 2005.
[12] Ryan A. Rossi and Nesreen K. Ahmed. The Network Data Repository with Interactive Graph Analytics and Visualization. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1), 2015.
[13] Satu Elisa Schaeffer. Graph Clustering. Computer Science Review, 1(1):27–64, 2007.
[14] Kalyani Selvarajah, Amangel Bhullar, Ziad Kobti, and Mehdi Kargar. WSCAN-TFP: Weighted SCAN Clustering Algorithm for Team Formation Problem in Social Networks. In Proceedings of the Thirty-First International Florida Artificial Intelligence Research Society Conference, pages 209–212, 2018.
[15] Hiroaki Shiokawa, Yasuhiro Fujiwara, and Makoto Onizuka. SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs. Proceedings of the VLDB Endowment, 8(11):1178–1189, 2015.
[16] Dong Wen, Lu Qin, Ying Zhang, Lijun Chang, and Xuemin Lin. Efficient Structural Graph Clustering: An Index-Based Approach. The VLDB Journal, 28(3):377–399, 2019.
[17] Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas A. J. Schweiger. SCAN: A Structural Clustering Algorithm for Networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 824–833, 2007.
[18] Fangyuan Zhang and Sibo Wang. Effective Indexing for Dynamic Structural Graph Clustering. Proceedings of the VLDB Endowment, 15(11):2908–2920, 2022.
[19] Weizhong Zhao, Gang Chen, and Xiaowei Xu. AnySCAN: An Efficient Anytime Framework with Active Learning for Large-Scale Network Clustering. In Proceedings of the 2017 IEEE International Conference on Data Mining, pages 665–674, 2017.