{"id":734,"date":"2014-02-25T13:55:58","date_gmt":"2014-02-25T17:55:58","guid":{"rendered":"http:\/\/www.michelecoscia.com\/?page_id=734"},"modified":"2019-03-27T12:01:53","modified_gmt":"2019-03-27T16:01:53","slug":"ycn-rw-bipartite-projections","status":"publish","type":"page","link":"https:\/\/www.michelecoscia.com\/?page_id=734","title":{"rendered":"YCN-RW: Bipartite Projections"},"content":{"rendered":"<p style=\"text-align: center;\"><strong>YCN Random Walk<\/strong><\/p>\n<p style=\"text-align: center;\">Implemented by me<\/p>\n<p style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-736\" src=\"http:\/\/www.michelecoscia.com\/wp-content\/uploads\/2014\/02\/toy.png\" alt=\"toy\" width=\"257\" height=\"242\" srcset=\"https:\/\/www.michelecoscia.com\/wp-content\/uploads\/2014\/02\/toy.png 715w, https:\/\/www.michelecoscia.com\/wp-content\/uploads\/2014\/02\/toy-300x281.png 300w\" sizes=\"auto, (max-width: 257px) 85vw, 257px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center;\"><span style=\"color: #ff0000;\"><strong>NEW VERSION! For the old implementation for the result reproducibility of the original paper, scroll below.<\/strong><\/span><\/p>\n<p style=\"text-align: center;\"><a href=\"http:\/\/www.michelecoscia.com\/wp-content\/uploads\/2019\/03\/network_map2.zip\">Download Link<\/a><\/p>\n<p>A custom Python library to perform bipartite network projection: transforming a bipartite network in a weighted unipartite network. Methods implemented:<\/p>\n<ul>\n<li>Simple projections (count, cosine, pearson, euclidean, jaccard);<\/li>\n<li>Hyperbolic projection [1];<\/li>\n<li>YCN Random Walks [2];<\/li>\n<li>ProbS [3], HeatS, &amp; Hybrid [4].<\/li>\n<\/ul>\n<p>Simply place the python script in your path or work folder. Each method requires you to pass a networkx graph and the list of nodes you want in your projection. It will return another networkx graph containing the projection and its weighted edges. An example of usage:<\/p>\n<pre>import networkx as nx\r\nimport network_map2 as nm2\r\n\r\nG = nx.read_edgelist(\"\/path\/to\/your\/network\")\r\nnodes = nx.algorithms.bipartite.basic.sets(G)\r\nrows = sorted(list(nodes[0]))\r\ncols = sorted(list(nodes[1]))\r\n\r\nGp = nm2.simple(G, rows)<\/pre>\n<p>Note that YCN, ProbS, HeatS, and Hybrid can return asymmetric projections (where the i,j weight is different than the j,i weight). By default they do not, so you have to manually set the &#8220;directed&#8221; paramter to True:<\/p>\n<pre>Gp = nm2.ycn(G, rows, directed = True)<\/pre>\n<p>Moreover, Hybrid takes an additional mandatory parameter, l, which regulates how much you want to weight HeatS over ProbS. Setting it to 0.5 means you take the middle point between the two:<\/p>\n<pre>Gp = nm2.hybrid(G, rows, .5, directed = True)<\/pre>\n<p>Note that this is all implemented in numpy, scipy, sklearn and networkx, so you have to have those libraries to use these methods. Also, while most methods use sparse matrix representation, some cannot, thus for large networks you might not be able to store the result in memory.<\/p>\n<p>For any inquiry, contact me at: <a href=\"michele.coscia@gmail.com\" target=\"_blank\" rel=\"noopener\">michele.coscia@gmail.com<\/a><\/p>\n<p style=\"text-align: center;\"><a href=\"http:\/\/www.michelecoscia.com\/wp-content\/uploads\/2019\/03\/network_map2.zip\">Download Link<\/a><\/p>\n<p>[1] Mark EJ Newman. Scientific collaboration networks. ii. shortest paths, weighted networks, and centrality. Physical review E, 64(1):016132, 2001c<\/p>\n<p>[2]\u00a0 Muhammed A Yildirim and Michele Coscia. Using random walks to generate associations between objects. PloS one, 9 (8):e104813, 2014<\/p>\n<p>[3] Tao Zhou, Jie Ren, Matus Medo, and Yi-Cheng Zhang. Bipartite network projection and personal recommendation. Physical Review E, 76(4):046115, 2007<\/p>\n<p>[4] Tao Zhou, Zoltan Kuscsik, Jian-Guo Liu, Matus Medo, Joseph Rushton Wakeling, and Yi-Cheng Zhang. Solving the apparent diversity-accuracy dilemma of recommender systems.<br \/>\nProceedings of the National Academy of Sciences, 107(10):4511\u20134515, 2010<\/p>\n<hr \/>\n<p style=\"text-align: center;\"><span style=\"color: #ff0000;\"><strong>LEGACY CODE! Only for reproducing the results in the paper.<\/strong><\/span><\/p>\n<p style=\"text-align: center;\"><a href=\"http:\/\/www.michelecoscia.com\/wp-content\/uploads\/2014\/04\/ycn-rw1.zip\">Download Link<\/a><\/p>\n<p style=\"text-align: left;\"><a href=\"http:\/\/www.michelecoscia.com\/wp-content\/uploads\/2014\/04\/ycn-rw1.zip\" target=\"_blank\" rel=\"noopener\">This archive<\/a> contains the code for utilizing the <strong>YCN-RW bipartite network projecting technique<\/strong> and for repeating the experiments of the paper &#8220;<a href=\"http:\/\/www.michelecoscia.com\/wp-content\/uploads\/2014\/07\/ycn_rw_MAY.pdf\"><strong>Using random walks to generate associations between objects<\/strong><\/a>&#8221; by <a href=\"http:\/\/www.hks.harvard.edu\/about\/faculty-staff-directory\/muhammed-yildirim\" target=\"_blank\" rel=\"noopener\">Muhammed Yildirim<\/a> and yours truly.<\/p>\n<p>For any inquiry, contact me at: <a href=\"michele.coscia@gmail.com\" target=\"_blank\" rel=\"noopener\">michele.coscia@gmail.com<\/a><\/p>\n<p>The archive contains the following files:<\/p>\n<p>&#8211; <strong>network_map.py<\/strong>: the Python library where the implementation is stored, along with other projection techniques that can be used (<strong>Cosine<\/strong>, <strong>Euclidean<\/strong>, <strong>Pearson<\/strong>, <strong>Jaccard<\/strong> and undirected <strong>Zhou<\/strong>, from the paper &#8220;<a href=\"https:\/\/doc.rero.ch\/record\/8503\/files\/zhang_bnp.pdf\" target=\"_blank\" rel=\"noopener\">Bipartite network projection and personal recommendation<\/a>&#8220;).<br \/>\n&#8211; <strong>experiment.py<\/strong>: a sample Python script file that illustrate how to use the library and it is set up for verifying the experiments of the paper.<br \/>\n&#8211; <strong>experiment_movielens.py<\/strong>: another Python script file that illustrate how to use the library and it is set up for verifying the experiments of the paper.<br \/>\n&#8211; <strong>pyroc.py<\/strong>: utility Python script invoked by experiment.py to draw ROC curves and calculate the AUC. Created by <a href=\"http:\/\/aimotion.blogspot.com\/\" target=\"_blank\" rel=\"noopener\">Marcel Caraciolo<\/a> on 2009-11-16.<br \/>\n&#8211; <strong>aid_bipartite<\/strong>: the bipartite network for the <strong>Aid<\/strong> dataset. It contains four tab-separated columns: entity1, entity2, type_of_entity1, type_of_entity2.<br \/>\n&#8211; <strong>aid_evalnet<\/strong>: the unipartite observed network for the <strong>Aid<\/strong> dataset. It contains three tab-separated columns: entity1, entity2, weight_of_unipartite_link.<br \/>\n&#8211; <strong>congress_bipartite<\/strong>: the bipartite network for the <strong>Congress<\/strong> dataset. It contains four tab-separated columns: entity1, entity2, type_of_entity1, type_of_entity2.<br \/>\n&#8211; <strong>congress_evalnet<\/strong>: the unipartite observed network for the <strong>Congress<\/strong> dataset. It contains three tab-separated columns: entity1, entity2, weight_of_unipartite_link.<br \/>\n&#8211; <strong>ipums_bipartite<\/strong>: the bipartite network for the <strong>IPUMS<\/strong> dataset. It contains four tab-separated columns: entity1, entity2, type_of_entity1, type_of_entity2.<br \/>\n&#8211; <strong>ipums_evalnet<\/strong>: the unipartite observed network for the <strong>IPUMS<\/strong> dataset. It contains three tab-separated columns: entity1, entity2, weight_of_unipartite_link.<br \/>\n&#8211; <strong>onet_bipartite<\/strong>: the bipartite network for the <strong>O-NET<\/strong> dataset. It contains four tab-separated columns: entity1, entity2, type_of_entity1, type_of_entity2.<br \/>\n&#8211; <strong>onet_evalnet<\/strong>: the unipartite observed network for the <strong>O-NET<\/strong> dataset. It contains three tab-separated columns: entity1, entity2, weight_of_unipartite_link.<br \/>\n&#8211; <strong>movielens_bipartite<\/strong>: the bipartite network for the <strong>Movielens<\/strong> dataset. It contains four tab-separated columns: entity1, entity2, type_of_entity1, type_of_entity2.<br \/>\n&#8211; <strong>README<\/strong>: a file containing this description.<\/p>\n<p><strong>Requirements<\/strong>:<\/p>\n<p><strong>network_map.py<\/strong> requires that you installed the <a href=\"http:\/\/www.numpy.org\/\" target=\"_blank\" rel=\"noopener\">Numpy<\/a>, <a href=\"http:\/\/www.scipy.org\/\" target=\"_blank\" rel=\"noopener\">Scipy<\/a> and <a href=\"http:\/\/scikit-learn.org\/stable\/\" target=\"_blank\" rel=\"noopener\">Scikit-learn<\/a> Python libraries.<br \/>\n<strong>experiment.py<\/strong> additionally requires the <a href=\"http:\/\/matplotlib.org\/\" target=\"_blank\" rel=\"noopener\">Matplotlib<\/a> Python library (it is required only for plotting the ROC curve and AUC calculation, so if you don&#8217;t want that, you can remove this requirement by commenting the relative lines, #23-33).<\/p>\n<p><strong>Usage instructions<\/strong>:<\/p>\n<p>To perform YCN-RW on a bipartite network, or use any other implemented method in network_map.py, first put the <strong>network_map.py<\/strong> file in the directory where you will run your Python script. Then, import it as a module: &#8220;<strong>import network_map<\/strong>&#8221; at the beginning of the file. Then, you can call the method by calling &#8220;<strong>edges = network_map.ycn_edges_2(bipartite_edges, key_map, directed = True\/False)<\/strong>&#8220;. The two parameters are:<br \/>\n&#8211; &#8220;<strong>bipartite_edges<\/strong>&#8220;: it has to be a dictionary. The <strong>key<\/strong> of the dictionary is the entity id. The <strong>value<\/strong> of the dictionary is the entity&#8217;s adjacency list, i.e. the list of ids of the entities this entity is connected to. Both entity types of the bipartite network has to be present as keys of the dictionary (see <strong>experiment.py<\/strong> lines <strong>60-61<\/strong>).<br \/>\n&#8211; &#8220;<strong>key_map<\/strong>&#8220;: it has to be a dictionary. The <strong>key<\/strong> of the dictionary is the entity id. The <strong>value<\/strong> of the dictionary is 0 if the entity is of the type that has to be in the unipartite network, 1 otherwise (see <strong>experiment.py<\/strong> lines <strong>58-59<\/strong>).<br \/>\n&#8211; &#8220;<strong>directed<\/strong>&#8220;: optional parameter. If True, then the x-y similarity will be different from the y-x similarity. Default: False.<br \/>\nThe output is a dictionary. The <strong>key<\/strong> of the dictionary is a tuple of two entities (a unipartite edge). The <strong>value<\/strong> of the dictionary is the relatedness value.<\/p>\n<p>You can replicate the results of the paper (and see how to use network_map.py and how it works) by using the <strong>experiment.py<\/strong> script.<br \/>\n<strong>experiment.py<\/strong> requires as input two files: the bipartite network and the unipartite network used for evaluation. In the package, these are the <strong>*_bipartite<\/strong> and <strong>*_evalnet<\/strong> files respectively, for the four datasets used in the paper (<strong>aid_*<\/strong>, <strong>congress_*<\/strong>, <strong>ipums_*<\/strong> and <strong>onet_*<\/strong>). <strong>experiment.py<\/strong> will provide as output a ROC plot and the AUC value (in parenthesis, the difference of AUC w.r.t the ycn-rw&#8217;s AUC). It will also write several files:<br \/>\n&#8211; &#8220;<strong>x_y_edge<\/strong>&#8221; file, containing the unipartite edges. Here, &#8220;<strong>x<\/strong>&#8221; is the <strong>dataset name<\/strong> (aid, congress, ipums, onet) and &#8220;<strong>y<\/strong>&#8221; is the <strong>projection method name<\/strong> (ycn, zho, jac, euc, pea, cos).<br \/>\n&#8211; &#8220;<strong>x_y_roc<\/strong>&#8221; file, containing the data to plot the ROC curve. Again, &#8220;<strong>x<\/strong>&#8221; is the <strong>dataset name<\/strong> (aid, congress, ipums, onet) and &#8220;<strong>y<\/strong>&#8221; is the <strong>projection method name<\/strong> (ycn, zho, jac, euc, pea, cos).<br \/>\n&#8211; &#8220;<strong>x_auc<\/strong>&#8221; file, containing the AUC values. Here, &#8220;<strong>x<\/strong>&#8221; is the <strong>dataset name<\/strong> (aid, congress, ipums, onet).<\/p>\n<p>To run <strong>experiment.py<\/strong> , make sure that the input files, <strong>network_map.py<\/strong> and <strong>pyroc.py<\/strong> are in the same folder, then type in your shell: <strong>python experiment.py dataset_name significance_threshold<\/strong>, where &#8220;<strong>dataset_name<\/strong>&#8221; is the filename part before the &#8220;<strong>_bipartite<\/strong>&#8221; and &#8220;<strong>_evalnet<\/strong>&#8221; extensions of your input files; and &#8220;<strong>significance_threshold<\/strong>&#8221; is the threshold for your unipartite edges to be considered significant.<br \/>\nFor example, to replicate the paper experiments, these are the commands used:<\/p>\n<p><strong>python experiment.py aid 12<\/strong><br \/>\n<strong>python experiment.py congress 7<\/strong><br \/>\n<strong>python experiment.py ipums 7<\/strong><br \/>\n<strong>python experiment.py onet 140<\/strong><\/p>\n<p><strong>experiment_movielens.py<\/strong> runs with the same set up, without the <strong>significance_threshold<\/strong> parameter. It does not generate aucs and rocs, but two files describing the <strong>rs<\/strong> and <strong>hit rates<\/strong>. See Zhou et al.&#8217;s\u00a0&#8220;<a href=\"https:\/\/doc.rero.ch\/record\/8503\/files\/zhang_bnp.pdf\" target=\"_blank\" rel=\"noopener\">Bipartite network projection and personal recommendation<\/a>&#8221; for more details about how to interpret the results.<\/p>\n<p>For any inquiry, contact me at: <a href=\"michele.coscia@gmail.com\" target=\"_blank\" rel=\"noopener\">michele.coscia@gmail.com<\/a><\/p>\n<p style=\"text-align: center;\"><a href=\"http:\/\/www.michelecoscia.com\/wp-content\/uploads\/2014\/04\/ycn-rw1.zip\" target=\"_blank\" rel=\"noopener\">Download Link<\/a><\/p>\n<p style=\"text-align: left;\">Happy bipartite network projection!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>YCN Random Walk Implemented by me &nbsp; NEW VERSION! For the old implementation for the result reproducibility of the original paper, scroll below. Download Link A custom Python library to perform bipartite network projection: transforming a bipartite network in a weighted unipartite network. Methods implemented: Simple projections (count, cosine, pearson, euclidean, jaccard); Hyperbolic projection [1]; &hellip; <a href=\"https:\/\/www.michelecoscia.com\/?page_id=734\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;YCN-RW: Bipartite Projections&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":25,"menu_order":0,"comment_status":"open","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-734","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.michelecoscia.com\/index.php?rest_route=\/wp\/v2\/pages\/734","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.michelecoscia.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.michelecoscia.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.michelecoscia.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.michelecoscia.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=734"}],"version-history":[{"count":9,"href":"https:\/\/www.michelecoscia.com\/index.php?rest_route=\/wp\/v2\/pages\/734\/revisions"}],"predecessor-version":[{"id":2146,"href":"https:\/\/www.michelecoscia.com\/index.php?rest_route=\/wp\/v2\/pages\/734\/revisions\/2146"}],"up":[{"embeddable":true,"href":"https:\/\/www.michelecoscia.com\/index.php?rest_route=\/wp\/v2\/pages\/25"}],"wp:attachment":[{"href":"https:\/\/www.michelecoscia.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=734"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}