
Block-approximated exponential random graphs
- Author
- Florian Adriaens, Alexandru-Cristian Mara (UGent) , Jefrey Lijffijt (UGent) and Tijl De Bie (UGent)
- Organization
- Project
- Abstract
- An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. By utilizing fast matrix block-approximation techniques, we propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions, while being able to meaningfully model local information of the graph (e.g., degrees) as well as global information (e.g., clustering coefficient, assortativity, etc.) if desired. This allows one to efficiently generate random networks with similar properties as an observed network, and the models can be used for several downstream tasks such as link prediction. Our methods are scalable to sparse graphs consisting of millions of nodes. Empirical evaluation demonstrates competitiveness in terms of both speed and accuracy with state-of-the-art methods-which are typically based on embedding the graph into some low-dimensional space- for link prediction, showcasing the potential of a more direct and interpretable probablistic model for this task.
- Keywords
- maximum entropy models, exponential random graphs, network modeling, link prediction, P-ASTERISK MODELS
Downloads
-
(...).pdf
- full text (Accepted manuscript)
- |
- UGent only
- |
- |
- 1.35 MB
-
DS353 i.pdf
- full text (Accepted manuscript)
- |
- open access
- |
- |
- 536.52 KB
-
(...).pdf
- full text (Published version)
- |
- UGent only
- |
- |
- 832.80 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-8675300
- MLA
- Adriaens, Florian, et al. “Block-Approximated Exponential Random Graphs.” 2020 IEEE 7TH INTERNATIONAL CONFERENCE ON DATA SCIENCE AND ADVANCED ANALYTICS (DSAA 2020), edited by G. Webb et al., IEEE, 2020, pp. 70–80, doi:10.1109/DSAA49011.2020.00019.
- APA
- Adriaens, F., Mara, A.-C., Lijffijt, J., & De Bie, T. (2020). Block-approximated exponential random graphs. In G. Webb, Z. Zhang, V. S. Tseng, G. Williams, M. Vlachos, & L. Cao (Eds.), 2020 IEEE 7TH INTERNATIONAL CONFERENCE ON DATA SCIENCE AND ADVANCED ANALYTICS (DSAA 2020) (pp. 70–80). https://doi.org/10.1109/DSAA49011.2020.00019
- Chicago author-date
- Adriaens, Florian, Alexandru-Cristian Mara, Jefrey Lijffijt, and Tijl De Bie. 2020. “Block-Approximated Exponential Random Graphs.” In 2020 IEEE 7TH INTERNATIONAL CONFERENCE ON DATA SCIENCE AND ADVANCED ANALYTICS (DSAA 2020), edited by G. Webb, Z. Zhang, V. S. Tseng, G. Williams, M. Vlachos, and L. Cao, 70–80. IEEE. https://doi.org/10.1109/DSAA49011.2020.00019.
- Chicago author-date (all authors)
- Adriaens, Florian, Alexandru-Cristian Mara, Jefrey Lijffijt, and Tijl De Bie. 2020. “Block-Approximated Exponential Random Graphs.” In 2020 IEEE 7TH INTERNATIONAL CONFERENCE ON DATA SCIENCE AND ADVANCED ANALYTICS (DSAA 2020), ed by. G. Webb, Z. Zhang, V. S. Tseng, G. Williams, M. Vlachos, and L. Cao, 70–80. IEEE. doi:10.1109/DSAA49011.2020.00019.
- Vancouver
- 1.Adriaens F, Mara A-C, Lijffijt J, De Bie T. Block-approximated exponential random graphs. In: Webb G, Zhang Z, Tseng VS, Williams G, Vlachos M, Cao L, editors. 2020 IEEE 7TH INTERNATIONAL CONFERENCE ON DATA SCIENCE AND ADVANCED ANALYTICS (DSAA 2020). IEEE; 2020. p. 70–80.
- IEEE
- [1]F. Adriaens, A.-C. Mara, J. Lijffijt, and T. De Bie, “Block-approximated exponential random graphs,” in 2020 IEEE 7TH INTERNATIONAL CONFERENCE ON DATA SCIENCE AND ADVANCED ANALYTICS (DSAA 2020), Sydney, Australia, 2020, pp. 70–80.
@inproceedings{8675300, abstract = {{An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. By utilizing fast matrix block-approximation techniques, we propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions, while being able to meaningfully model local information of the graph (e.g., degrees) as well as global information (e.g., clustering coefficient, assortativity, etc.) if desired. This allows one to efficiently generate random networks with similar properties as an observed network, and the models can be used for several downstream tasks such as link prediction. Our methods are scalable to sparse graphs consisting of millions of nodes. Empirical evaluation demonstrates competitiveness in terms of both speed and accuracy with state-of-the-art methods-which are typically based on embedding the graph into some low-dimensional space- for link prediction, showcasing the potential of a more direct and interpretable probablistic model for this task.}}, author = {{Adriaens, Florian and Mara, Alexandru-Cristian and Lijffijt, Jefrey and De Bie, Tijl}}, booktitle = {{2020 IEEE 7TH INTERNATIONAL CONFERENCE ON DATA SCIENCE AND ADVANCED ANALYTICS (DSAA 2020)}}, editor = {{Webb, G. and Zhang, Z. and Tseng, V. S. and Williams, G. and Vlachos, M. and Cao, L.}}, isbn = {{9781728182063}}, issn = {{2472-1573}}, keywords = {{maximum entropy models,exponential random graphs,network modeling,link prediction,P-ASTERISK MODELS}}, language = {{eng}}, location = {{Sydney, Australia}}, pages = {{70--80}}, publisher = {{IEEE}}, title = {{Block-approximated exponential random graphs}}, url = {{http://dx.doi.org/10.1109/DSAA49011.2020.00019}}, year = {{2020}}, }
- Altmetric
- View in Altmetric
- Web of Science
- Times cited: