Existing　graph　systems　focus　mainly　on　the　execution　efficiency　of　the　graph　analysis　tasks,　often　ignoring　the　importance　and　efficiency　of　time-evolving　graph　storage.　However,　to　effectively　mine　the　potential　application　values,　an　efficient　storage　system　is　important　for　time-evolving　graphs　whose　storage　requirement　scales　with　the　increasing　number　of　snapshots.　Storage　cost　and　snapshot　access　speed　are　the　two　most　important　performance　indicators　for　a　time-evolving　graph　storage　system,　which　are　challenging　for　designers　of　such　systems　because　they　are　conflicting　goals.　In　this　article,　we　address　these　challenges　by　proposing　an　efficient　storage　scheme　for　the　large　time-evolving　graphs.　We　first　design　a　Snapshot-level　Data　Deduplication　(SLDD)　strategy　to　eliminate　the　large　number　of　repeated　vertices　and　edges　among　the　snapshots,　and　then　a　Structure-Changing　Graph　Representation　(SCGR)　to　significantly　improve　the　snapshot　access　speed.　We　implement　an　efficient　time-evolving　graph　storage　system,　TgStore,　based　on　this　scheme　to　effectively　store　large-scale　time-evolving　graphs,　aiming　to　efficiently　support　the　time-evolving　graph　analysis　tasks.　Experimental　results　show　that　TgStore　can　obtain　a　high　compression　ratio　of　43.03:1　when　storing　100　snapshots　of　Twitter,　while　with　an　average　snapshot　access　speedup　of　16×.　Efficient　storage　scheme　enables　TgStore　to　efficiently　support　time-evolving　graph　algorithms.　For　example,　when　executing　the　Pagerank　algorithm　on　the　time-evolving　graph　of　Twitter,　TgStore　outperforms　Graphone,　a　state-of-the-art　time-evolving　graph　storage　system,　by　15.9×　in　algorithm　execution　speed　and　1.45×　in　memory　usage.　　©　2015　IEEE.