A method and a system for privacy-preserving SNA. A plurality of vertices of a first subgraph of a graph is encrypted with a first key of a commutatively encryption scheme. A plurality of vertices of a second subgraph encrypted with a second key of the commutatively encryption scheme are received and encrypted commutatively with the first key. A plurality of commutatively encrypted vertices of the first subgraph and a plurality of commutatively encrypted vertices of the second subgraph are used for computing centrality metrics preserving the privacy of the graph and its structure.