AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (8.9 MB)
Submit Manuscript AI Chat Paper
Show Outline
Show full outline
Hide outline
Show full outline
Hide outline
Open Access

Public-private-core maintenance in public-private-graphs

School of Computer Science and Technology, Shandong University, Qingdao 266200, China
Department of Computer Science, Georgia State University, Atlanta, GA 30080, USA
Show Author Information


A public-private-graph (pp-graph) is developed to model social networks with hidden relationships, and it consists of one public graph in which edges are visible to all users, and multiple private graphs in which edges are only visible to its endpoint users. In contrast with conventional graphs where the edges can be visible to all users, it lacks accurate indexes to evaluate the importance of a vertex in a pp-graph. In this paper, we first propose a novel concept, public-private-core (pp-core) number based on the k-core number, which integrally considers both the public graph and private graphs of vertices, to measure how critical a user is. We then give an efficient algorithm for the pp-core number computation, which takes only linear time and space. Considering that the graphs can be always evolving over time, we also present effective algorithms for pp-core maintenance after the graph changes, avoiding redundant re-computation of pp-core number. Extension experiments conducted on real-world social networks show that our algorithms achieve good efficiency and stability. Compared to recalculating the pp-core numbers of all vertices, our maintenance algorithms can reduce the computation time by about 6–8 orders of magnitude.


R. Dey, Z. Jelveh, and K. Ross, Facebook users have become much more private: A large-scale study, in Proc. 2012 IEEE Int. Conf. on Pervasive Computing and Communications Workshops, Lugano, Switzerland, 2012, pp. 346−352.
F. Chierichetti, A. Epasto, R. Kumar, S. Lattanzi, and V. Mirrokni, Efficient algorithms for public-private social networks, in Proc. 21thACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Sydney, Australia, 2015, pp. 139−148.
A. D. Sarma, S. Gollapudi, M. Najork, and R. Panigrahy, A sketch-based distance oracle for web-scale graphs, in Proc. 3rdACM Int. Conf. on Web Search and Data Mining, New York, NY, USA, 2010, pp. 401−410.
T. H. Haveliwala, Topic-sensitive PageRank, in Proc. 11thInt. Conf. on World Wide Web, Honolulu, HI, USA, 2002, pp. 517−526.

N. Bansal, A. Blum, and S. Chawla, Correlation clustering, Mach. Learn., vol. 56, nos. 1–3, pp. 89–113, 2004.


K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, and A. Sharma, Preventing unraveling in social networks: The anchored k-core problem, SIAM J. Discrete Math., vol. 29, no. 3, pp. 1452–1475, 2015.


F. Zhang, W. J. Zhang, Y. Zhang, L. Qin, and X. M. Lin, OLAK: An efficient algorithm to prevent unraveling in social networks, Proc. VLDB Endow., vol. 10, no. 6, pp. 649–660, 2017.

F. Zhang, Y. Zhang, L. Qin, W. J. Zhang, and X. M. Lin, Finding critical users for social network engagement: The collapsed k-core problem, in Proc. 31stAAAI Conf. on Artificial Intelligence, San Francisco, CA, USA, 2017, pp. 245−251.

F. Zhang, C. G. Li, Y. Zhang, L. Qin, and W. J. Zhang, Finding critical users in social communities: The collapsed core and truss problems, IEEE Trans. Knowl. Data Eng., vol. 32, no. 1, pp. 78–91, 2020.

S. B. Seidman, Network structure and minimum degree, Soc. Netw. , vol. 5, no. 3, pp. 269−287, 1983.

Q. S. Hua, Y. L. Shi, D. X. Yu, H. Jin, J. G. Yu, Z. P. Cai, X. Z. Cheng, and H. H. Chen, Faster parallel core maintenance algorithms in dynamic graphs, IEEE Trans. Parallel Distrib. Syst., vol. 31, no. 6, pp. 1287–1300, 2020.

V. Batagelj and M. Zaversnik, An O(m) algorithm for cores decomposition of networks, arXiv preprint arXiv: cs/0310049, 2003.
V. Batagelj and M. Zaveršnik, Fast algorithms for determining (generalized) core groups in social networks,Adv. Data Anal. Classi. , vol. 5, no. 2, pp. 129−145, 2011.

A. E. Saríyüce, B. Gedik, G. Jacques-Silva, K. L. Wu, and Ü. V. Çatalyürek, Streaming algorithms for k-core decomposition, Proc. VLDB Endow., vol. 6, no. 6, pp. 433–444, 2013.


M. A. Beauchamp, An improved index of centrality, Behav. Sci., vol. 10, no. 2, pp. 161–163, 1965.


P. Bonacich, Power and centrality: A family of measures, Am. J. Sociol., vol. 92, no. 5, pp. 1170–1182, 1987.

U. Brandes, A faster algorithm for betweenness centrality, J. Math. Sociol. , vol. 25, no. 2, pp. 163−177, 2001.
L. C. Freeman, A set of measures of centrality based on betweenness, Sociometry, vol. 40, no. 1, pp. 35−41, 1977.
Q. Luo, D. X. Yu, H. Sheng, J. G. Yu, and X. Z. Cheng, Distributed algorithm for truss maintenance in dynamic graphs, in Proc. 21stInt. Conf. on Parallel and Distributed Computing, Applications and Technologies, Shenzhen, China, 2021, pp. 104−115.
X. Huang, J. Jiang, B. Choi, J. Xu, Z. Zhang, and Y. Song, PP-DBLP: Modeling and generating attributed public-private networks with DBLP, in 2018 IEEE International Conference on Data Mining Workshops (ICDMW), doi: 10.1109/ICDMW.2018.00142.
B. Mirzasoleiman, M. Zadimoghaddam, and A. Karbasi, Fast distributed submodular cover: Public-private data summarization, in Proc. 30thInt. Conf. on Neural Information Processing Systems, Barcelona, Spain, 2016, pp. 3601−3609.
A. Archer, S. Lattanzi, P. Likarish, and S. Vassilvitskii, Indexing public-private graphs, in Proc. 26thInt. Conf. on World Wide Web, Perth, Australia, 2017, pp. 1461−1470.
J. X. Jiang, X. Huang, B. Choi, J. L. Xu, S. S. Bhowmick, and L. Xu, PPKWS: An efficient framework for keyword search on public-private networks, in Proc. 36thInt. Conf. on Data Engineering(ICDE), Dallas, TX, USA, 2020, pp. 457−468.
J. Cheng, Y. P. Ke, S. M. Chu, and M. T. Özsu, Efficient core decomposition in massive networks, in Proc. 27thInt. Conf. on Data Engineering, Hannover, Germany, 2011, pp. 51−62.

R. H. Li, J. X. Yu, and R. Mao, Efficient core maintenance in large dynamic graphs, IEEE Trans. Knowl. Data Eng., vol. 26, no. 10, pp. 2453–2465, 2014.

N. Dasari, D. Ranjan, and M. Zubair, ParK: An efficient algorithm for k-core decomposition on multicore processors, in Proc. 2014 IEEE Int. Conf. on Big Data (Big Data), Washington, DC, USA, 2014, pp. 9−16.
Q. Luo, D. X. Yu, F. Li, Z. H. Dou, Z. P. Cai, J. G. Yu, and X. Z. Cheng, Distributed core decomposition in probabilistic graphs, in Proc. 8thInt. Conf. on Computational Data and Social Networks, Ho Chi Minh City, Vietnam, 2019, pp. 16−32.
W. Bai, Y. X. Zhang, X. Z. Liu, M. Chen, and D. Wu, Efficient core maintenance of dynamic graphs, in Proc. 25thInt. Conf. on Database Systems for Advanced Applications, Jeju, Republic of Korea, 2020, pp. 658−665.
D. X. Yu, N. Wang, Q. Luo, F. Li, J. G. Yu, X. Z. Cheng, and Z. P. Cai, Fast core maintenance in dynamic graphs, IEEE Trans. Comput. Soc. Syst., doi: 10.1109/TCSS.2021.3064836.
Intelligent and Converged Networks
Pages 306-319
Cite this article:
Yu D, Zhang X, Luo Q, et al. Public-private-core maintenance in public-private-graphs. Intelligent and Converged Networks, 2021, 2(4): 306-319.










Received: 03 December 2021
Accepted: 18 January 2022
Published: 30 December 2021
© All articles included in the journal are copyrighted to the ITU and TUP.

This work is available under the CC BY-NC-ND 3.0 IGO license: