Disclosed is a method for managing mobility of mobile nodes between heterogeneous networks in an IP-based mobile communication system including a plurality of access nodes for providing an IP service to mobile nodes located in their service areas and a neighbor graph server for supporting connection to the access nodes by the mobile nodes. The method includes classifying the access nodes according to available service level; classifying the mobile nodes according to required service level, generating service level neighbor graphs each including access nodes supporting the same service level; generating a mapping table for mapping the mobile nodes to the neighbor graphs according to service level required by the mobile node; and supporting movement of a mobile node between networks using the neighbor graph and the mapping table.