Loading…
An Ensemble Approach to Link Prediction
A network with n nodes contains O(n 2 ) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Further, even though link prediction is closely related to missing value estimation problems, it is often difficult to...
Saved in:
Published in: | IEEE transactions on knowledge and data engineering 2017-11, Vol.29 (11), p.2402-2416 |
---|---|
Main Authors: | , , , , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
cited_by | cdi_FETCH-LOGICAL-c293t-39d9001d0d05fd80cd7df287c5a0e0c2a06a6be4da0b576510a98de7952390493 |
---|---|
cites | cdi_FETCH-LOGICAL-c293t-39d9001d0d05fd80cd7df287c5a0e0c2a06a6be4da0b576510a98de7952390493 |
container_end_page | 2416 |
container_issue | 11 |
container_start_page | 2402 |
container_title | IEEE transactions on knowledge and data engineering |
container_volume | 29 |
creator | Liang Duan Shuai Ma Aggarwal, Charu Tiejun Ma Jinpeng Huai |
description | A network with n nodes contains O(n 2 ) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Further, even though link prediction is closely related to missing value estimation problems, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity on large networks. Hence, most known link prediction methods are designed for evaluating the link propensity on a specified subset of links, rather than on the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this article, we propose an ensemble enabled approach to scaling up link prediction, by decomposing traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with latent factor models, which can be effectively implemented on networks of modest size. By incorporating with the characteristics of link prediction, the ensemble approach further reduces the sizes of subproblems without sacrificing its prediction accuracy. The ensemble enabled approach has several advantages in terms of performance, and our experimental results demonstrate the effectiveness and scalability of our approach. |
doi_str_mv | 10.1109/TKDE.2017.2730207 |
format | article |
fullrecord | <record><control><sourceid>proquest_ieee_</sourceid><recordid>TN_cdi_ieee_primary_7987705</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>7987705</ieee_id><sourcerecordid>2174463798</sourcerecordid><originalsourceid>FETCH-LOGICAL-c293t-39d9001d0d05fd80cd7df287c5a0e0c2a06a6be4da0b576510a98de7952390493</originalsourceid><addsrcrecordid>eNo9kD1PwzAQhi0EEqXwAxBLJAamlDt_5OyxKuVDVIKhzJZrOyKlTYodBv49qVox3Q3P-97pYewaYYII5n75-jCfcECacBLAgU7YCJXSJUeDp8MOEkspJJ2zi5zXAKBJ44jdTdti3ua4XW1iMd3tUuf8Z9F3xaJpv4r3FEPj-6ZrL9lZ7TY5Xh3nmH08zpez53Lx9vQymy5Kz43oS2GCAcAAAVQdNPhAoeaavHIQwXMHlatWUQYHK0WVQnBGh0hGcWFAGjFmt4fe4ZPvn5h7u-5-UjuctBxJykqQ0QOFB8qnLucUa7tLzdalX4tg9z7s3ofd-7BHH0Pm5pBpYoz__NBGBEr8AXVQWUY</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2174463798</pqid></control><display><type>article</type><title>An Ensemble Approach to Link Prediction</title><source>IEEE Xplore (Online service)</source><creator>Liang Duan ; Shuai Ma ; Aggarwal, Charu ; Tiejun Ma ; Jinpeng Huai</creator><creatorcontrib>Liang Duan ; Shuai Ma ; Aggarwal, Charu ; Tiejun Ma ; Jinpeng Huai</creatorcontrib><description>A network with n nodes contains O(n 2 ) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Further, even though link prediction is closely related to missing value estimation problems, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity on large networks. Hence, most known link prediction methods are designed for evaluating the link propensity on a specified subset of links, rather than on the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this article, we propose an ensemble enabled approach to scaling up link prediction, by decomposing traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with latent factor models, which can be effectively implemented on networks of modest size. By incorporating with the characteristics of link prediction, the ensemble approach further reduces the sizes of subproblems without sacrificing its prediction accuracy. The ensemble enabled approach has several advantages in terms of performance, and our experimental results demonstrate the effectiveness and scalability of our approach.</description><identifier>ISSN: 1041-4347</identifier><identifier>EISSN: 1558-2191</identifier><identifier>DOI: 10.1109/TKDE.2017.2730207</identifier><identifier>CODEN: ITKEEH</identifier><language>eng</language><publisher>New York: IEEE</publisher><subject>Algorithm design and analysis ; big data ; Collaboration ; ensembles ; Estimation ; Link prediction ; Links ; Mathematical models ; Networks ; NMF ; Prediction algorithms ; Predictive models ; Social network services ; social networks</subject><ispartof>IEEE transactions on knowledge and data engineering, 2017-11, Vol.29 (11), p.2402-2416</ispartof><rights>Copyright The Institute of Electrical and Electronics Engineers, Inc. (IEEE) 2017</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c293t-39d9001d0d05fd80cd7df287c5a0e0c2a06a6be4da0b576510a98de7952390493</citedby><cites>FETCH-LOGICAL-c293t-39d9001d0d05fd80cd7df287c5a0e0c2a06a6be4da0b576510a98de7952390493</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/7987705$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,54796</link.rule.ids></links><search><creatorcontrib>Liang Duan</creatorcontrib><creatorcontrib>Shuai Ma</creatorcontrib><creatorcontrib>Aggarwal, Charu</creatorcontrib><creatorcontrib>Tiejun Ma</creatorcontrib><creatorcontrib>Jinpeng Huai</creatorcontrib><title>An Ensemble Approach to Link Prediction</title><title>IEEE transactions on knowledge and data engineering</title><addtitle>TKDE</addtitle><description>A network with n nodes contains O(n 2 ) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Further, even though link prediction is closely related to missing value estimation problems, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity on large networks. Hence, most known link prediction methods are designed for evaluating the link propensity on a specified subset of links, rather than on the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this article, we propose an ensemble enabled approach to scaling up link prediction, by decomposing traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with latent factor models, which can be effectively implemented on networks of modest size. By incorporating with the characteristics of link prediction, the ensemble approach further reduces the sizes of subproblems without sacrificing its prediction accuracy. The ensemble enabled approach has several advantages in terms of performance, and our experimental results demonstrate the effectiveness and scalability of our approach.</description><subject>Algorithm design and analysis</subject><subject>big data</subject><subject>Collaboration</subject><subject>ensembles</subject><subject>Estimation</subject><subject>Link prediction</subject><subject>Links</subject><subject>Mathematical models</subject><subject>Networks</subject><subject>NMF</subject><subject>Prediction algorithms</subject><subject>Predictive models</subject><subject>Social network services</subject><subject>social networks</subject><issn>1041-4347</issn><issn>1558-2191</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><recordid>eNo9kD1PwzAQhi0EEqXwAxBLJAamlDt_5OyxKuVDVIKhzJZrOyKlTYodBv49qVox3Q3P-97pYewaYYII5n75-jCfcECacBLAgU7YCJXSJUeDp8MOEkspJJ2zi5zXAKBJ44jdTdti3ua4XW1iMd3tUuf8Z9F3xaJpv4r3FEPj-6ZrL9lZ7TY5Xh3nmH08zpez53Lx9vQymy5Kz43oS2GCAcAAAVQdNPhAoeaavHIQwXMHlatWUQYHK0WVQnBGh0hGcWFAGjFmt4fe4ZPvn5h7u-5-UjuctBxJykqQ0QOFB8qnLucUa7tLzdalX4tg9z7s3ofd-7BHH0Pm5pBpYoz__NBGBEr8AXVQWUY</recordid><startdate>20171101</startdate><enddate>20171101</enddate><creator>Liang Duan</creator><creator>Shuai Ma</creator><creator>Aggarwal, Charu</creator><creator>Tiejun Ma</creator><creator>Jinpeng Huai</creator><general>IEEE</general><general>The Institute of Electrical and Electronics Engineers, Inc. (IEEE)</general><scope>97E</scope><scope>RIA</scope><scope>RIE</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7SP</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20171101</creationdate><title>An Ensemble Approach to Link Prediction</title><author>Liang Duan ; Shuai Ma ; Aggarwal, Charu ; Tiejun Ma ; Jinpeng Huai</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c293t-39d9001d0d05fd80cd7df287c5a0e0c2a06a6be4da0b576510a98de7952390493</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>Algorithm design and analysis</topic><topic>big data</topic><topic>Collaboration</topic><topic>ensembles</topic><topic>Estimation</topic><topic>Link prediction</topic><topic>Links</topic><topic>Mathematical models</topic><topic>Networks</topic><topic>NMF</topic><topic>Prediction algorithms</topic><topic>Predictive models</topic><topic>Social network services</topic><topic>social networks</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Liang Duan</creatorcontrib><creatorcontrib>Shuai Ma</creatorcontrib><creatorcontrib>Aggarwal, Charu</creatorcontrib><creatorcontrib>Tiejun Ma</creatorcontrib><creatorcontrib>Jinpeng Huai</creatorcontrib><collection>IEEE All-Society Periodicals Package (ASPP) 2005-present</collection><collection>IEEE All-Society Periodicals Package (ASPP) 1998–Present</collection><collection>IEEE Electronic Library Online</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Electronics & Communications Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>IEEE transactions on knowledge and data engineering</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Liang Duan</au><au>Shuai Ma</au><au>Aggarwal, Charu</au><au>Tiejun Ma</au><au>Jinpeng Huai</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>An Ensemble Approach to Link Prediction</atitle><jtitle>IEEE transactions on knowledge and data engineering</jtitle><stitle>TKDE</stitle><date>2017-11-01</date><risdate>2017</risdate><volume>29</volume><issue>11</issue><spage>2402</spage><epage>2416</epage><pages>2402-2416</pages><issn>1041-4347</issn><eissn>1558-2191</eissn><coden>ITKEEH</coden><abstract>A network with n nodes contains O(n 2 ) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Further, even though link prediction is closely related to missing value estimation problems, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity on large networks. Hence, most known link prediction methods are designed for evaluating the link propensity on a specified subset of links, rather than on the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this article, we propose an ensemble enabled approach to scaling up link prediction, by decomposing traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with latent factor models, which can be effectively implemented on networks of modest size. By incorporating with the characteristics of link prediction, the ensemble approach further reduces the sizes of subproblems without sacrificing its prediction accuracy. The ensemble enabled approach has several advantages in terms of performance, and our experimental results demonstrate the effectiveness and scalability of our approach.</abstract><cop>New York</cop><pub>IEEE</pub><doi>10.1109/TKDE.2017.2730207</doi><tpages>15</tpages></addata></record> |
fulltext | fulltext |
identifier | ISSN: 1041-4347 |
ispartof | IEEE transactions on knowledge and data engineering, 2017-11, Vol.29 (11), p.2402-2416 |
issn | 1041-4347 1558-2191 |
language | eng |
recordid | cdi_ieee_primary_7987705 |
source | IEEE Xplore (Online service) |
subjects | Algorithm design and analysis big data Collaboration ensembles Estimation Link prediction Links Mathematical models Networks NMF Prediction algorithms Predictive models Social network services social networks |
title | An Ensemble Approach to Link Prediction |
url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-24T20%3A17%3A40IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_ieee_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=An%20Ensemble%20Approach%20to%20Link%20Prediction&rft.jtitle=IEEE%20transactions%20on%20knowledge%20and%20data%20engineering&rft.au=Liang%20Duan&rft.date=2017-11-01&rft.volume=29&rft.issue=11&rft.spage=2402&rft.epage=2416&rft.pages=2402-2416&rft.issn=1041-4347&rft.eissn=1558-2191&rft.coden=ITKEEH&rft_id=info:doi/10.1109/TKDE.2017.2730207&rft_dat=%3Cproquest_ieee_%3E2174463798%3C/proquest_ieee_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c293t-39d9001d0d05fd80cd7df287c5a0e0c2a06a6be4da0b576510a98de7952390493%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2174463798&rft_id=info:pmid/&rft_ieee_id=7987705&rfr_iscdi=true |