# Human Clustering Based on Graph Embedding and Space Functions of Trajectory Stay Points on Campus
## 2 Methodology
### Feature Representation  
Graph embedding algorithms are effective in transforming high-dimensional, sparse graphs into low-dimensional and continuous feature-vector spaces. Such an algorithm encodes the relationships among nodes into feature vectors, among which distances reflect proximities in the network. These algorithms utilize biased random walks and enable us to generate low-dimensional, fix-length feature vectors that represent individuals' interaction patterns within these space functions. With representation learning, the structure and relationships in the graph can be captured for various machine learning tasks in the vector space. Node2 Vec [27] achieves this by employing the graph's biased random walk strategy, which can effectively balance local and global structural information to generate node embeddings. The algorithm aims to learn representations for nodes so that nodes sharing similar network neighborhoods are closer together in the embedding vector space. In order to capture the complex relationships in human networks, Node2 Vec can generate feature representations of individuals within a network. It can capture not only spatio-temporal activity patterns of human individuals but also the structural connections among them. [PERSON] et al. (2014) used DeepWalk [28], a random walk-based method, to learn latent representations of social networks, which improved performance in community detection and link prediction tasks. [PERSON] (2024) introduced Node2 Vector [29], combining network analysis and neural networks to improve the quality of node embeddings for machine learning tasks.  
The algorithm is primarily based on two concepts: network neighborhoods and node similarity. A network neighborhood of a node is a fixed-size subset of neighbors of the given node. Node similarity is defined by comparing the network neighborhoods of nodes. In Node2 Vec, node embeddings are obtained by generating random walk-based sequences on the graph, which can be viewed as a method of sampling nodes from the graph. The core idea is to perform multiple random walks on the nodes to capture all neighboring nodes and generate meaningful embeddings. Two transition probabilities parameters are involved (\(p\) and \(q\)), which represent whether the random walk is biased towards Breadth-First Search (BFS) or Depth-First Search (DFS). BFS sequences typically explore neighboring nodes, while DFS is more prone to exploring nodes distant from the current node. In this study, typical combinations of parameters \(\mathrm{p}\) and \(\mathrm{q}\) were explored to adjust the random walk's inclination towards depth-first search (DFS) or breadth-first search (BFS) [27] and further optimize subsequent clustering and analysis of the resulting embeddings. Figure 3 shows the diagrams of BFS and DFS, and Equations (1), (2), and (3) are the formulas for the Node2 Vec sampling strategies.  
Given the source node (\(u\)) and the sampling length (\(L\)), assuming the current sampling node is node \(c_{i-1}\), the probability of the next sampling node being \(x\) is expressed as follows:  
\[P(c_{i}=x\mid c_{i-1}=u)=\begin{cases}\frac{\pi_{ux}}{Z}&\text{if}(u,x)\in E\\ 0&\text{otherwise}\end{cases} \tag{1}\]  
Taking Figure 2 as an example, if the current node is node \(u\) and the previous step was at node \(t\), then the transition probability is \(\pi_{\text{ux}}\). In this work, \(\mathrm{w}_{\text{ux}}\) is set to 1.  
\[\pi_{\text{ux}}=\alpha_{\text{pq}}(\mathrm{t},\mathrm{x})\cdot\mathrm{w}_{ \text{ux}} \tag{2}\]  
and  
\[\alpha_{pq}(t,x)=\begin{cases}\frac{1}{p}&if\ d_{tx}=0\\ 1&if\ d_{tx}=1\\ \frac{1}{q}&if\ d_{tx}=2\end{cases} \tag{3}\]  
Each node in the human network is represented by a 16-dimensional feature vector from Node2 Vec, which can achieve a balance between preserving sufficient information and computational efficiency [27]. Figure 4 illustrates examples of 9 vectors generated for nodes in the human network.  
Figure 3: Transition probabilities in Node2 Vec: BFS and DFS preferences.