Source-linked AI summary
A Novel Information Workflow for Structural Behavioural Analysis in Dynamic Attributed Graphs
Gatadi Ashwitha, K. Swarupa Rani
TL;DR
Existing approaches do not provide a unified way to predict missing links, update graphs, and detect communities dynamically in attributed graphs. The paper proposes inc-LPCDAG, using Dynamic CSADW for link prediction and Dynamic I-Louvain for community detection; experiments report effective dynamic structural and behavioural analysis, with significant improvement over inc-AGGMMR. The workflow remains scoped for future extension to weighted attributed graphs and multiple node types.
Problem
Existing methods do not jointly handle attributed graphs, missing-link prediction, graph updates, and dynamic community detection.
Method
inc-LPCDAG combines Dynamic CSADW for Phase-I link prediction with Dynamic I-Louvain for Phase-II community detection.
Results
The proposed approach performs significantly better than inc-AGGMMR, with p-value 0.01142 and Cohen’s d 5.8291.
Takeaways & Limitations
The workflow supports analysing structural and behavioural processes in dynamic attributed graphs through enhanced link prediction and community-detection phases.
Takeaways & Limitations
Future work is needed to extend the workflow to weighted attributed graphs and different node types and attributes.
Abstract
from arXiv · showhide
Social systems play a vital role through interactions around shared interests and the maintenance of relationships, which are part of society. These can be represented as networks, and their analysis plays a crucial role in dynamic environments, which can be achieved through link prediction and community detection tasks. Several link prediction approaches estimate new relationships, such as suggesting friends on social media. On the other hand, a social faction is a group of connected people that reveals the internal structure of the social system and can be identified through community detection approaches. The evolution of social systems can be understood using these approaches by analysing their structure and behaviour. To handle this, a combination of these approaches, along with interaction-based analysis, is used to form cohesive communities, thereby enabling the study of social systems dynamically. In addition, attribute information plays a critical role. Most real-world graphs, like Facebook and Twitter, have attribute information that provides context, and integrating them with structural information offers deeper insights into patterns, which is a critical task. However, existing approaches have limitations in handling dynamics of social systems. Additionally, no existing approaches in the literature help identify potential links and form densely connected communities for attributed graphs. To address these challenges, we have proposed an information workflow, i.e., inc-LPCDAG (\underline{inc}remental Link Prediction and Community Detection in Attributed Graphs). We conducted experiments to evaluate efficiency, and results demonstrate the effectiveness of our proposed workflow by analysing and understanding structural and behavioural processes.
I. INTRODUCTION
The introduction identifies a gap in jointly handling link prediction and community detection for dynamic attributed graphs. It proposes inc-LPCDAG, combining incremental link prediction with community updates using structural and attribute information.
- Attributed graphs require combining node attributes with structural information because structural-only methods can predict links between users with different characteristics and detect communities less efficiently.
- Link prediction and community detection are related tasks, but few approaches use link prediction to improve communities in dynamic settings.
- inc-LPCDAG is proposed as an incremental workflow for link prediction and community detection in attributed graphs.
- The workflow predicts links, adds them to the graph, and updates the community structure to reflect those changes.
- The workflow includes Dynamic CSADW for Phase-I link prediction and Dynamic I-Louvain for Phase-II community detection.
II. RELATED WORK
Related work covers separate and combined approaches for link prediction and community detection in attributed or non-attributed graphs. The paper identifies the absence of a unified dynamic approach for attributed graphs that predicts missing links, updates the graph, and detects communities.
- Existing attributed-graph link prediction methods integrate structural and node attribute information using embeddings, graph neural networks, or higher-order proximities.
- Attributed-graph community detection methods combine node attributes and graph structure through matrix factorization, inertia-based modularity, or modified label propagation.
- Some methods use community structure to predict links, while others predict links before detecting communities when missing links may reduce community quality.
- LINE predicts missing links before community detection but is static, whereas LPCD extends this sequence incrementally for dynamic graphs.
- The literature lacks a unified approach that handles attributed graphs, predicts missing links, updates the graph, and detects communities dynamically.
III. LINK PREDICTION AND COMMUNITY DETECTION IN DYNAMIC GRAPHS
The section presents link prediction and community detection as related tasks in dynamic graphs, illustrating an iterative workflow that predicts links, updates the graph, and detects communities.
- Link prediction approaches can use community structure to favor links within communities, while community detection can be hindered by missing links.
- The workflow example begins with an attributed graph of 11 nodes and 12 links, then predicts links before community detection.
- After the first iteration, predicted links are added and three communities are formed in the updated graph.
- In the second iteration, additional links are predicted and added, after which node 5 moves to C1 while the other nodes remain in their communities.
A. Predicting Links in Evolving Attributed Graphs:
The proposed workflow combines incremental attributed-graph link prediction with incremental community updating. It refreshes only affected representations and communities as new links are introduced.
- A. Predicting Links in Evolving Attributed Graphs:: Dynamic CSADW incrementally updates affected node and edge embeddings when new links are added, avoiding recomputation over the entire graph.
- A. Predicting Links in Evolving Attributed Graphs:: The link-prediction phase combines structural and attribute similarity to generate weighted transitions, random walks, embeddings, and link probability scores.
- A. Predicting Links in Evolving Attributed Graphs:: Candidate non-connected pairs receive Hadamard edge embeddings, logistic-regression scores, and ranked selection of the top P% predicted links.
- B. Community Detection in Dynamic Attributed Graphs: A Knowledge-Driven Approach: Dynamic I-Louvain initializes singleton communities and repeatedly moves nodes when modularity gains are positive, stopping when modularity no longer changes.
- B. Community Detection in Dynamic Attributed Graphs: A Knowledge-Driven Approach: When new links arrive, community updates focus on affected nodes; within-community links preserve structure, whereas between-community links trigger updates.
C. Computational Complexity Analysis
The complexity analysis decomposes inc-LPCDAG into link-prediction and community-detection phases and gives an overall cost proportional to the number of incremental updates.
- Phase-I has complexity O(V^2 + V × Num Walks × Walk Length + M + E × d).
- Phase-II is approximately O(E × (V −1)) after accounting for modularity updates over incremental links.
- The overall workflow complexity is O(n × [(V^2 + V × Num Walks × Walk Length + M + E × d) + (E × (V −1))]).
IV. EXPERIMENTAL SETUP, DATASETS
The evaluation uses benchmark datasets and tests inc-LPCDAG’s two phases—link prediction and community detection—on a specified desktop software and hardware environment.
- Experiments evaluate the proposed inc-LPCDAG workflow using benchmark datasets suitable for both link prediction and community detection.
- The experiments were run on an Intel i7 1.90 GHz desktop with 32 GB RAM, Ubuntu 20.04.3 LTS, and Python 3.9.23.
A. Computational Environment
inc-LPCDAG limits link-prediction candidates to non-connected node pairs within two hops and incrementally updates the graph using selected top-ranked links.
- Considering all non-connected pairs would require exponential time, so experiments restrict candidates to pairs at a 2-hop distance.
- The workflow tests 5, 10, 15, and 20 prediction iterations and updates the graph with the top-ranked 3%, 5%, or 10% of candidate links.
B. Benchmark Datasets
The evaluation uses bibliographic Cora and Citeseer graphs alongside a Twitter graph whose attributes are expanded to create the Twitter+ dataset.
- Twitter contains 2511 nodes, one Tag attribute, and 37154 edges, while Twitter+ adds Visibility, Gender, Age, and Followers attributes.The additional attributes are generated using the Synt HoAG approach.
V. RESULTS, VALIDATION AND STATISTICAL ANALYSIS
The experiments evaluate inc-LPCDAG across iterative link updates, parameter settings, and community-quality measures, with 3% and 5% updates generally preserving good quality.
- V. RESULTS, VALIDATION AND STATISTICAL ANALYSIS: The study independently evaluates Phase-I link prediction and Phase-II community detection, using Table V for intermediate results and Table II for final results.Statistical analysis is also reported as evidence that the proposed approach is effective and statistically significant.
- V. RESULTS, VALIDATION AND STATISTICAL ANALYSIS: The experiments simulate incremental updates over 20 iterations, recording results every 5 iterations while varying predicted-link updates between 3%, 5%, and 10%.Community quality is evaluated with Performance, Modularity, Density, and Conductance.
- A. Significance of Results: 3% and 5% predicted-link updates maintain good community quality over the iterations, whereas 10% causes slight measure decreases while retaining community quality.The passage attributes the decrease to more predictions, particularly links between communities.
- A. Significance of Results: The Twitter+ evaluation with 10% predicted links stops at the 15th iteration because insufficient non-connected pairs remain within the two-hop constraint.
- 1) Parameter Tuning:: Parameter tuning identifies α=0.6, Walk Length=80, Num Walks=20, and node-embedding vector size=128 as effective settings.The tested ranges were α 0.4–0.7, Walk Length 20–90, and Num Walks 5–25; the passage states vector sizes were tested from 24 to 28 before selecting 128.
B. Evaluating the proposed approach
The study compares inc-LPCDAG with conventional approaches on attributed and relaxed non-attributed graphs, reporting stronger community-evaluation results than inc-AGGMMR.
- B. Evaluating the proposed approach: The comparison uses 10% predicted links over 20 iterations for Cora and Citeseer, and 15 iterations for Twitter+.Results are reported in Tables III and IV under attributed and relaxed non-attributed settings.
- 1) Performance Comparison on Attributed Graphs:: inc-LPCDAG is compared with inc-AGGMMR after adding edges to the conventional approach for evaluation.
- 1) Performance Comparison on Attributed Graphs:: inc-LPCDAG outperforms inc-AGGMMR on modularity (Q), density (ρ), and conductance (ϕ).The comparison is reported in columns F, G, H, and I of Table III.
2) Performance Comparison on Non-Attributed Graphs:
On non-attributed graphs, inc-LPCDAG outperforms conventional LPCD particularly on modularity while remaining comparable on other measures. Its dynamic link-prediction phase also performs well as predicted links update the graph.
- Performance comparison: inc-LPCDAG performs better than LPCD, especially on modularity, producing higher-quality final communities.Across other measures and datasets, the approaches show comparable performance.
- Performance comparison: AUC and AP results remain good when predicted links update the graph, supporting dynamic link prediction in Phase-I.The evaluation uses iterative graph updates, with one subgraph for prediction and another as ground truth.
- Performance comparison: The workflow was evaluated against inc-AGGMMR using statistical significance analysis.The comparison uses paired t-tests across benchmark datasets and modularity values for effect-size estimation.
- Performance comparison: The workflow addresses dynamic attributed-graph analysis through enhanced phases evaluated against existing methods.The authors frame the evaluation around efficiency and structural-behavioural analysis in dynamic environments.
- Performance comparison: The approach can be extended to weighted attributed graphs and different node types and attributes.These extensions are identified as future scope rather than results established by the current evaluation.